CODEWITHSUNDEEP
c++c++11language-lawyerstdvector
Richard Hodges
Richard Hodges

Reputation: 69892

Does std::vector::reserve guarantee that the implementation will not invalidate iterators in this case?

Here is a function which intends to:

a) accept a vector of int

b) for each int in the input vector, append the inverse of this int

preconditions: none

postconditions: returned vector's size() is exacly 2 * the input vector's size.

Note that the vector is modified in-place.

Question:

Is this function strictly defined behaviour vis-a-vis iterator invalidation during the transform?

Bonus:

Is there a better/more succinct/robust way to write it?

Code:

std::vector<int> append_negatives(std::vector<int> v)
{
    v.reserve(v.size() * 2);
    std::transform(begin(v), end(v), 
                   back_inserter(v), 
                   [](auto&& x) { return -x; });
    return v;
}

Upvotes: 16

Views: 1875

Answers (2)

Matteo Italia
Matteo Italia

Reputation: 126827

The part about the iterator invalidation rules has already been covered, so I'll take this occasion to humbly question the need to use all this machinery (with its delicate rules) for such a trivial problem. You may also consider this a stab at the

Bonus:

Is there a better/more succinct/robust way to write it?

part of the question.

Honestly, I'd sidestep the problem completely with the advanced technology of for loops. KISS!

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz*2);
    for(size_t i = 0; i < sz; ++i) v[i+sz] = -v[i];
    return v;
}

Not everything must be obfuscated in a deep cloak of STL algorithms. This is both shorter, IMO more readable and avoids the headaches about iterators invalidation.

Also, unless compilers have gotten extra smart since last time I checked, this is significantly faster, as avoids all the overhead of push_back (check if capacity is enough and increment size at each iteration), which is replaced with straight pointer access (one assembly instruction); the slim and simple loop body gives better chances for automatic unrolling. I expect this to be faster to compile as well, as we avoid instantiating a bunch of templates.

Mind you, the speed advantage/no invalidation headache can be obtained even with the transform benemoth:

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz * 2);
    auto beg = begin(v);
    std::transform(beg, beg + sz, beg + sz, 
                   [](int x) { return -x; });
    return v;
}

but I fail to see any advantage of this kind of overly verbose code over a plain for loop, unless you are paid by the number of "cool" C++ features you manage to squeeze in your code.

@MikeMB asks about types that are costly to default-construct; in that case, an explicit push_back is fine:

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.reserve(sz*2); // optional
    for(size_t i = 0; i < sz; ++i) v.push_back(-v[i]);
    return v;
}

You could also use a range-based for loop if the transform in the original post was valid:

std::vector<int> append_negatives(std::vector<int> v) {
    v.reserve(v.size()*2);
    for(int &x: v) v.push_back(x);
    return v;
}

which is way nicer on the eyes than the transform-based solution, but I see in the comments that there's still no consensus about the end iterator invalidation, so this would be just as invalid.

Upvotes: 4

user7860670
user7860670

Reputation: 37587

As long as you don't exceed preallocated capacity no reallocation should happen and no references or iterators referring to vector items should get invalidated. However since iterator returned by end() does not refer to any vector items it may still get invalidated.

23.3.11.3 vector capacity [vector.capacity]

  1. ...No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity()

...

23.3.11.5 vector modifiers [vector.modifiers]

  1. ...If no reallocation happens, all the iterators and references before the insertion point remain valid.

Upvotes: 15

Related Questions