Isn't calling `list<T>::end()` inefficient?

Question

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?

Answer 1

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!

Answer 2

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.

Answer 3

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.