In a C++ programming book I saw the following for a std::list iterator:
for (iterator = list.start(); iterator != list.end(); iterator++)
Isn't it inefficient to call list.end() all the time? Would it be better to save the end to another variable or will the C++ compiler (i. e. g++) take care of this automatically?
list::end() ought to have constant time complexity and for linked lists in particular it means it's probably very efficient.
It could be slightly more efficient to store the value if your algorithm allows that (again, the difference is unlikely to be large for especially linked lists).
Oh, and and do read Steve Jessop's answer about testing the efficiency yourself!
It's unlikely to make any difference.
Standard container functions get inlined, so there should be no noticeable function call overhead. What's left is whether the optimizer is smart enough to avoid unnecessary overhead that's not strictly necessary in order to perform the comparison. For example: does it actually create a temporary list::iterator object, fill in its current position field, and then read that field back, or does the comparison end up just as a pointer comparison between a value from iterator and a value in the head of the list?
Even if there is some unnecessary overhead, it might be negligible compared with incrementing the iterator, and even more negligible compared with your loop body.
You could test it, which is more reliable than guessing. Remember to enable optimization -- testing performance without optimization is kind of like saying that Blake must be faster than Bolt if Blake walks quicker from the warm-up track to the bus.
Generally, no, it's not inefficient. end() will typically be an inline function, and the compiler will generate good code to do whatever it does. More to the point, inefficient compared to what? Yes, you could add code to create a variable to hold the result, and that might or might not be a little bit faster than simply calling end(). It seems very unlikely that such a change would make a big enough speed difference to turn a program that's too slow into one that meets requirements.
The call to std::list<T>::end() is unlikely to be a big efficiency issue and probably just reads a single value. However, you'd give the compiler a hint that it isn't meant to change by storing it a variable. For other containers a computation may be involved in addition to reading a base address which is a bit more involved. Still nothing dramatic but possibly worth avoiding.
Note, however, that it may also change the semantic of the loop: If the body of the loop may append elements, the former end may move. Interestingly, I don't find any specific requirements in the standard stating whether std::list<T>::end() may change when inserting elements into the container (I can imagine implementations where it does change as well as some where it doesn't; most likely it doesn't change, though). If you want to get guaranteed behavior when also modifying the list, you might very well call list.end() in every iteration.
BTW, there is a bigger performance concern I'd have about using iterator++ instead of ++iterator, especially this is really what the author used in the book. Still, this is a micro optimization like storing the result of list.end() but one cheap to do.
In practice, for STL containers, container::end() is extremely cheap. In fact, the C++ standard mandates algorithmic complexity for several methods of several classes (if not for all), and container::end() is always constant-time.
Also, the compiler is free to inline those methods, removing essentially any overhead it could have. I can think of no other way to get the end of a list in constant time than storing it, so your list.end() call probably ends up being a field access, which is no more expensive on x86 platforms than storing it on the stack.
Your mileage may vary with other collections, but it's a safe bet that list.end() will not end up being your bottleneck.
If you need to micro-optimize, yes.
In general, calling list.end() won't have a significant performance penalty and probably won't be an issue. It may return the same value every call, may be inlined, and so on. While not slow, it does take some small amount of time.
If you absolutely need the speed, you want to use for (iterator = list.start(), end = list.end; iteration != end; ++iterator). This caches the end iterator (and does a pre-inc), and should have no repeated calls.
The second type is typically unnecessary, but if .end() is expensive or the loop is very large, may be useful.
While premature optimization is evil, good habits are not. If you don't expect your loop termination condition to change, i.e. you're not changing the container, then this pattern can be used:
for (mylist::iterator it = alist.begin(), finish = alist.end(); it != finish; ++it)
The compiler is unlikely to make this optimization for you if it can't determine that the container isn't changing.
Note that this is unlikely to make a measurable timing difference, but it can't hurt.
One good reason not to cache end() on std::list is that it prevents you from making the following mistake:
for (iterator = list.rstart(), end = list.rend(); iterator != end; iterator++) {
// modify list
No iterators will be invalidated when you make modifications in std::list, but rend is NOT a sentinel (it points to the first element of the underying list), which means that it will stop being the end of the list if you append to the end of the reverse list (aka prepend to the beginning of the unreversed list.)
