Is there any reason that the STL does not provide functions to return an iterator via index?

Question

Hi,

Is there a reason that the STL does not provide functions to return an iterator into a container via an index?

For example, let's say I wanted to insert an element into a std::list but at the nth position. It appears that I have to retrieve an iterator via something like begin() and add n to that iterator. I'm thinking it would be easier if I could just get an iterator at the nth position with something like, std::list::get_nth_iterator(n).

I suspect I have misunderstood the principles of the STL. Can anyone help explain?

Thanks BeeBand

Answer 1

You can use advance() from the <iterator> header:

list<foo>::iterator iter = advance(someFooList.begin(), n);

list<foo>::iterator iter = someFooList.begin();

std::advance( iter, n);

If the iterator supports random access (like vector) it'll work quite efficiently, if it only supports increasing (or decreasing) the iterator, like list, it'll work but only as well as can be.

Answer 2

std::list is a linked list. So it does not support random access. To get to the nth position in the list, you have to start at the beginning and move through all the nodes until you arrive at n. This is pretty expensive (O(n)), and thus it's bad to have a method that does not suggest this expense. get_nth_iterator(n) implies getting the iterator that points to the nth node is cheap.

std::vector of course supports this directly with the [] operator, because the datastructure supports random access and so this is very inexpensive for it.

Answer 3

std::list isn't random-access container, so there is no reason for accessing n-th element. if you need this, consider using std::vector instead..

Answer 4

Generally, anything that might be costly is made a bit clumsy, so you won't do it by accident. Using your example, with a container that provides random access iterators it would be simply container.begin()+n, but for an std::list (which provides a forward iterator) you'd need to use list.begin() followed by advance().

If you want to get the N^th iterator, chances are that you just shouldn't be using std::list in the first place. Then again, if you started that sentence at "chances", it would remain nearly as true...