467,142 Members | 1,343 Online

Quickest way to find the rank of a <map>

 Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Thanks Steve Feb 28 '06 #1
• viewed: 3983
Share:
13 Replies
 Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Check out the member functions of std::map, notably, find. Your algorithm is O(n), the member function is probably O(log2 n). Ben Pope -- I'm not just a number. To many, I'm known as a string... Feb 28 '06 #2
 In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Check out the member functions of std::map, notably, find. Your algorithm is O(n), the member function is probably O(log2 n). Ben Pope Thanks, but that returns an iterator to the element. I'm not sure how this helps me determine its index. Steve Feb 28 '06 #3
 Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? std::map<> is an associative container with elements sorted based on some comparison operator. In other words, it doesnot really mean anything to find "index" of an element in std::map<> - (You cannot really insert an element in a map at a "given position", unlike say, std::vector<>, where you can). If by the word "index" you actually mean the "iterator" to the element, then the member function find() will do the trick. This function takes a key and returns the iterator to the element with that key (and the iterator to end() otherwise if no such element exists) Feb 28 '06 #4
 Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Check out the member functions of std::map, notably, find. Your algorithm is O(n), the member function is probably O(log2 n). Ben Pope Thanks, but that returns an iterator to the element. I'm not sure how this helps me determine its index. #include #include #include int main() { std::map m; m[3] = "foo"; m[6] = "bar"; m[9] = "baz"; m[12] = "qux"; m[15] = "quux"; std::map::iterator iter = m.find(3); if(iter != m.end()) { std::cout << "element with key: " << iter->first << " , value: " << iter->second << " , has index: " << std::distance(m.begin(), iter) << std::endl; } return 0; } Does that help? Ben Pope -- I'm not just a number. To many, I'm known as a string... Feb 28 '06 #5
 Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. No. The problem is that is designed so inserting an element is fast. Yet if you insert a new element at rank 1, all existing items have their rank changed. If this rank was stored, getting the rank would be fast but insertion would be slow. It's a design tradeoff, and std::map wasn't designed for it. You could try a vector, notstd::pair_greater_first> vmapOfFreq HTH, Michiel Salters Feb 28 '06 #6
 In article , Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Check out the member functions of std::map, notably, find. Your algorithm is O(n), the member function is probably O(log2 n). Ben Pope Thanks, but that returns an iterator to the element. I'm not sure how this helps me determine its index. Once you have the iterator, you can use std::distance. -- Magic depends on tradition and belief. It does not welcome observation, nor does it profit by experiment. On the other hand, science is based on experience; it is open to correction by observation and experiment. Feb 28 '06 #7
 In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: std::distance(m.begin(), iter) Thanks, that's the function I couldn't figure out. Steve Feb 28 '06 #8
 Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: std::distance(m.begin(), iter) Thanks, that's the function I couldn't figure out. Steve Of course this call is still O(n) - as any solution must be. Something tells me you should instead use a std::vector for your job and keep it sorted. This assumes that the data in the map doesn't normally change, but if it does your "rank" is not of much use anyway. /Peter Feb 28 '06 #9
 In article <11**********************@t39g2000cwt.googlegroups .com>, Mi*************@tomtom.com wrote: Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. No. The problem is that is designed so inserting an element is fast. Yet if you insert a new element at rank 1, all existing items have their rank changed. If this rank was stored, getting the rank would be fast but insertion would be slow. It's a design tradeoff, and std::map wasn't designed for it. You could try a vector, notstd::pair_greater_first> vmapOfFreq HTH, Michiel Salters Thanks, I can see why rank is not stored. But I wondered if when you did a retrieval-by-key, the behind-the-scenes search algorithm would become aware of the position within the sorted list, and hence be able to provide the rank as a by-product of the search. Feb 28 '06 #10
 In article <11*********************@v46g2000cwv.googlegroups. com>, "Neelesh Bodas" wrote: Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? std::map<> is an associative container with elements sorted based on some comparison operator. In other words, it doesnot really mean anything to find "index" of an element in std::map<> - (You cannot really insert an element in a map at a "given position", unlike say, std::vector<>, where you can). If by the word "index" you actually mean the "iterator" to the element, then the member function find() will do the trick. This function takes a key and returns the iterator to the element with that key (and the iterator to end() otherwise if no such element exists) Thanks, I do take your point, but that's not to say that the rank isn't a very useful bit of info. (sets that store scores often need to be queried for rank i.e. "who came 7th?", "what rank is the one that scored x?") No problem, I can just iterate over them, or use std::distance(m.begin(), iter) as Ben suggested. Steve Feb 28 '06 #11
 In article <11**********************@e56g2000cwe.googlegroups .com>, "peter koch" wrote: Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope wrote: std::distance(m.begin(), iter) Thanks, that's the function I couldn't figure out. Steve Of course this call is still O(n) - as any solution must be. Something tells me you should instead use a std::vector for your job and keep it sorted. This assumes that the data in the map doesn't normally change, but if it does your "rank" is not of much use anyway. /Peter Yes, after reading the various posts I appreciate the problem now. Searching by key is the most important job I have to do though, so I'll just put up with having to determine rank manually. Steve Feb 28 '06 #12
 Steve Edwards wrote in news:gf***********************@news.btinternet.com : In article <11**********************@t39g2000cwt.googlegroups .com>, Mi*************@tomtom.com wrote: Thanks, I can see why rank is not stored. But I wondered if when you did a retrieval-by-key, the behind-the-scenes search algorithm would become aware of the position within the sorted list, and hence be able to provide the rank as a by-product of the search. Nope. Nothing says that the map is stored in any sort of linear way. It's far more likely that it's stored in some sort of tree data structure. Feb 28 '06 #13
 Steve Edwards wrote: Hi, Given a map: typedef map > mapOfFreq; Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. As others have pointed out, std::map<> does not support this. If performance of this operation turns out to be critical, you can, however, design a container very much like std::map<> based upon a balanced tree. In addition to a key/value pair, every node would also keep a count of the size of the subtree whose root the given node is. This way, you can obtain the position of a node in the traversal order in log(N) time by adding some sizes along a path. The costs for updating the size information is also logarithmic. Thus, you can keep log(N) performance for insert/erase. Best Kai-Uwe Bux Mar 1 '06 #14