C++最容易矢量

Question

對不起，我的潛力nOOb'ness但在一個單一的元素移動到新位置，最有效的方法一直試圖讓這個幾個小時，不能似乎找到C++ 98

一個優雅的解決方案

我的問題是，假設我有一個字符串{a，b，c，d，e，f}的向量，並且我想將'e'移動到第二個元素，我該怎麼做呢？很顯然，預期的輸出結果現在可以打印出來{0128}，但是我們希望能夠聽到一些關於如何處理這些問題的建議做到這一點。

謝謝。

Answer 1

編輯正如評論，下面的代碼實際上模仿std::rotate，這當然是上面在任何情況下我的手挽碼首選的注意。

---

你可以用K交換完成這個w這裏K是元件之間的距離：

#include <iostream> 
#include <string> 

using namespace std; 

int main() 
{ 
    string v = "abcdef"; // use string here so output is trivial 

    string::size_type insert_index = 1; // at the location of 'b' 
    string::size_type move_index = 4; // at the location of 'e' 

    while(move_index > insert_index) 
    { 
    std::swap(v[move_index], v[move_index-1]); 
    --move_index; 
    } 
    std::cout << v; 
} 

Live demo here。注意我使用std::string，但算法對於std::vector保持不變。 The same can be done with iterators，所以你可以推廣到沒有operator[]的容器。

Answer 2

由於std::vector<>存儲在連續的內存中，因此您必須將舊位置和新位置之間的所有內容都移動一個元素，因此不可能通過std::vector<>「高效」執行此操作。所以它是矢量長度的線性時間（或至少移動的距離）。

天真的解決方案是insert()，然後erase()，但是這需要將您修改的最右邊位置後的所有內容移動兩次！因此，您可以「手動」，將b通過d一個位置複製到右邊（例如用std::copy()，然後覆蓋b。至少可以避免在修改範圍之外移動任何東西。讓std::rotate()做到這一點，因爲@WhozCraig在評論中提及。

Answer 3

我會用std::rotate第一次嘗試，只有嘗試其他手動東西（或比其他載體的容器），如果證明是不夠高效：

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

int main() 
{ 
    // move 5 from 4th to 1st index 

    std::vector<int> v {1,2,3,4,5,6}; 
    // position:  0 1 2 3 4 5 

    std::size_t i_old = 4; 
    std::size_t i_new = 1; 
    auto it = v.begin(); 

    std::rotate(it + i_new, it + i_old, it + i_old + 1); 
    for (int i : v) std::cout << i << ' '; 
} 

Live demo。