4

As I look at the standard for different STL objects and functions, one thing that doesn't make sense to me is why would the begin() and end() functions for container objects return an iterator by value rather than by constant reference? It seems to me that iterators could be held by the container object internally and adjusted whenever the container is mutated. This would mitigate the cost of creating unnecessary temporaries in for loops like this:

for (std::vector<int>::iterator it=my_vec.begin(); it!=my_vec.end(); ++it){
    //do things
}

Is this a valid concern? Is there something about using references to iterators that makes this a bad idea? Do most compiler implementations optimize this concern away anyway?

c.hughes
  • 284
  • 1
  • 13
  • But then a container would be a container of objects and iterators. That sounds like a lot of overhead. You could be holding many, many iterators into the same container. – CB Bailey Feb 26 '13 at 19:42
  • Indeed, there are reasonable algorithms that construct a second container of iterators, just as big as the initial container, to establish a second, independent order. – MSalters Feb 26 '13 at 19:50
  • 2
    Try to follow that train of thought and see where it takes you... `begin()` returns a reference to an iterator, what happen if you *copy* it (so that you can increment it)? How does the container know how many copies were done? Where would it hold those iterators? – David Rodríguez - dribeas Feb 26 '13 at 20:14
  • @DavidRodríguez-dribeas I don't think it would be the container's responsibility to keep track of copies of that iterator. But yes, it seems it would be silly to have begin() return a reference given that the user would be forced to manually copy the iterator to be able to iterate over the container. – c.hughes Feb 26 '13 at 20:20
  • Note also that STL algorithms all take iterators by value. – Marc Glisse Feb 26 '13 at 20:27
  • 1
    Are your going to implement device drivers in C++? Always remember the golden rule of software-engineering: "Think about optimization only if the bottleneck was proven". I remember a project, where the usage of STL was prohibited because of performance. But, they used tons of images in GUI-themes and the software was slow because of silly GUI design. – Valentin H Feb 26 '13 at 23:11
  • @ValentinHeinitz: My manager pointed this question's subject out recently and I got curious about why the STL specification would do something that seemed sub-optimal. Now I have found that it isn't a big concern. – c.hughes Feb 27 '13 at 15:35

3 Answers3

5

Iterators are designed to be light-weight and copyable (and assignable). For example, for a vector an iterator might literally just be a pointer. Moreover, the whole point of iterators is to decouple algorithms from containers, and so the container shouldn't have to care at all what kind of iterators anyone else is currently holding

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
5

If the begin and end methods returned a reference, the container would be forced to have each of those iterators as members. The standards people try to leave as much flexibility to an implementation as possible.

For example you can create a simple wrapper for an array that behaves as a standard container and doesn't consume any extra memory. If this wrapper were required to contain the iterators it wouldn't be so simple or small anymore.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • "*For example you can create a simple wrapper for an array that behaves as a standard container and doesn't consume any extra memory*" Thank you C++11: [`std::array`](http://es.cppreference.com/w/cpp/container/array) – Manu343726 Mar 26 '14 at 22:19
0

Well, if you choose right iterator, STL would :-)

for (
    std::vector<int>::const_iterator it=my_vec.begin(), 
    end=my_vec.end(); 
    it!=end; 
    ++it)
{
    //do things
}

Iterator in STL has pointer-semantic. Const iterator has const pointer semantic.

Valentin H
  • 7,240
  • 12
  • 61
  • 111
  • The end() function still returns a const_iterator by value in that situation. I was stating concern over the performance costs of creating and destroying a bunch of temporary iterator objects. – c.hughes Feb 26 '13 at 20:14
  • 1
    @c.hughes: In this version of loop end() is called only once. In your version - size-times of my_vec. Btw: on Win64, VS2008 sizeof(std::vector::const_iterator) returns 12. It's not that much. – Valentin H Feb 26 '13 at 23:05
  • Oh, I see what you did there. Your comments made me only pay attention to the fact that you used const_iterator. – c.hughes Feb 27 '13 at 15:28