Sign in to follow this  
fathom88

C++ and STL's Map Silly Question

Recommended Posts

I'm trying to access a member of a map. For example, I want to see the 3rd element in a map. map<string, string>::iterator i = Map.begin(); i += 2; Does not compile. I know this works. i++; I could just increment in a loop until I reach the correct number. Yes, I realize I can do a Find with the map. However, I looking to access my map via index. Is there a better way to do it? Thanks in advance.

Share this post


Link to post
Share on other sites
You can use std::advance() on a map iterator. This isn't a particularly efficient method of doing things. If you really want an index then you should consider other solutions like using a vector of pointers to map elements, a second map or a multi-index container.

Share this post


Link to post
Share on other sites
std::map does not provide random-access iterators. While at any given time there may be such a thing as the "third element" in the container, it is not a stable third element and may show up at a completely different point in the iteration the next time the map is iterated.

You can access this element by using an iterator and incrementing it in a loop until you reach the desired 'index,' or by using std::advance. I do not recommend this at all, however.

If you need to access the map elements by index, use an auxiliary data structure, or revisit the utility of map in the first place.

Share this post


Link to post
Share on other sites
Quote:
Original post by fathom88
I'm trying to access a member of a map. For example, I want to see the 3rd element in a map.


Why do you think you want to do this?

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
std::map does not provide random-access iterators. While at any given time there may be such a thing as the "third element" in the container, it is not a stable third element and may show up at a completely different point in the iteration the next time the map is iterated.
Um, map is an ordered container. Iteration will proceed in non-descending order of keys. Were you thinking of TR1's unordered_map (although I think even that might provide some guarantees for iteration)?

Σnigma

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
Quote:
Original post by jpetrie
std::map does not provide random-access iterators. While at any given time there may be such a thing as the "third element" in the container, it is not a stable third element and may show up at a completely different point in the iteration the next time the map is iterated.
Um, map is an ordered container. Iteration will proceed in non-descending order of keys. Were you thinking of TR1's unordered_map (although I think even that might provide some guarantees for iteration)?

Σnigma


I did not say map was unordered. I said the index is not stable. Perhaps I should have been more specific, I didn't mean 'stable' in the algorithmic sense you might see it applied when discussing, say, sorting:

My point was that an 'index' is a relatively meaningless property to associate with map elements; the iteration will produce stable results as long as nothing is added to or removed from the map. But inserting a new key into the map may, since the map is ordered, insert that key anywhere (based on the comparison function used for the map). This can disrupt the apparent index of the element in the map in an implicit fashion (versus the explicit fashion that a indexed-insert on something like a vector).

Thus, associating 'indices' with map elements is generally a sign that either the wrong data structure is being used, or an auxiliary one needs to be used. Because of the implicit nature of index remapping in a map, it's harder to make sure all indices pointing into the map elements stay valid across an insertion or removal -- it requires knowledge of the comparison predicate, and of the current map contents, versus simply knowing which index is being inserted at in something like a vector.

Share this post


Link to post
Share on other sites
I don't see why that's tongue-in-cheek. For an infrequently updated dictionary, that's close to an ideal solution (assuming you sort it).

Share this post


Link to post
Share on other sites
I have done a combination of vector<MyElement*> and map<string, MyElement*> in my XML-like file format. That way, the user can call MyDocument::GetFirstElement()/GetLastElement() for sequential iteration and MyDocument::GetElement(Name) for lookup.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this