STL: keep order for map
-
Hi, I need to keep an (arbitrary) order for a map. My idea is to use the map<> for fast lookup, and a separate list to keep the original order, but I wonder if there's a better way. TIA Peter
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
-
Hi, I need to keep an (arbitrary) order for a map. My idea is to use the map<> for fast lookup, and a separate list to keep the original order, but I wonder if there's a better way. TIA Peter
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
What are you storing as the value in your map? Could you create a class for your value that contains your data and a sort value?
class MyData
{
MyClass m_MyClass;
int m_SortIndex;
};What do you need to determine from the separate list? Do you need to traverse the data in a sorted order once you find a starting point or something? It really depends on what you're going to do after you find an item in your map. Todd Smith
-
What are you storing as the value in your map? Could you create a class for your value that contains your data and a sort value?
class MyData
{
MyClass m_MyClass;
int m_SortIndex;
};What do you need to determine from the separate list? Do you need to traverse the data in a sorted order once you find a starting point or something? It really depends on what you're going to do after you find an item in your map. Todd Smith
value is either a string, or a class mainly containing a string-string map (with the same problem): I need fast string-based lookup, so I guess I will need a map. (lookup is case insensitive, but original case should be preserved, a linear search in an unsorted list is probably a really bad idea) I will continually insert, erase, and change values in the map, but at the same time, I need to iterate over the map in the same order as items were added to the map (bare thiose that were removed, of course) e.g. map["polonius"] = "rat" map["ophelia"] = "dead"; map["hamlet"] = "mad"; // iterate over map so I get it in order polonius, ophelia, hamlet map["hamlet"] = "dead"; map["polonius"] = "dead"; map.erase("ophelia"); // iterate original order again - now only polonius, hamlet map["ophelia"] = "floating"; // iterate - now it doesn't matter if it's p-h-o, or p-o-h if the key was an integer, I wouldn't hesitate to simply use a separate list as an index, but I wonder if there's a mroe effective method e.g.: could I use a list< map::iterator >, or even a list instead? (provided I remove them from the lsit before removing them from the map) Although other iterators should not be affected by inserting / removing, I'm still a bit "shaky" on this topic... Peter
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
-
value is either a string, or a class mainly containing a string-string map (with the same problem): I need fast string-based lookup, so I guess I will need a map. (lookup is case insensitive, but original case should be preserved, a linear search in an unsorted list is probably a really bad idea) I will continually insert, erase, and change values in the map, but at the same time, I need to iterate over the map in the same order as items were added to the map (bare thiose that were removed, of course) e.g. map["polonius"] = "rat" map["ophelia"] = "dead"; map["hamlet"] = "mad"; // iterate over map so I get it in order polonius, ophelia, hamlet map["hamlet"] = "dead"; map["polonius"] = "dead"; map.erase("ophelia"); // iterate original order again - now only polonius, hamlet map["ophelia"] = "floating"; // iterate - now it doesn't matter if it's p-h-o, or p-o-h if the key was an integer, I wouldn't hesitate to simply use a separate list as an index, but I wonder if there's a mroe effective method e.g.: could I use a list< map::iterator >, or even a list instead? (provided I remove them from the lsit before removing them from the map) Although other iterators should not be affected by inserting / removing, I'm still a bit "shaky" on this topic... Peter
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
peterchen wrote: a linear search in an unsorted list is probably a really bad idea How many items do you expect the container to hold? And what kind of performance do you need? A list would be easiest to implement assuming a linear search isn't to slow. Todd Smith
-
peterchen wrote: a linear search in an unsorted list is probably a really bad idea How many items do you expect the container to hold? And what kind of performance do you need? A list would be easiest to implement assuming a linear search isn't to slow. Todd Smith
typical 10, 100 not unusual - admitted, that's not too much. but typical access is over two maps, and comparison is case-insensitive (which adds up) But maybe you're right, I should implement it with a simple list, and see how fast it is.
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
-
value is either a string, or a class mainly containing a string-string map (with the same problem): I need fast string-based lookup, so I guess I will need a map. (lookup is case insensitive, but original case should be preserved, a linear search in an unsorted list is probably a really bad idea) I will continually insert, erase, and change values in the map, but at the same time, I need to iterate over the map in the same order as items were added to the map (bare thiose that were removed, of course) e.g. map["polonius"] = "rat" map["ophelia"] = "dead"; map["hamlet"] = "mad"; // iterate over map so I get it in order polonius, ophelia, hamlet map["hamlet"] = "dead"; map["polonius"] = "dead"; map.erase("ophelia"); // iterate original order again - now only polonius, hamlet map["ophelia"] = "floating"; // iterate - now it doesn't matter if it's p-h-o, or p-o-h if the key was an integer, I wouldn't hesitate to simply use a separate list as an index, but I wonder if there's a mroe effective method e.g.: could I use a list< map::iterator >, or even a list instead? (provided I remove them from the lsit before removing them from the map) Although other iterators should not be affected by inserting / removing, I'm still a bit "shaky" on this topic... Peter
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]
Why does the lookup need to be based on string comparison? If you just want fast lookup preserving the order of insertion, try using this class as the key of your map this:
class seq_string
{
public:
seq_string(const char *str):str(str),count(total_count++){}
seq_string(const std::string& str):str(str),count(total_count++){}
seq_string(const seq_string& r):str(str),count(total_count++){}
operator const char *()const{return str.c_str();}
operator const std::string&()const{return str;}
bool operator <(const seq_string& r)const{return count<r.count;}
private:
std::string str;
unsigned int count;
static unsigned int total_count;
};
...
unsigned int seq_string::total_count=0;Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
-
Why does the lookup need to be based on string comparison? If you just want fast lookup preserving the order of insertion, try using this class as the key of your map this:
class seq_string
{
public:
seq_string(const char *str):str(str),count(total_count++){}
seq_string(const std::string& str):str(str),count(total_count++){}
seq_string(const seq_string& r):str(str),count(total_count++){}
operator const char *()const{return str.c_str();}
operator const std::string&()const{return str;}
bool operator <(const seq_string& r)const{return count<r.count;}
private:
std::string str;
unsigned int count;
static unsigned int total_count;
};
...
unsigned int seq_string::total_count=0;Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
thanks for the suggestion, but I need both string-based lookup, and iteration in (temporal) order of insertion (although your class keeps the info, it would about O(n*n) to actually iterate in "sorted by count" order) I'll go with the list<> implementation and a linear search, and make some speed comparisons. [edit] some interesting results (not all to much surprising) times only for lookup with <= 10 strings, the list is faster, for 25 strings it's list is about factor 2 slower, factor 3 for 50. (map looses early for creation of a std::string from literal when doing the lookup, and additional comparison for equality) Having said that, With 25 strings in a list I get ca. 200.000 accesses / second on my 1.3GHz box, not astonishing, but fast enough for most uses. All this is just lookup, map insertion is of course much slower due to additional comparisons (and I might be stuck with thousands of inserts and just a few lookups), so list implementation is "perfect enough"
One day I might find it quite amusing how touching tongues make life so confusing Anne Clark again [sighist]