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

Question

I am porting some old hand rolled array processing classes I wrote to now use the std library containers. One method I am having trouble porting is what I call "ChangeRecordOrder" for lack of a better term. I need a standard library replacement.

Its definition is:

template <class T>
void ChangeRecordOrder( std::vector<T> IN OUT &inputVector, 
                        uint newInsertIndex, 
                        std::vector<uint> IN const &indexesToMoveToNewIndex );

For example (Pseudo code):

MyVector<uint> = {0,10,20,30,40,50,60,70,80,90}
IndexesToMove = {2,4}
NewIndex = 6

After call to ChangeRecordOrder( MyVector, NewIndex, IndexesToMove ):

MyVector<uint> == {0,10,30,50,20,40,60,70,80,90}

Note that the elements at 2 and 4 (20 and 40), were moved to index 6 of the original vector (in front of 60).

Of course I would like to do this in place, and not use another temporary vector. I also dont mind the requirement that the IndexesToMove vector needs to be sorted before calling.

I couldn't find an std lib algorithm for this. The algorithm that I had before worked on the raw memory and did not use c++ move semantics.

Thank you!

Answer 1

template <typename t> void move(std::vector<t>& v, size_t oldIndex, size_t newIndex)
{
    if (oldIndex > newIndex)
        std::rotate(v.rend() - oldIndex - 1, v.rend() - oldIndex, v.rend() - newIndex);
    else        
        std::rotate(v.begin() + oldIndex, v.begin() + oldIndex + 1, v.begin() + newIndex + 1);
}

test: https://coliru.stacked-crooked.com/a/5c31007000b9eeba

int main()
{
    std::vector<int> v{ 3, 4, 5, 6, 7, 8, 9  };  

    move(v, 1, 4);
    move(v, 4, 1);
    move(v, 3, 3);
}

output:

move 1 to 4:  3   [4]   5    6    7    8    9  
     result:  3    5    6    7   [4]   8    9  

move 4 to 1:  3    5    6    7   [4]   8    9  
     result:  3   [4]   5    6    7    8    9  

move 3 to 3:  3    4    5   [6]   7    8    9  
     result:  3    4    5   [6]   7    8    9  

Answer 2

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

      }
   }

Answer 3

Here is a solution, that moves each of the non-selected elements at most once:

#include <vector>
#include <algorithm>

using namespace std;
int main() {
    vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
    vector<size_t> IndexesToMove{2,4};
    size_t NewIndex = 6;
    //check that your indices are sorted, non-empty, in the correct range, etc.

    // move one element in front of the next element to move
    // then move those two elements in front of the next element to move
    // ...
    auto it_next = values.begin() + IndexesToMove.front();
    for(size_t i = 0; i < IndexesToMove.size() -1; i++) {
        auto it_first = it_next - i;
        it_next = values.begin() + IndexesToMove[i+1];
        rotate(it_first, it_first + i + 1 , it_next);
    }

    // move the collected elements at the target position
    rotate(it_next - IndexesToMove.size() + 1, it_next + 1, values.begin() + NewIndex);
}

Readability is admittedly not too good. It couldprobably be improved by better variable names and/or putting some of it into a separate function

Answer 4

You're looking for std::rotate.

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

int main() {
    std::vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
    std::vector<size_t> indexes_to_move{2,4};
    size_t destination_index = 6;
    if(destination_index > values.size()) throw std::runtime_error("Come on, bro.");

    for(auto const& val : values) std::cout << val << ',';
    std::cout << std::endl;

    for(size_t _index = 0; _index < indexes_to_move.size(); _index++) {
        size_t index = indexes_to_move[indexes_to_move.size() - _index - 1]; //We need to iterate in reverse.
        if(index >= values.size()) throw std::runtime_error("We dun goofed.");
        if(index >= destination_index) throw std::runtime_error("We goofed in a different way.");

        std::rotate(values.begin() + index, values.begin() + index + 1, values.begin() + destination_index);
        destination_index--;
    }

    for(auto const& val : values) std::cout << val << ',';
    std::cout << std::endl;
    return 0;
}

This yields the following output, according to ideone.com:

0,10,20,30,40,50,60,70,80,90,
0,10,30,50,20,40,60,70,80,90,