Nice Way to Append a Vector to Itself

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.

Append vector to itself?

Range-for is syntactic sugar for an iterator-based for-loop, and std::vector::push_back() can invalidate iterators like the ones being used internally by the range-for:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

You can use std::copy() after a resize():

vector<int> a;
a.push_back(2);
a.push_back(3);

auto size = a.size();
a.resize(size * 2);
std::copy(a.begin(), a.begin() + size, a.begin() + size);

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.

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!

Best way to append vector to vector

In my opinion, your first solution is the best way to go.

vector<>::insert is designed to add element so it's the most adequate solution.

You could call reserve on the destination vector to reserve some space, but unless you add a lot of vector together, it's likely that it wont provide much benefits: vector<>::insert know how many elements will be added, you will avoid only one reserve call.

Note: If those were vector of more complex type (ie a custom class, or even std::string), then using std::move could provide you with a nice performance boost, because it would avoid the copy-constructor. For a vector of int however, it won't give you any benefits.

Note 2: It's worth mentioning that using std::move will cause your source vector's content to be unusable.

C++ append one vector to another

If you're in the position to change scanDir, make it a (template) function accepting an output iterator:

template <class OutIt>
void scanDir(const std::string& dirname, OutIt it) {
  // ...
  // Scan subdir
  scanDir(subdir, it);
  // ...
}

You'll have the additional benefit to be able to fill all sort of data structures like

std::vector<string> vector;
scanDir(dir1, std::back_inserter(vector));
std::set<string> fileset
scanDir(dir1, std::inserter(fileset, fileset.begin()));

etc.

EDIT (see comment ...)

For using this function for class member initialization, you could either call it in the constructor as in

class MyClass {
private:
  std::vector<string> m_fileList;
public:
  MyClass(const std::string& dirname) {
    scanDir(dirname, std::back_inserter(m_fileList);
  }
}

or using a wrapper function

std::vector<string> scanDir(const std::string& dirname) {
  std::vector<string> result;
  scanDir(dirname, std::back_inserter(result);
  return result;
}

class MyClass {
// Same as above..
  MyClass(const std::string& dirname) : m_fileList(scanDir(dirname)) { }
}

I would prefer the first version for performance (and other) reasons ...

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));

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.

---

Related Topics