Difference in behaviour of list::iterator and vector::iterator

Question

I have a std::list<int> and a std::vector<int>. I want to remove even elements from them, and duplicate odd element in them.

I've two different functions for both of them:

Vector:

std::vector<int> vec_remove_even_duplicate_odd(std::vector<int> target) {
    std::vector<int>::iterator begin = target.begin();

    while (begin != target.end()) {
        if (*begin % 2 == 0) {
            begin = target.erase(begin);
        } else {
            begin = target.insert(begin, *begin);
            begin += 2;
        }
    }

    return target;
}

This works fine. But the same function for std::list<int> shows error at the line begin += 2:

error: no match for ‘operator+=’ (operand types are ‘std::list<int>::iterator {aka std::_List_iterator<int>}’ and ‘int’)

If I change it to:

begin = begin + 2

it shows the following note:

note:   mismatched types ‘const std::reverse_iterator<_Iterator>’ and ‘int’

But, if I change that line to:

++begin;
++begin;

It works fine for list too. So what is it with this behaviour, that I might have missed while reading about containers.

Why is the += operator not defined for std::list<T>::iterator? And why that message for simple + operator? I haven't even created a reverse_iterator?

I'm aware that a vector is a contiguous structure, while a list is not. But how will that matter, given that post-increment is applicable? Is this issue specific to list only, or some other container also have this issue?

Since `std::list` is not contiguous, it's iterators can only move one at a time, so `++` works, but `+` doesn't. See http://stackoverflow.com/questions/5211914/types-of-iterator-output-vs-input-vs-forward-vs-random-access-iterator and http://www.cplusplus.com/reference/iterator/BidirectionalIterator/ — Mooing Duck, Jul 09 '13 at 19:36
@MooingDuck. Thanks. Didn't knew about different kinds of iterators. It's clear now. :) — Rohit Jain, Jul 09 '13 at 19:42

score 3 · Accepted Answer · edited May 23 '17 at 10:34

3

Since std::list is actually a linked list, its iterators provide only the functionality that is trivial to implement in such a data structure; in particular, std::list iterators are so-called bidirectional iterators, not random access iterators, thus they do not provide neither operator+= nor operator+, hence the messages you get.

If in a generic algorithm you need to go forward of n elements, regardless of the computational cost of the operation, you can use std::advance, which will use operator+= for random iterators and repeated application of ++ or -- in the other cases.

By the way, your loop for std::vector doesn't look fine - insertion and removal in a std::vector can invalidate iterators (including those you are using to iterate over your vector); you should change the approach of your algorithm (maybe the simplest thing is just to copy the elements in a separate vector).

edited May 23 '17 at 10:34

Community

1
1

answered Jul 09 '13 at 19:40

Matteo Italia

123,740
17
206
299

Also, `std::distance` is handy. And, `std::next` and `std::prev` in C++11 as well. – Mooing Duck Jul 09 '13 at 19:43
Thanks @Matteo. Didn't knew about different kinds of iterators. It's clear now. :) – Rohit Jain Jul 09 '13 at 19:43
Thanks @Matteo for the advice. I've just started learning C++. So, hopefully will learn about the these issues gradually. :) – Rohit Jain Jul 09 '13 at 19:50
@RohitJain: be ready, C++ is an ugly beast :) - by the way, when writing algorithms to work on containers check out the content of [the header ``](http://www.cplusplus.com/reference/algorithm/), you may well find most of the work already done. – Matteo Italia Jul 09 '13 at 19:53
1

@MatteoItalia. That is certainly a handful of algorithms in one header. Thanks. Probably will be of use once I learn how to do it myself. :) And yes, it seems like a complex language. Since I've accepted the challenge, let's face it :) – Rohit Jain Jul 09 '13 at 19:57
@MatteoItalia. When I replaced `begin += 2` with `std::next(begin, 2)`, my machine hanged. I had to restart it. Is this the problem with the function or, it hanged just by chance. – Rohit Jain Jul 09 '13 at 20:15
`std::next` doesn't increment the iterator - it returns a new iterator, incremented by the value you specified, which got you stuck into an infinite loop that continued to add elements to the vector. Use `std::advance` (remember: `std::next`=>`+`, `std::advance`=>`+=`). By the way, restarting the machine shouldn't be necessary, you should be able to kill the process before (although on Windows it may require some time once the system start thrashing due to all the requested memory). – Matteo Italia Jul 09 '13 at 20:41

Difference in behaviour of list::iterator and vector::iterator

1 Answers1