Vector::iterator crashes on compare with begin

Question

I am trying to iterate in reverse through a vector. I've "made" an iterator using a typedef:

typedef std::vector<Object*>::iterator Cursor;

My problem is, this function seems to crash when it reaches the begin of the vector. I have the following code:

void InsertFunc(Cursor& it, Object& o) {
     vec_.insert(it, o);
     --it;
     for (; it >= vec_.begin(); --it) {
         if ((*it)->type() == Object::SomeType) {
             do_something
         } else {
             do_something_else
         }
     }
std::cout << "Insertion succes!" << std::endl;
}

I've tested it already, and I know for sure that the function reaches the begin of the vector, but then the program just terminates and the message "Insertion succes!" is never printed. Any idea why?

Run it through your debugger and obtain more information than "it just terminates". Also, this likely depends on what `do_something` and `do_something_else` do. I suspect an erase mechanic gone wrong. http://sscce.org — Lightness Races in Orbit, Dec 20 '13 at 15:00
If you are wanting to modify the contents of the container while iterating, `std::deque` is probably what you are after — smac89, Dec 20 '13 at 15:05
@πάνταῥεῖ I know for sure the iterator will never be at vec_.begin() when this function is called. — JNevens, Dec 20 '13 at 15:06
If you're inserting at the end of the vector you might be better off with push_back. If you're inserting at the front or back of the vector you might be better off with deque. If you're inserting in the middle of the vector you might be better off with list, but all of those considerations depend on what else you're doing with the vector. — YoungJohn, Dec 20 '13 at 15:37

score 7 · Accepted Answer · edited May 23 '17 at 10:32

7

Your iterator is potentially invalidated by the insert, if the elements had to be moved in memory due to a growing re-allocation.

You can obtain a new, valid iterator from the insert call itself:

it = vec_.insert(it, o);

And away you go.

Your following line, --it, will cause a failure if the new element was already at begin(); you've just iterated past the beginning. I'd revisit the logic of this function entirely, to be honest.

^{- Iterator invalidation rules}

edited May 23 '17 at 10:32

Community

1
1

answered Dec 20 '13 at 15:01

Lightness Races in Orbit

378,754
76
643
1,055

I didn't know that insert could invalidate the iterator. This worked for me, thanks! – JNevens Dec 20 '13 at 15:09

score 0 · Answer 2 · answered Dec 20 '13 at 15:20

0

First, the call to vec.insert( it, o ) can invalidate it. You want:

it = vec.insert( it, o );

(which returns an iterator to the inserted element).

Second, if it was equal to vec.begin(), the following --it is illegal.

And third, if it >= vec.begin() can never be false, unless the code contains undefined behavior: the valid range of iterators is it >= vec.begin() && it < vec.end(). (But we usually try to avoid comparisons for inequality on iterators, because not all iterators support them.

What you probably want is something like:

void InsertFunc( Cursor& it, Object const& o )
{
    it = vec.insert( it, o );
    while ( it != vec.begin() ) {
        -- it;
        //  ...
    }
}

When iterating backwards over a range, the usual solution is to use a while, with the decrementation at the top.

Alternatively, you can use reverse iterators:

void InsertFunc( Cursor& it, Object const& o )
{
    typedef std::vector<Object>::reverse_iterator RCursor;
    it = vec.insert( it, o );
    for (RCursor rit = RCursor(it); rit != vec.rend(); ++ rit ) {
        //  ...
    }
}

(Regretfully, there doesn't seem to be a make_reverse function. It wouldn't be hard to write, however.)

answered Dec 20 '13 at 15:20

James Kanze

150,581
18
184
329

What would `make_reverse` do, that the existing `RCursor` constructor does not already do? – Lightness Races in Orbit Dec 20 '13 at 15:44
Implicit type deduction. With `make_reverse` and `auto`, you wouldn't need the typedef, and you'd never have to spell out the type. (Same reason we have `make_pair`, for example.) – James Kanze Dec 20 '13 at 16:45
Ah, yes. That'll do. However I'd quite like _not_ to see C++ introduce `make_*` for all `*` just to satisfy the `auto`-mongers! – Lightness Races in Orbit Dec 20 '13 at 16:53
@LightnessRacesinOrbit I agree in general. Between `make_...` and `auto`, it's possible to write a program without having the slightest idea what types are involved. But iterators do seem to be a special case. They're used in very limited contexts, in very special ways, which tends to make the type more or less clear, or at least clear enough for someone reading the code to understand what is going on. – James Kanze Dec 20 '13 at 16:59
@LightnessRacesinOrbit And just to be clear: even with iterators, the use of `make_...` and `auto` is really only tolerable for loops like the above. The `make_...` are also useful when calling a template function. – James Kanze Dec 20 '13 at 17:02
I guess I have a problem with the emerging pattern of making a `make_*` for things, as if this were PHP. It seems so... analogue. But then without (gasp!) specifying a type, this is what we're left with: half the name of a function arbitrarily specifying a kind of type "category". Yuck! – Lightness Races in Orbit Dec 21 '13 at 00:21

Vector::iterator crashes on compare with begin

2 Answers2