Generally speaking is it a good idea to cache an end iterator (specifically STL containers) for efficiency and speed purposes? such as in the following bit of code:
std::vector<int> vint;
const std::vector<int>::const_iterator end = vint.end();
std::vector<int>::iterator it = vint.begin();
while (it != end)
{
....
++it;
}
Under what conditions would the end value be invalidated? would erasing from the container cause end to be invalidated in all STL containers or just some?
Erasing from a container over which you are currently iterating is always a bad idea. The actual caching of your end iterator is not going to change that.
h.
If we are talking about efficiency and speed: caching the end iterator is unnecessary because of compiler optimizations and inlining.
I often use this style for iterating containers:
// typedef std::vector<Person> Persons;
Persons::iterator it = persons.begin(), end = persons.end();
for (; it != end; ++it)
{
Person & person = *it;
// ...
}
Erasing an element from a vector invalidates all iterators after the erased position.
I'm not certain about the other container types. In any case I think it would be safe to assume that all iterators become invalid after an erase. If you really need very specific information then you can always look it up. I rarely need this because because of my rather conservative coding style.
In general it should not matter if you cache the end iterator. If you feel it does matter, then you should already be using a profiler on your code and would be able to profile both variations. I'd suspect it could differ depending upon the container type - but a profiler would be the only way to know for sure given your compiler, optimizations and STL vendor.
Generally speaking is it a good idea to cache an end iterator (specifically STL containers) for efficiency and speed purposes?
If you use the STL container algorithms the caching of the end iterator is happens anyway (as you pass the result of container.end() as a parameter).
If you modify the memory of the container (insert/remove elements) it's a bad bad idea.
Also, caching for efficiency rarely makes much sense: in most cases the end() is inlined by the compiler, and when it is not, it is very probable that your efficiency doesn't hang on the end() result being cached. YMMV though.
In the simple case of a vector, the end iterator will change when you add or remove elements from the container; though, it's usually safest to assume that if you mutate the container while iterating over it, all iterators to it become invalid. Iterators may be implemented differently in any given STL implementation.
With regard to caching the end iterator -- it's certainly valid to cache it, but to find out if it is actually faster in your case, the best bet is for you to profile your code and see. While retrieving the end iterator from a vector is likely a fast implementation with a recent STL library and compiler, I have worked on past projects where caching the end iterator gave us a significant speed boost. (This was on the PlayStation 2, so do take with a grain of salt.)
The invalidation rules (for iterators) is defined very explicitly for each type of container. I find the SGI site very useful http://www.sgi.com/tech/stl/table_of_contents.html
Specifically for vectors I find:
[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.