CODEWITHSUNDEEP
c++algorithmvectorstlcopy
RussianStranger
RussianStranger

Reputation: 55

std::copy for vector doesn't work properly

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> a{ 1, 2, 3 };
    copy(a.begin(), a.end(), back_inserter(a));
    for (const int& x : a)
        cout << x << ' ';
}

Output:

1 2 3 1 -572662307 -572662307

Expected output:

1 2 3 1 2 3

I have no idea why is this happening. What's is the reason for this behavior?

Upvotes: 5

Views: 598

Answers (3)

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 30005

The problem is that as the vector grows, iterators you provided are potentially invalidated. You can fix that by using reserve. It is, in general, a good idea to use reserve if you know the size in advance so there are fewer allocations going on:

#include <algorithm>
#include <vector>

int main() {
  std::vector<int> a{1, 2, 3};
  a.reserve(a.size() * 2);

  a.insert(a.end(), a.begin(), a.end());
}

Do note that insert is often better and simpler than back_inserter.

Upvotes: 7

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 123439

Possible implementation of copy from cppreference:

template<class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, 
              OutputIt d_first)
{
    while (first != last) {
        *d_first++ = *first++;
    }
    return d_first;
}

With a back_inserter *first++ will call push_back on the vector. Calling push_back potentially invalidates all iterators when the vector needs to reallocate. Hence your code has undefined behavior.

Note that back_inserter is a little exotic. It violates the usual strict separation of iterators and container, because the iterator has to store a reference to the container. That alone does not explain the effect you see, but it is indication that one needs to be careful when the iterator actually does modify the container.

Upvotes: 5

Vlad from Moscow
Vlad from Moscow

Reputation: 311136

In general your program has undefined behavior because the iterators can become invalid during adding new elements to the vector.

You have to reserve enough memory in the vector. For example

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v = { 1, 2, 3 };

    v.reserve( 2 * v.size() );
    
    std::copy( std::begin( v ), std::end( v ), std::back_inserter( v ) );
    
    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';
    
    return 0;
}

If your compiler supports the C++ 17 Standard (in the C++ 14 Standard there is a requirement that the iterators that specify the copied range were not iterators of the vector itself) then you may use the method insert, For example

#include <iostream>
#include <vector>
#include <iterator>

int main() 
{
    std::vector<int> v = { 1, 2, 3 };

    v.insert( std::end( v ), std::begin( v ), std::end( v ) );

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';
    
    return 0;
}

Upvotes: 6

Related Questions