Efficiently erasing elements in tr1::unordered_map

Question

I am experimenting with tr1::unordered_map and stumbled upon the problem how to efficiently delete elements. The 'erase' method offers to delete either by key or by iterator. I would assume the latter to be more efficient, since the former presumably involves an implicit find operation. On the other hand my investigations on the internet have revealed that iterators may become invalid after calling the insert() method.

I am interested in a typical real-world situation, where objects put into a hash table have a life span which is long enough such that calls to insert() happen during that life span. Thus may I conclude that in such a situation deletion by key is the only option left? Are there any alternatives how to delete objects more efficiently? I am fully aware that the question only matters in applications, where deletions happen often. Whether this will be the case for my current project, remains to be seen, but I would rather learn about these issues while designing my project rather than when there is already a lot of code present.

Answer 1

The whole point of the unordered containers is to have the fastest possible lookup time. Worrying about the time it takes to erase an element by key sounds like the classic example of premature optimization.