Erase elements efficiently in tr1 :: unordered_map

Question

I am experimenting with tr1 :: unordered_map and came across a problem on how to remove elements efficiently. The erase method suggests deleting either the key or an iterator. I would suggest that the latter would be more efficient, since the former supposedly implies an implicit search operation. On the other hand, my research on the Internet has shown that iterators may become invalid after calling the insert () method.

I am interested in a typical situation in the real world where objects placed in a hash table have a lifespan that is long enough, so insert () calls occur during that lifespan. Thus, I can conclude that in such a situation, deleting by key is the only option left? Are there any alternatives on how to delete objects more efficiently? I am fully aware that this issue only matters in applications where deletion happens quite often. Whether this will be the case with my current project remains to be seen, but I would rather find out about these issues when developing my project, and not when there is already a lot of code.

Answer 1

The whole point of unordered containers is the fastest search time. Worrying about the time it takes to erase an item by keywords is like a classic example of premature optimization.

Answer 2

If this matters a lot to you because you are saving the iterator for some other reason, then C ++ 0x talks about std::unordered_map (quoting from FDIS) in 23.2.5 / 11:

Members of the insert and emplace should not affect the validity of iterators if (N + n) z * B, where N is the number of elements in the container before the insert operation, n is the number of elements inserted, B is the number of containers bucket, and z is the containers maximum coefficient load.

I have not tested whether the tr1 specification tr1 the same guarantee, but it is logical enough based on the expected implementation.

If you can use this guarantee, you can protect your iterators to a certain point. However, as Mark says, searching in unordered_map should be fast. Storing a key, not an iterator, is worse than storing an index, not an iterator, in vector , but better than the equivalent for map .

Answer 3

Yes, insert() can invalidate all iterators. Therefore, I do not think there is a way to avoid the (implicit) search. The good news is that the latter is likely to be cheap.