Stl Vector: Moving All Elements of a Vector

STL vector: Moving all elements of a vector

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.

STL vector: Moving all elements of a vector

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.

Moving elements from std::vector to another one

The std::move lets you move the objects, as opposed to copying them, allowing for a potentially faster execution speed. The savings may be even greater when you move a range of values. However, when you do move a range from a container, the container still holds the places that were once occupied by these values.

You need to resize the container manually to remove these placeholders if you want to get rid of them (you don't have to, in case you would prefer reusing these container spots for other elements). One way to do it is to call vector::erase on the same range that you moved out of the container.

How to Move certain elements of std::vector to a new index within the vector?

The above two examples had issues with different input (noted above). I worked out the algorithm to handle the different cases and it passed my unit tests. It can probably be improved for speed.

template <class CONTAINER_TYPE>
void ChangeRecordOrder( CONTAINER_TYPE IN OUT &values,
                        uint newIndex,
                        std::vector<uint> IN const &indexesToMove )
   {
   // Make a copy of the indexesToMove as we need to do fixups to them in certain cases    
   std::vector<uint> temporaryIndexes = indexesToMove;

   for ( uint i=0; i<temporaryIndexes.size(); i++ )
      {
      uint indexToMove = temporaryIndexes[i];

      if ( indexToMove < newIndex )
         {
         uint leftIndex  = indexToMove;
         uint rightIndex = newIndex -1;
         uint newFirst   = leftIndex + 1;
         std::rotate( values.begin() + leftIndex, values.begin() + newFirst,  values.begin() + rightIndex +1);

         // fix up indexes
         for( uint j=i+1; j<temporaryIndexes.size(); j++ )
            {
            uint &futureIndex = temporaryIndexes[j];
            if ( futureIndex > leftIndex && futureIndex <=rightIndex )
               --futureIndex;
            }
         }
      else if ( indexToMove > newIndex )
         {
         uint leftIndex  = newIndex;
         uint rightIndex = indexToMove;
         uint newFirst   = indexToMove;
         std::rotate( values.begin() + leftIndex, values.begin() + newFirst,  values.begin() + rightIndex +1);

         // fix up indexes
         for( uint j=i+1; j<temporaryIndexes.size(); j++ )
            {
            uint &futureIndex = temporaryIndexes[j];
            if ( futureIndex > leftIndex && futureIndex <=rightIndex )
               ++futureIndex;
            }

         ++newIndex;
         }

      }
   }

Is there a better way of moving elements in a vector

You could use std::rotate:

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

int main()
{
    std::vector<int> values{1, 2, 3, 4, 5};
    std::rotate(values.begin()+2, values.end()-1, values.end());
    for(int i: values)
        std::cout << i << " ";
    std::cout << "\n";
}

try it

Outputs:
1 2 5 3 4

You can probably adjust the iterators used if you need to move an element that isn't at the end.

Moving a vector element to the back of the vector

You can do this with std::rotate from the standard library. Since this doesn't change the vector size it also won't trigger a reallocation. Your function would look something like this:

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
    auto it = v.begin() + itemIndex;
    std::rotate(it, it + 1, v.end());
}

Moving an item in a vector

I believe you can use std::rotate to this end.

vector<T> vec = ...
vector<T>::iterator from = ...
vector<T>::iterator to = ...
if(from < to ) {
    rotate(from, from+1, to+1);
} else if (from > to) {
    rotate(to, from, from+1);
}

Disclaimer: untested code

By the way, you can get the vector index from iterator easily with eg,

vector<T> vec = ...
vector<T>::iterator it = ...
size_t idx = it - vec.begin();

---

Related Topics