CODEWITHSUNDEEP
c++stlstdvector
aminfar
aminfar

Reputation: 2365

STL vector: Moving all elements of a vector

I have two STL vectors A and B and I'd like to clear all elements of A and move all elements of B to A and then clear out B. Simply put, I want to do this:

std::vector<MyClass> A;
std::vector<MyClass> B;
....
A = B;
B.clear();

Since B could be pretty long, it takes k*O(N) to do this operation, where k is a constant, and N is max(size_of(A), size_of(B)). I was wondering if there could be a more efficient way to do so. One thing that I could think of is to define A and B as pointers and then copy pointers in constant time and clear out B.

Upvotes: 71

Views: 117266

Answers (8)

redfeatherplusplus
redfeatherplusplus

Reputation: 123

I lack rep to comment, but I want to mention that per: https://en.cppreference.com/w/cpp/container/vector/operator%3D void.pointer is right. In particular...

2) Move assignment operator. Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.

Thus Praetorian's answer is wrong per standard. However, for MSVC at least, is good enough because the implementation clears the list anyway (Probably true for most).

Something interesting is that since we declare a move constructor, no implicit move assignment operator will be declared. Thus we "know" that std::vector must declare a move assignment operator.

Upvotes: 2

Sameer Ahuja
Sameer Ahuja

Reputation: 71

std::move works fine. Here is the sample code for the same

    vector<int> v1 = {1,2,3,10,20,30,100,200,300,999};
    vector<int> v2;

    cout << "Size of v1 before move = " << v1.size() << endl;
    cout << "Capacity of v1 before move = " << v1.capacity() << endl;

    v2 = std::move(v1);

    cout << "Size of v2 after move = " << v2.size() << endl;
    cout << "Capacity of v2 after move = " << v2.capacity() << endl;

    cout << "Size of v1 after move = " << v1.size() << endl;
    cout << "Capacity of v1 after move = " << v1.capacity() << endl;

-----------Output-------------------------
Size of v1 before move = 10
Capacity of v1 before move = 10
Size of v2 after move = 10
Capacity of v2 after move = 10
Size of v1 after move = 0
Capacity of v1 after move = 0

Upvotes: 6

metal
metal

Reputation: 6332

If you can't std::move or std::swap the vectors (e.g., because A and B are related but different types, perhaps differing only by const), you can do:

std::vector<MyClass>       A;
std::vector<const MyClass> B;
// ...
for( auto& a : A )
{
    B.emplace_back( std::move( a ) );
}

Note that this leaves A with the same number of elements, but they are all in an indeterminate state (i.e., they can be assigned to or destructed, but not read).

Upvotes: 2

mfontanini
mfontanini

Reputation: 21910

Using C++11, it's as simple as:

A = std::move(B);

Now A contains the elements that were previously held by B, and B is now empty. This avoids copying: the internal representation is simply moved from B to A, so this is an O(1) solution.

As for C++03, as Prætorian states, you could swap the vectors. There is a specialization of the std::swap function, which takes std::vectors as its arguments. This effectively swaps the internal representation, so you end up avoiding creating copies of the elements held by them. This function works in O(1) complexity as well.

Upvotes: 139

mogulkahn
mogulkahn

Reputation: 79

just call clear on vector will take o(1) time, since clear will do nothing, If you really want to clear B after assign it to A, you could do the following

A.swap(B);
{
    std::Vector<..> C;
    c.swap(B);
}

Upvotes: 4

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208446

I have two STL vectors A and B and I'd like to clear all elements of A and move all elements of B to A and then clear out B.

This can be done with a combination of swap. First swap A and B for the first half. Then swap an empty std::vector<> with B or call clear(). The difference is that clear() will not release the memory, but only destroy the objects:

std::vector<int> a, b; // initialize them somehow
swap(a,b);

// clear b without releasing the memory:
std::size_t capacity = b.capacity();
b.clear();
assert(b.capacity()==capacity);

// or release the memory
std::vector<int>().swap(b);
assert(b.capacity()==0);

Upvotes: 5

Jason
Jason

Reputation: 1632

The swap function does this.

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

int main(int argc, char* argv)
{
  std::vector<int> A;
  std::vector<int> B;

  for (int i = 0; i < 10; ++i)
  {
     B.push_back(i);
  }

  std::cout << "Before swap\n";
  std::cout << "A:";
  std::copy(A.begin(), A.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\nB:";
  std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";

  A.swap(B);
  B.clear();

  std::cout << "After swap\n";
  std::cout << "A:";
  std::copy(A.begin(), A.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\nB:";
  std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";
}

The output

Before swap
A:
B:0 1 2 3 4 5 6 7 8 9 
After swap
A:0 1 2 3 4 5 6 7 8 9 
B:

Upvotes: 2

Praetorian
Praetorian

Reputation: 109249

If you have a C++11 compiler you can move B into A.

A = std::move(B);

If you're working with an older compiler, just swap the two

A.swap(B);

In both cases, the only O(N) operation will be clearing the contents of A. In the first case the clearing will be done during the assignment itself, while in the second it will happen when B goes out of scope (since the contents were swapped).

Upvotes: 21

Related Questions