2

I have an STL vector that stores the diagonals of a matrix. A certain mathematical rule I'm implementing tells me that I can produce a new matrix of a tensor product's diagonals simply by taking the original vector and concatenating a copy of that vector onto itself (it doubles in size, and the values repeat after 1/2 * size() ).

I wrote the following code:

std::vector<int> aVec;

for (int k = 0; k < aVec.size(); k++) aVec.insert(aVec.end(), aVec[k]);

But I get seg-faults when I try this. If I create a copy of aVec and use that as the insert "value", as well as using it for the size() in the loop args, it will work, but I must do both of these things (otherwise I will still get seg-faults).

Can anyone explain what's going on underneath that makes this implementation not work?

hadsed
  • 327
  • 2
  • 4
  • 11
  • There's a nice [insert method](http://stackoverflow.com/a/201729/962089) of concatenating two vectors. – chris Jul 16 '12 at 19:29

3 Answers3

4

Use iterator-based operations:

vec.reserve(vec.size() * 2);
vec.insert(vec.end(), vec.begin(), vec.end());
Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • Are you sure you need to `reserve` before inserting? The complexity of `insert` must be `linear in the number of elements inserted plus the distance to the end of the vector`. If I understand correctly, this means that an implementation of `insert` is required to compute the distance between the two input iterators, and reserve enough capacity for the new number of elements, am I wrong? – Luc Touraille Jul 16 '12 at 20:21
  • 1
    @Luc But that invalidates the iterator range that you pass to it. – Konrad Rudolph Jul 16 '12 at 20:23
  • Hmm, right, I guess the requirement deals with amortized complexity then. Nevertheless, am I right in thinking that some implementations would specialize `insert` for random access iterators, in order to perform the reservation beforehand (even though the standard requires nothing of the sort)? – Luc Touraille Jul 16 '12 at 20:33
  • @Luc Almost definitely. I know that the stdlibc++ implementation does it for container *constructors*, it would be weird if `insert` behaved differently. And I expect other implementations of the standard library to also do this. – Konrad Rudolph Jul 16 '12 at 21:04
  • 2
    You should not not append this way, it is undefined behavior ([I made the same mistake](http://stackoverflow.com/q/14791984/237483)). – Christian Ammer Feb 28 '13 at 13:44
3

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));
MvG
  • 57,380
  • 22
  • 148
  • 276
  • This may work in some implementations, but it is still undefined behavior. – Ben Voigt Oct 18 '14 at 19:50
  • @BenVoigt: Which of the two? The first I'd consider well within the specs. The latter is not perfectly within the specs: “Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. 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()`.” But `end()` is not an iterator referring to an element, so it might *in theory* get invalidated. I can think of no way to implement vector so that it gets invalidated. – MvG Oct 18 '14 at 21:10
  • Reallocation isn't the only operation that causes invalidation. Any insertion or deletion invalidates handles (iterators/pointers/references) at or after the insertion/deletion point. Handles before the insertion/deletion point are ok, but `end()` is not before the insertion point. – Ben Voigt Oct 18 '14 at 22:02
1

You should read the value of aVec.size() once before you start adding elements to aVec.

Nordic Mainframe
  • 28,058
  • 10
  • 66
  • 83