向量中的移動元素未按預期工作

Question

我試圖將每個具有x值的元素移動到向量的開頭，以便所有具有x值的元素都位於向量的前面，但它是不工作，所以你能告訴我我做錯了嗎？

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

using namespace std; 

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    typename Container::iterator it = find(c.begin(), c.end(), x); 
    if (it!=c.end()) { 
     c.insert(c.begin(), *it); 
     remove (it, c.end(), x); 
    } 
} 
int main() 
{ 
    int x=1; 
    vector <int> v{1,2,4,6,7,1,3,1,1,8,9}; 

    move_x(v, x); 
    for(auto i:v) 
     cout<<v[i]; 

    return 0; 
} 

和我得到這個輸出，當我運行它

411613848811 

Answer 1

一旦插入容器，迭代器不再有效

c.insert(c.begin(), *it); // This invalidates 'it'  
    remove (it, c.end(), x); // oops! trying to use invalid iterator 

使用std::rotate提供了更好的選擇，這不會使迭代器無效：

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    typedef typename Container::iterator It; 
    It write_it = c.begin(), read_it = c.begin(); 
    for (;;) { 
     It found_it = find(read_it, c.end(), x); 
     if (found_it==c.end()) break; 
     read_it = found_it; 
     ++read_it; 
     std::rotate(write_it,found_it,read_it); 
     ++write_it; 
    } 
} 

只要你是在處理簡單的項目，如整型，這是一個好辦法：

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    typename Container::reverse_iterator it = std::remove(c.rbegin(),c.rend(),x); 

    for (;it!=c.rend();++it) { 
     *it = x; 
    } 
} 

Answer 2

這是一個固定的實現，你在你的代碼有什麼：

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    typename Container::iterator it = find(c.begin(), c.end(), x); 
    if (it!=c.end()) { 
     c.erase(it); 
     c.insert(c.end(), x); 
    } 
} 

一與您的實施問題是，insert任何地方but the end可以導致重新分配，並且不管將插入的位置後的任何東西無效。所以根據定義，因爲您在開頭插入it將無效。

第二個問題是cout<<v[i];它實際上應該是cout<<i;。

一個更好的實現，它使用反向迭代器並移動所有的x s。這個消失，並保持count，然後在完成時插入count。使用erase with reverse iterators有點棘手：

template <typename Container, typename Arg> 
void move_all_x(Container& c, Arg x) 
{ 
    unsigned int count = 0 ; 

    for(typename Container::reverse_iterator it = c.rbegin() ; it != c.rend();) 
    { 
     if(*it == x) 
     { 
     c.erase(--(it++).base()) ; 
     ++count ; 
     } 
     else 
     { 
      ++it ; 
     } 
    } 

    for(unsigned int i = 0; i < count; ++i) 
     { 
     c.insert(c.begin(), x) ; 
     } 
} 

Answer 3

輸出錯誤。應該有for (auto i:v) cout << i;而不是v[i]。你會看到一個正確的算法太垃圾

Answer 4

你需要一個循環來處理所有匹配（或使用計數和插入）。 v定義爲list<int>：

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    for (auto it = find(c.begin(), c.end(), x); 
     it != c.end(); 
     it = find(it, c.end(), x)) { 
    c.insert(c.begin(), x); 
    it = c.erase(it); 
    } 
} 

Answer 5

你可以使用std ::分區，將移動中滿足給定謂詞的範圍的開始範圍內的所有元素，並返回一個迭代器，其沒有按第一要素不符合謂詞。

template <typename Container, typename Arg> 
void move_x(Container& c, Arg x) 
{ 
    typename Container::iterator endrange = 
     std::partition(c.begin(), c.end(), [&x](Arg ele){ return ele == x; }); 
} 

在這種情況下，我們沒有使用返回值，但我認爲它可能會有用。