Incrementing iterator using an integer

[janac]

My question is: why can't I increment a list iterator using an integer? Here's the error, which says the + operator isn't defined for list iterator.

"binary '+': 'std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator"

If I change the container to a deque, it runs fine. I've been searching for a list of defined operators for iterators ... where can I find one? Thanks in advance for any help.

  int my_array[] = {1, 2, 3, 4, 5};
  list<int> my_list(my_array, my_array + 5);
  list<int>::const_iterator it = my_list.begin() + 3;

[DizzyDon]

The iterator category for std::list is LegacyBidirectionalIterator, which only allows read, increment (with multiple passes), and decrement. The next category up, LegacyRandomAccessIterator allows +, -, etc. A deque uses random access iterators.

See https://en.cppreference.com/w/cpp/iterator

[jonnin]

there is no direct way to implement a + operation, so it would be terribly slow for a list of any size. You can define it, but how you gonna get to the data? By ++ one at a time.

[janac]

DizzyDon, thanks for the link.

jonnin, I see what you mean. But then, why does + 3 work for a deque? I don't get an error when I change to that container.

Could you guys take a look at my next question?

[George P]

Each C++ container has different design objectives for use and access to elements using iterators. What works for a std::deque (or std::vector) might not work for a std::list as your example shows.

Iterators are not pointers, though they can act like them. Iterators can be incremented, just not always in the way regular arrays (and pointers) can be. Depending on the iterator category used for the container.
https://en.cppreference.com/w/cpp/iterator

std::list is LegacyBidirectionalIterator.

#include <iostream>
#include <list>

int main()
{
   int my_array[ ] { 1, 2, 3, 4, 5 };

   std::list<int> my_list(my_array, my_array + 5);

   std::list<int>::const_iterator it { my_list.begin() };

   it++; it++; it++;

   std::cout << *my_list.begin() << ' ' << * it << '\n';
}

std::vector is LegacyRandomAccessIterator

#include <iostream>
#include <vector>

int main()
{
   int my_array[ ] { 1, 2, 3, 4, 5 };

   std::vector<int> my_list(my_array, my_array + 5);

   std::vector<int>::const_iterator it { my_list.begin() + 3 };

   std::cout << *my_list.begin() << ' ' << * it << '\n';
}

And putting up a Short, Self Contained, Correct (Compilable), Example (SSCCE) goes a long way to enticing people to help, it is catnip to a lot of programmers.
http://www.sscce.org/

Not every C++ container can be accessed like a regular array using pointer math.

[janac]

Thanks for all the help.

I thought programmers would rather see as little as possible, relevant code. Now that I know that's not true, I'll head over to sscce.org.

[jonnin]

On the surface there is no reason in the world that a dequeue would allow this and a list not, since its more or less a doubly linked list.
the only answer I have on that is 'because c++ said so'.
Or, another answer, the c++ containers do not align 100% with a traditional data structures book.

comes down to, the dequeue represents a linked list, maybe, but isnt implemented that way:

https://www.cplusplus.com/reference/deque/deque/

Specific libraries may implement deques in different ways, generally as some form of dynamic array. But in any case, they allow for the individual elements to be accessed directly through random access iterators, with storage handled automatically by expanding and contracting the container as needed.

[TheIdeasMan]

cppreference wrote:

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

https://en.cppreference.com/w/cpp/container/deque

[JLBorges]

> On the surface there is no reason in the world that a dequeue would allow this and a list not,
> since its more or less a doubly linked list.

No, it is not anything like a doubly linked list.

It could theoretically be implemented as a vector of vectors (with constant time random access),
but not as a list of vectors (which would not permit constant time random access).

[seeplus]

Don't forget std::next() which can take a number of element positions to offset from current position. If the container doesn't support random access then it's done by incrementing (or decrementing) by 1 in a loop.

See http://www.cplusplus.com/reference/iterator/next/

For a list of what can be done by what type of iterator, see
http://www.cplusplus.com/reference/iterator/