3

我正在尝试将每个具有 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
4

5 回答 5

2

插入容器后，迭代器不再有效

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

Usingstd::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;
    }
}
于 2013-03-11T00:36:43.623 回答
1

这是您在代码中的固定实现：

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

一个更好的实现，它使用反向迭代器并移动所有xs。这个会随着它的进行擦除并保留一个count，然后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) ;
      }
}
于 2013-03-11T00:44:43.437 回答
1

您可以使用 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; });
}

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

于 2013-03-11T02:11:33.167 回答
0

输出错误。应该for (auto i:v) cout << i;没有v[i]。你也会用正确的算法看到垃圾

于 2013-03-11T00:46:48.430 回答
0

您需要一个循环来处理所有匹配项（或使用计数和插入）。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);
  }
}
于 2013-03-11T00:58:41.223 回答