CODEWITHSUNDEEP
c++stl
user1095108
user1095108

Reputation: 14603

end() iterator in associative containers

Does this code work across all standard compliant C++ compilers (it works with g++)? Why (please give c++11 reference, if possible)? How about std::unordered_map and associative containers in general?

std::map<std::string, std::string> map;

std::map<std::string, std::string>::iterator i(map.end());

map.insert({"bla", ""});
map.insert({"hah", ""});

assert(map.end() == i);

Upvotes: 2

Views: 317

Answers (5)

doron
doron

Reputation: 28872

The end iterator indicates that one cannot iterate further through a contained and therefore should be expected to change when new elements are inserted into the container.

maps are normally implemented as a binary tree and may use a special value (such as NULL) to indicate that further iteration is impossible. But this is a result of the underlying implementation and has nothing to do with specified behaviour.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490108

For map, yes -- virtually nothing but deletion of the referred-to object invalidates an iterator in a map.

For unordered_map, in practice, maybe yes for this specific case -- the end iterator is often a bit different from other iterators, so it may not contain any actual address or anything like that -- it's just a special sentinel value that other iterators will compare equal to after you've iterated across an entire container.

That's not really guaranteed though. Specifically, your insertions could cause rehashing, [Edit: here I'm more or less assuming that your two insertions are intended as a place-holder for some arbitrary number of insertions. You can figure out whether re-hashing happens for a specific load factor, number of insertions, etc., but you generally don't want to -- depending on it leads to fragile code] and rehashing invalidates iterators (§23.2.5/8). Although (as mentioned above) the iterator returned by end() is often "special", the standard doesn't require that, so after the insertions, what you previously got from end may be invalid, so virtually nothing is required about it (including comparing equal to anything in particular).

Upvotes: 2

Jesse Good
Jesse Good

Reputation: 52365

It seems you are looking for quotes from the standard concerning interator invalidation:

For set, multiset, map and multimap

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

For unordered_set, unordered_map, unordered_multiset, and unordered_multimap

The insert members shall not affect the validity of iterators if (N+n) < z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor.

So, for map insertion does not invalidate the end iterator, however, for unordered_map it will if the number of elements added to the existing number of elements exceeds bucket_count * max_load_factor.

Upvotes: 3

hmjd
hmjd

Reputation: 121961

From C++ 03 standard section 23.1.2 Associative containers [lib.associative.reqmts], point 8 states:

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

From C++11 standard section 23.2.4 Associative containers [associative.reqmts], point 9 states:

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Based on this, the assert() in the posted code will be true.

EDIT:

These quotes are not true for unordered containers: see answer from Jesse.

Upvotes: 1

ApprenticeHacker
ApprenticeHacker

Reputation: 22011

The code uses extended initialiazer lists over here:

map.insert({"bla", ""}); // the {"bla", ""}

This is a C++ 11 feature, hence won't work on non-C++ 11 compilers.

Working on Compilers:

  • GCC 4.4.1 and all later versions

Not working:

  • Digital Mars C++
  • Borland C++ (Not exactly mainstream, but still checked)
  • Visual C++
  • Obviously most compilers that don't support C++ 11

Upvotes: 0

Related Questions