3

sのベクトルから重複する値を削除したいとしますint。通常の解決策は、ベクトルをソートし、erase-removeイディオムを使用して重複を消去することです。ただし、削除されない要素の順序を維持する必要があるため、並べ替えることはできません。したがって、次のような述語を考え出し、remove_ifアルゴリズムで使用することができます。

struct comp {
    std::set<int> s;
    comp() : s() {}
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};

setただし、メンバーのコピーが2つ取得されるため、何らかの理由で述語オブジェクトがコピーされると、これは機能しなくなります。そして確かに、gccの実装remove_ifはまさにそれを行います：

template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    remove_if(_ForwardIterator __first, _ForwardIterator __last,
          _Predicate __pred)
    {

      __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);

      if(__first == __last)                             // ^^^^^ here a copy is made
        return __first;
      _ForwardIterator __result = __first;
      ++__first;
      for(; __first != __last; ++__first)
        if(!bool(__pred(*__first)))
          {
            *__result = _GLIBCXX_MOVE(*__first);
            ++__result;
          }
      return __result;
    }

回避策はset、ファンクターのメンバーを静的にすることです。

struct comp {
    static set<int> s;
    comp() { s. clear(); }
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};
set<int> comp::s;

しかし、疑問は残ります：

述語ファンクターの可能なコピーがロジックを壊さないことを確認する必要がありますか？ この問題に関して特定の動作を義務付ける（または禁止する）規格には何かありますか？それとも、実装のバグですか？

4

3 に答える 3

5

はい、標準では、述語がコピーされる回数も指定されていません。また、述語がコンテナの要素に適用される順序も指定されていません。基本的に、述語は純粋関数のように機能する必要があります。観察可能な状態があってはなりません。1

したがってremove_if、ここでは適切なアルゴリズムのようには聞こえません。ファンクターの外部に保存するなどのハックでsetは、問題は解決しません。未定義の動作を引き続き呼び出すことになります。

1.より詳細な説明については、Scott MeyersのEffectiveSTLの項目39（「述語を純粋関数にする」）を参照してください。

于 2012-06-17T13:34:38.150 に答える
3

述語ファンクターの可能なコピーがロジックを壊さないことを確認する必要がありますか？

はい、述語がコピーされていると想定する必要があります。C ++ 11では、 std::refまたはstd::crefの使用を検討できます。

別の方法は、参照によって取得するようにcomp構造を変更することです。set

struct comp {
    std::set<int>& s;
    comp(std::set<int> s) : s(s) {}
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};

注：これが機能するかどうかについては何も述べてremove_ifいません。コピーしてはならない状態を含む、コピーされた述語の問題に対処しているだけです。

編集コメントで指摘されているように、アプローチは根本的に壊れています。述語呼び出しの結果は、可変状態に依存するべきではありません。

于 2012-06-17T13:25:27.410 に答える
2

はい、引数を不確定な回数コピーすることが許可されています。メンバーセットを静的にするよりも優れたアプローチは、ファンクターの外部でセットを作成し、それをコンストラクターパラメーターとして渡すことです。ポインタを内部に格納します。

于 2012-06-17T13:24:49.563 に答える