CODEWITHSUNDEEP
c++vectorreferenceinsert
Maksim
Maksim

Reputation: 191

vector::insert in VS2010 performs unexpected result

I occasionally found a strange issue in VS2010 with next code:

void Test1()
{
    std::vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.insert(vec.end(), vec[0]);
    // GCC: vec == [10, 20, 10];
    // VS2005: vec == [10, 20, 10];
    // VS2010: vec == [10, 20, -17891602];
}

It seems that vector reallocates memory and deletes the old one before reading a new value, that leads to copying of corrupted value. This issue is present in VS2010. Checked in VS2005 and GCC - OK.

Is it valid to pass to insert() a reference taken from operator[] or front()/back() methods?

UPD: Having done some investigations based on comments below, I came to a conclusion that using reserve() is not a good idea because of performance. It leads to unwanted big number of reallocations.

void Test2()
{
    std::vector<int> vec, vec2;
    const int count = 10000;
    int prevCap = 0, reallocCount = 0;
    int prevCap2 = 0, reallocCount2 = 0;
    for (int i = 0; i < count; ++i)
    {
        if (vec.size() >= vec.capacity())
        {
            vec.reserve(vec.size()+1);
        }
        vec.insert(vec.end(), i);
        vec2.insert(vec2.end(), i);
        const int cap = vec.capacity();
        const int cap2 = vec2.capacity();
        if (prevCap != cap) ++reallocCount;
        prevCap = cap;
        if (prevCap2 != cap2) ++reallocCount2;
        prevCap2 = cap2;
    }
    cout << reallocCount << " " << reallocCount2 << endl;
    // reallocCount == 10000, reallocCount2 == 15 GCC
}

So for now I have only two options:

1) use temporary variable

const int tempValue = vec[0];
vec.insert(vec.end(), tempValue);

But I'm not sure if tempValue can be removed by a compiler by some optimizations.

2) use push_back(0) and further pop_back() calls

vec.push_back(0);
vec.pop_back();
vec.insert(vec.end(), vec[0]);

This approach seems better, it gives an expected result and performance in VS2005/2010 and GCC.

Did I miss something? Is there a better solution?

Upvotes: 3

Views: 134

Answers (2)

simonc
simonc

Reputation: 42165

The docs for insert say (my emphasis)

The vector is extended by inserting new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted.

This causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.

Since the second argument to insert is a reference and reallocation may require a relocation of your heap cell, this suggests that your code is only safe if you know that reallocation cannot happen. i.e. when vec.capacity() > vec.size()

As noted by Agnew and quetzalcoatl, there are a couple of ways you could fix your code

You could copy your new value to a temporary to ensure a reference to it remains valid

int val = vec[0];
vec.insert(vec.end(), val);

...or you could increase the capacity of your vector before calling insert

if (vec.capacity == vec.size()) {
    vec.reserve(vec.size()+1);
}
vec.insert(vec.end(), val);

Upvotes: 3

Balog Pal
Balog Pal

Reputation: 17163

insert takes second argument by reference. op[] provides reference also. Calling insert invalidates references, so you have undefined behavior, anything can happen.

Upvotes: 4

Related Questions