如何將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); 
} 

可讀性公然不太好。它可能可以通過更好的變量名稱和/或將其放入單獨的函數中來改進