7

次のC++STLプログラムでは、ファンクターNthを定義し、n回目に取り消されるとtrueを返します。それを汎用アルゴリズムremove_ifに変換すると、何か奇妙なことが起こります。

コード：

#include <iostream>
#include <list>
#include <algorithm>
#include "print.hpp"

using namespace std;

class Nth{
private:
    int nth,ncount;
public:
    Nth(int n):nth(n),ncount(0){}

    bool operator()(int)
    {
        return ++ncount == nth;
    }
};

int main()
{
    list<int> col;
    for (int i = 1;i <=9 ;++i)
    {
        col.push_back(i);
    }

    PRINT_ELEMENTS(col,"col : ");

    list<int>::iterator pos;
    pos = remove_if(col.begin(),col.end(),
        Nth(3));

    col.erase(pos,col.end());

    PRINT_ELEMENTS(col,"nth removed : ");
}

print.hpp：

#include <iostream>

template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;

    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

Microsoft Visual Studio 2008で実行すると、次の結果が得 ここに画像の説明を入力してください られます。必要のない要素3と6が削除されます。3つだけが削除されると思いました。誰かが私のために解釈してもらえますか？どうもありがとう。

4

3 に答える 3

11

C ++標準ライブラリから：ニコライM.ジョスティスによるチュートリアルとリファレンス

これは、アルゴリズムの通常の実装がアルゴリズム中に述語を内部的にコピーするために発生します。

template <class ForwIter, class Predicate>
   ForwIter std::remove_if(ForwIter beg, ForwIter end,
                           Predicate op)
   {
       beg = find_if(beg, end, op);
       if (beg == end) {
           return beg;
       }
       else {
       ForwIter next = beg;
           return remove_copy_if(++next, end, beg, op);
       }
   }

アルゴリズムはfind_if（）を使用して、削除する必要のある最初の要素を検索します。ただし、渡された述語opのコピーを使用して、残りの要素がある場合はそれを処理します。ここでは、元の状態のNthが再び使用され、残りの要素の3番目の要素（実際には6番目の要素）も削除されます。

この動作はバグではありません。この標準では、アルゴリズムによって述語が内部的にコピーされる頻度は指定されていません。したがって、C ++標準ライブラリの保証された動作を取得するには、その動作がコピーまたは呼び出される頻度に依存する関数オブジェクトを渡さないでください。したがって、2つの引数に対して単項述語を呼び出し、両方の引数が等しい場合、述語は常に同じ結果を生成する必要があります。つまり、述語は呼び出しによってその状態を変更してはならず、述語のコピーは元の状態と同じである必要があります。関数呼び出しのために述部の状態を変更できないようにするには、演算子（）を定数メンバー関数として宣言する必要があります。

于 2012-04-22T12:44:50.797 に答える
5

std::remove_ifには使用しないでくださいstd::list。代わりに、リストのメンバー関数を使用してください。

col.remove_if(Nth(3));

一般的なアルゴリズムは、要素の値を再配置して、最後から安全に消去できるようにしますが、リストの場合、メンバーアルゴリズムは、他の要素に触れることなく、不要なノードを直接削除します。

アップデート。指摘されたように、述語が内部の値による状態を持つことは許可されていないため、これが実際に問題を解決することは保証されません。代わりにこれを試してください：

struct Nth
{
    const int n;
    int & counter;
    Nth(int N, int & c) : n(N), counter(c) { }
    bool operator()(int) const { return ++counter == N; }
};

{
    int counter = 0;
    cols.remove_if(Nth(3, counter));
}

この新しい述語はコピー可能であり、（外部の）カウンター変数の参照ラッパーとして機能します。

于 2012-04-22T12:42:06.900 に答える
0

《標準C ++ライブラリ》を読んで、別の解決策を見つけました。それは、関数remove_ifを再実装することです。

template <class ForwIter,class Predicate>
ForwIter remove_if_re(ForwIter begin,ForwIter end,Predicate op)
{
    while(begin != end && !op(*begin))
        ++begin;
    if(begin == end)
        return begin;
    else{
        ForwIter next = begin;
        return remove_copy_if(++next,end,begin,op);
    }
}

それは機能します。

しかし、私は少し興味があります。この実装は、渡された述語opのコピーを使用して残りの要素を処理しませんか？

私はSTLを学ぶのは初めてです。あなたの患者の答えに感謝します。

どうもありがとう。

于 2012-04-22T13:17:13.203 に答える