向量中的元素移动不如预期般有效。

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

- user1653150

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

只要您处理的是像 int 这样简单的项目，这就是一个不错的方法：

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

- Vaughn Cato

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（除了末尾）都可能导致重新分配，并且无论如何都会使插入位置之后的任何内容无效。因此，根据定义，由于您是在开头插入，it将无效。

第二个问题与cout<<v[i];有关，它实际上应该是cout<<i;。

更好的实现使用反向迭代器并移动所有x。该实现在进行遍历时进行删除并保持计数，然后在完成后执行count次插入。使用反向迭代器擦除有点棘手：

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

- Shafik Yaghmour

Answer 3

你可以使用std::partition，它会将满足给定谓词的范围内的所有元素移动到范围的开头，并返回一个指向第一个不满足谓词的元素的迭代器。

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

在这种情况下，我们没有使用返回值，但我认为它可能会有用。

- Muscles

---

整洁的解决方案，有两个问题，你没有捕获 x，并且在结尾放错了 ;。我修复了这两个问题后，看起来它可以正常工作了。 - Shafik Yaghmour

谢谢你指出这些问题。我原计划要通过编译器运行它，但被叫走了。现在似乎可以编译了。 - Muscles

Answer 4

输出结果是错误的。应该使用for (auto i:v) cout << i;而不是v[i]。即使使用正确的算法，您也会看到垃圾数据。

- Dmitry Galchinsky

Answer 5

你需要一个循环来处理所有匹配项（或使用计数和插入）。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);
  }
}

- perreal