Appending Std::Vector to Itself, Undefined Behavior

Appending std::vector to itself, undefined behavior?

According to the C++03 ISO spec (§23.1.1, Table 67) (and as @AndyProwl has mentioned, in §23.2.3, table 11 of the C++11 ISO spec), as part of sequence requirements, the operation a.insert(p, i, j) in a sequence container has this precondition:

i, j are not iterators into a.

In other words, sequence containers are allowed to safely assume that if you do a range insertion operation, that range will not be defined from iterators over that original container.

As a result, if you try to insert a container's elements into itself, you are calling a standard library function and breaking a precondition. This results in undefined behavior, meaning that it might work on some platforms if the library implementers are nice people, but it could terribly and catastrophically fail with no justification.

Hope this helps!

Nice way to append a vector to itself

Wow. So many answers that are close, none with all the right pieces. You need both resize (or reserve) and copy_n, along with remembering the original size.

auto old_count = xx.size();
xx.resize(2 * old_count);
std::copy_n(xx.begin(), old_count, xx.begin() + old_count);

or

auto old_count = xx.size();
xx.reserve(2 * old_count);
std::copy_n(xx.begin(), old_count, std::back_inserter(xx));

When using reserve, copy_n is required because the end() iterator points one element past the end... which means it also is not "before the insertion point" of the first insertion, and becomes invalid.

---

23.3.6.5 [vector.modifiers] promises that for insert and push_back:

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. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

Can I insert a vector to itself with std::vector::insert?

Regardless of whether perform reserve in advance or not, the behavior is undefined. For std::vector::insert:

inserts elements from range [first, last) before pos.

The behavior is undefined if first and last are iterators into *this.

Wrong results when appending vector to itself using copy and back_inserter

std::back_inserter creates an inserting iterator that inserts elements into a container. Each time this iterator is dereferenced, it calls push_back on the container to append a new element to the container.

For a std::vector container, a call to push_back where v.size() == v.capacity() will result in a reallocation: a new array is created to store the contents of the vector, its current contents are copied into the new array, and the old array is destroyed. Any iterators into the vector at this time are invalidated, meaning they can no longer be used.

In your program, this includes the input range defined by begin(vec) and end(vec) from which the copy algorithm is copying. The algorithm continues to use these iterators, even though they are invalidated, thus your program exhibits undefined behavior.

---

Even if your container had sufficient capacity, its behavior would still be undefined: the specification states that, upon insertion, "if no reallocation happens, all the iterators and references before the insertion point remain valid" (C++11 §23.3.6.5/1).

The call to push_back is equivalent to insertion at the end, so the end iterator (std::end(vec)) that you passed into std::copy is invalidated after a single call to push_back. If the input range is nonempty, the program therefore exhibits undefined behavior.

---

Note that the behavior of your program would be well-defined if you used a std::deque<int> or a std::list<int>, because neither of those containers invalidates iterators when elements are appended.

Under-the-hood STL: Concatenating an std::vector to itself without new vector

You will copy items indefinitely. Note how many to copy up front:

size_t n = aVec.size();
for (int k = 0; k != n; ++k)
  aVec.push_back(aVec[k]);

While many C++ algorithms are better expressed using begin() and end() iterators, in this case your access via index is superior, because modifying the container might invalidate the iterators, but the element access will remain valid. You can, however, use reserve to avoid that invalidation:

aVec.reserve(2*aVec.size());
std::copy(aVec.begin(), aVec.end(), std::back_inserter(aVec));

Error while concatenating a vector to itself in c++

In your original program push_back invalidates the iterators and using those invalidated iterators can lead to undefined behavior.

One way to solve this would be to use std::copy_n with std::vector::resize as shown below:

 vector<int> getConcatenation(vector<int>& nums) {
        
       std::vector<int>::size_type old_Size = nums.size();
       nums.resize(2 * old_Size);
       std::copy_n(nums.begin(), old_Size, nums.begin() + old_Size);
        
        return nums; //NO NEED for this return since the function took vector by reference and so the change is already reflected on passed vector     
    }

Also you would need to add #include <algorithm> for std::copy_n.

Note that since your function takes the vector be reference, there is no need to return nums because the changes you do on nums is already reflected on the original vector. So you can use void as the return type of the function and then remove the return statement.

add at beginning and end of vector

First, if the container is going to be large then consider using deque instead of vector. It's more efficient for adding at the start.

For vector you can't insert elements out of the vector to the start because the first thing that happens is everything in the vector gets moved (and all iterators and references to those elements are invalidated). So you either need to copy the elements out of the vector or you need to put insert elements at the start and then copy-assign to them. Assuming the type is int, I'll go with the former:

if (v.size() >= 2) {
    int tmp[] = {*(v.end() - 2), *(v.end() - 1)};
    v.insert(v.begin(), tmp, tmp + 2);
    tmp[0] = v[2]; tmp[1] = v[3];
    v.insert(v.end(), tmp, tmp + 2);
}

Alternatively, this uses more memory but might be easier to read. As a bonus it gives the strong exception guarantee even with types whose copy constructor can throw. My code above can be made to offer the strong guarantee by adding a call to reserve, but only because int is a trivial type:

if (v.size() >= 2) {
    std::vector<int> new_v;
    new_v.reserve(v.size() + 4);
    new_v.insert(new_v.end(), v.end() - 2, v.end());
    new_v.insert(new_v.end(), v.begin(), v.end());
    new_v.insert(new_v.end(), v.begin(), v.begin() + 2);
    v.swap(new_v);
}

For deque you don't need to store any elements outside the container provided you use a reference instead of an iterator to access them. Again this only offers the basic exception guarantee.

if (v.size() >= 2) {
    v.push_front(v.back());
    v.push_front(*&(v.end() - 1));
    v.push_back(*&(v.begin() + 2));
    v.push_back(*&(v.begin() + 3));
}

Why is appending std::deque object to itself through std::copy successful if the deque is not large enough?

Page 455/456 of the book introduces std::back_inserter, while page 457/458 introduces std::front_insert. There is a short explanation in each case, including a list of applicable container. Each section has a code snippet as example, with only one of the applicable containers chosen to exemplify the usage.

For std::back_inserter, as container std::vector is chosen and a comment in the code snippets mentions, why it is necessary to first reserve enough space in the vector.

For std::front_inserter the author chose std::list, not std::deque. std::list does not invalidate references or iterators on insert, therefore

copy(coll.begin(), coll.end(), front_inserter(coll));

is fine, see [list.modifiers]/1 of the current C++ draft.

There is therefore in both cases no error in the author's code. I suppose he did never intend to fully explain the dangers of copying into a container itself, but simply chose these cases, because it allowed him to write shorter complete usage examples.

I think for the case where coll is a std::deque this is clearly undefined behavior. std::front_inserter inserts elements by calls to push_front (see [front.insert.iter.ops]/2), which invalidates all iterators (see [deque.modifiers]/1):

At the same time std::copys behavior is [alg.copy]/4:

Effects: Copies elements in the range [first, last) into the range
[result, result + N) starting from first and proceeding to last. For
each non-negative integer n <
N, performs *(result + n) = *(first + n).

After the first insert, first is invalidated and undefined behavior will be caused.

---

Related Topics