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

を使用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;
    }
}

intsのような単純なアイテムを扱っている限り、これは良いアプローチです。

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

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 に答える
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);
    }
}

実装に関する問題の1つは、最後以外のinsert場所で再割り当てが発生する可能性があり、挿入された位置以降は無効になる可能性があることです。したがって、定義上、最初に挿入しているので無効になります。it

2番目の問題は、cout<<v[i];実際にはである必要があるということcout<<i;です。

逆イテレータを使用し、すべてを移動する、より優れた実装x。これは、それが進むにつれて消去し、を保持し、完了したら挿入を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 に答える
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 に答える