CODEWITHSUNDEEP
c++stldictionaryiterator
Frank
Frank

Reputation: 66214

Iterating over std::map<X,std::vector<Y> > and sorting the vectors

When iterating over std::map<X,std::vector<Y> >, may I sort the vectors, or might that invalidate the iterator?

In other words, is the following code okay?

typedef std::map<int, std::vector<int> > Map;
Map m;
for (Map::iterator it = m.begin(); it != m.end(); ++it) {
  std::sort(it->second.begin(), it->second.end());
}

Upvotes: 4

Views: 3262

Answers (4)

Tony Delroy
Tony Delroy

Reputation: 106156

Some misinformation here, so will chip in. std::maps are kind of special in that you can insert new elements without invalidating existing iterators, and removing an element only invalidates any iterators to that specific element. Given an iterator into the map, you may not modify the key (otherwise the sort order would be corrupted - one of the container's invariants), but you may modify the values however you like. Your array sorting falls into this last category of operation, and is perfectly fine.

To quote from the SGI STL page: http://www.sgi.com/tech/stl/Map.html

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Upvotes: 2

Simon Courtenage
Simon Courtenage

Reputation: 416

As aschepler says, your code is fine. I'd only add that there is a distinction between a vector which the map has as its target and the values inside any of the vectors. Because of this, you can change the values inside the vectors without affecting the map.

Upvotes: 0

icecrime
icecrime

Reputation: 76785

Your code is perfectly fine. As a matter of fact, you shouldn't have any doubt as you are neither inserting nor removing elements from the map : the structure of the map is unchanged, you are only affecting the values stored.

Upvotes: 2

aschepler
aschepler

Reputation: 72421

Your code is okay. Iterators from a map are only invalidated when you remove elements from the map. Modifying an element of an STL container never invalidates that container's iterators, only operations on the container itself, like removing or sometimes adding elements.

Upvotes: 6

Related Questions