How to insert a duplicate element into a vector?

问题:

I'm trying to insert a copy of an existing vector element to double it up. The following code worked in previous versions but fails in Visual Studio 2010.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
   vector<int> test;
   test.push_back(1);
   test.push_back(2);
   test.insert(test.begin(), test[0]);
   cout << test[0] << " " << test[1] << " " << test[2] << endl;
   return 0;
}

Output is -17891602 1 2, expected 1 1 2.

I've figured out why it's happening - the vector is being reallocated, and the reference becomes invalid before it's copied to the insertion point. The older Visual Studio apparently did things in a different order, thus proving that one possible outcome of undefined behavior is to work correctly and also proving that it's never something you should rely on.

I've come up with two different ways to fix this problem. One is to use reserve to make sure that no reallocation takes place:

   test.reserve(test.size() + 1);
   test.insert(test.begin(), test[0]);

The other is to make a copy from the reference so that there's no dependency on the reference remaining valid:

template<typename T>
T make_copy(const T & original)
{
    return original;
}

   test.insert(test.begin(), make_copy(test[0]));

Although both work, neither one feels like a natural solution. Is there something I'm missing?

回答1:

The issue is that vector::insert takes a reference to a value as the second parameter and not a value. You don't need the template to make a copy, just use a copy constructor to create another object, which will be pass by reference. This copy remains valid even if the vector is resized.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
   vector<int> test;
   test.push_back(1);
   test.push_back(2);
   test.insert(test.begin(), int(test[0]));
   cout << test[0] << " " << test[1] << " " << test[2] << endl;
   return 0;
}

回答2:

I believe this is defined behavior. In §23.2.3 of the 2011 C++ standard, table 100 lists sequence container requirements and there is an entry for this case. It gives the example expression

a.insert(p,t)

where a is a value of X which is a sequence container type containing elements of type T, p is a const iterator to a, and t is an lvalue or const rvalue of type X::value_type, i.e. T.

The assertion for this expression is:

Requires: T shall be CopyInsertable into X. For vector and deque, T shall also be CopyAssignable.
Effects: Inserts a copy of t before p.

The only relevant vector specific quote I could find is in §23.3.6.5 paragraph 1:

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Although this does mention the vector being reallocated, it doesn't make an exception to the previous requirements for insert on sequence containers.

As for working around this issue, I agree with @EdChum's suggestion of just making a copy of the element and inserting that copy.