如何将std :: vector的某些元素移动到向量中的新索引？

Question

我正在移植一些我现在写的使用std库容器的旧手卷处理类。我无法移植的一种方法就是我称之为“ChangeRecordOrder”，因为缺少更好的术语。我需要一个标准的库替换。

它的定义是：

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

例如（伪码）：

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} 

注意，在2和4（20和40）中的元素，被转移到的索引6原始矢量（在60之前）。

当然我想这样做，而不是使用另一个临时向量。我也不介意IndexesToMove矢量在调用之前需要排序的要求。

我找不到这个std lib算法。我以前在原始内存中工作过的算法并没有使用C++移动语义。

谢谢！

Answer 1

以上两个示例在不同输入（上面提到的）中存在问题。我制定了算法来处理不同的情况，并通过了我的单元测试。它可能可以提高速度。

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 2

您正在寻找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; 
} 

这产生以下输出，根据ideone.com：

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

Answer 3

这里是一个解决方案，即移动每个非选择元件中的最多一次：

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

可读性公然不太好。它可能可以通过更好的变量名称和/或将其放入单独的函数中来改进