`std :: set`の何が問題になっていますか？

StackOverflow https://stackoverflow.com/questions/5397616

質問

の 他のトピック 私は解決しようとしていました これ 問題。問題は、aから重複した文字を削除することでした std::string. 

std::string s= "saaangeetha";

注文が重要ではなかったので、私はソートしました s 最初に、次に使用します std::unique そして最終的にそれを取得するためにサイズを変更しました 望ましい結果: 

aeghnst

それは正しいです！

今、私は同じことをしたいのですが、同時にキャラクターの順序をそのままにしたいです。つまり、この出力が欲しい：

sangeth

だから私は書いた これ:

template<typename T>
struct is_repeated
{
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), is_repeated<char>()), s.end()); 
    std::cout << s ;
}

これはこの出力を与えます：

saangeth

あれは、 a 他の繰り返しはなくなりましたが、繰り返されます。コードの何が問題になっていますか？

とにかく私 私のコードを変更します 少し：（コメントを参照）

template<typename T>
struct is_repeated
{
    std::set<T> & unique;  //made reference!
    is_repeated(std::set<T> &s) : unique(s) {} //added line!
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::set<char> set; //added line!
    s.erase(std::remove_if(s.begin(),s.end(),is_repeated<char>(set)),s.end()); 
    std::cout << s ;
}

出力：

sangeth

問題がなくなった！

では、最初の解決策の何が問題になっていますか？

また、メンバー変数を作成しない場合 unique 次に、参照タイプ 問題はありません.

何が悪いのか std::set また is_repeated ファンクタ？正確に問題はどこにありますか？

また、 is_repeated Functorはどこかにコピーされ、そのすべてのメンバーもコピーされます。ここで問題はありません！

役に立ちましたか？

解決

gcc（libstdc ++）, remove_if 本質的に実装されています

    template<typename It, typename Pred>
    It remove_if(It first, It last, Pred predicate) {
      first = std::find_if(first, last, predicate);
    //                                  ^^^^^^^^^
      if (first == last)
         return first;
      else {
         It result = first;
         ++ result;
         for (; first != last; ++ first) {
           if (!predicate(*first)) {
    //          ^^^^^^^^^
              *result = std::move(*first);
              ++ result;
           }
         }
      }
    }

あなたの述語が渡されることに注意してください バリュー に find_if, 、したがって、構造体、したがってセットは内部で変更されました find_if 発信者に伝播されることはありません。

最初の複製が表示されるため：

  saaangeetha
//  ^

初期 "sa" 後に保持されます find_if 電話。その間、 predicateのセットは空です（内部の挿入 find_if ローカルです）。したがって、その後のループは3番目を維持します a.

   sa | angeth
// ^^   ^^^^^^
// ||   kept by the loop in remove_if
// ||
// kept by find_if

他のヒント

機能者は、ファンクターのコピーが元の機能者と同一である方法で設計されることになっています。つまり、1つのファンサーのコピーを作成してから一連の操作を実行する場合、どのファンサーを使用しても、2つのファンチャーをインターリーブする場合でも、結果は同じでなければなりません。これにより、STLの実装により、ファットをコピーし、適切であると見なされるように渡す柔軟性が得られます。

最初のファンチャーを使用すると、このクレームは保持されません。なぜなら、私があなたのファンチャーをコピーしてそれを呼び出すと、その保存されたセットに加えた変更が元のファンチャーに反映されないため、コピーとオリジナルは異なる機能を遂行するためです。同様に、2番目のファンチャーを使用して、参照ごとにセットを保存しないようにすると、ファンクターの2つのコピーは同じように動作しません。

ただし、ファクターの最終バージョンが機能する理由は、セットが参照によって保存されているという事実は、TUEファンチャーの任意の数のコピーが互いに同じように動作することを意味するためです。

お役に立てれば！

実際には答えではありませんが、考慮すべきもう1つの興味深い情報として、元のファンチャーを使用しているにもかかわらず、これは機能します。

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::remove_copy_if(s.begin(), s.end(), 
                        std::ostream_iterator<char>(std::cout), 
                        is_repeated<char>());
    return 0;
}

編集：私はそれがこの動作に影響を与えるとは思わないが、私はあなたのfunctorのマイナーなスリップも修正した（operator（）は明らかにタイプtのパラメーターを取るべきであるが、そうではないでください char).

問題はその中にある可能性があると思います is_repeated Functorは、実装内のどこかにコピーされます std::remove_if. 。その場合、デフォルトのコピーコンストラクターが使用され、これが順番に呼び出されます std::set コンストラクターをコピーします。あなたは2つになります is_repeated おそらく独立して使用されています。ただし、両方のセットが異なるオブジェクトであるため、相互の変化は見られません。フィールドを回す場合 is_repeated::unique 参考までに、コピーされたファンチャーは、この場合に望むものである元のセットをまだ使用しています。

ファンチャークラスは純粋な機能であり、独自の状態を持たない必要があります。 Scott Meyer'sの項目39を参照してください 効果的なSTL これについての良い説明のために予約してください。しかし、それの要点は、ファンチャークラスがアルゴリズム内で1回以上コピーされる可能性があることです。

他の答えは正しいです。問題は、あなたが使用している機能者がそうではないということです コピー可能 安全。特に、GCC（4.2）に付属するSTLは実装しています std::remove_if の組み合わせとして std::find_if 削除する最初の要素を見つけるには std::remove_copy_if 操作を完了する。 

template <typename ForwardIterator, typename Predicate>
std::remove_if( ForwardIterator first, ForwardIterator end, Predicate pred ) {
   first = std::find_if( first, end, pred ); // [1]
   ForwardIterator i = it;
   return first == last? first 
          : std::remove_copy_if( ++i, end, fist, pred ); // [2]
}

1]のコピーは、見つかった最初の要素がファンチャーのコピーに追加されることを意味し、それは最初の「A」が忘却で失われることを意味します。ファンクターも[2]にコピーされていますが、そのコピーのオリジナルが空のファンチャーであるためではない場合は問題ありません。

の実装に応じて remove_if あなたの述語のコピーを作ることができます。ファンチャーをリファクタリングして、ステートレスにするか、使用するか boost.ref 「通常、議論のコピーを取る機能テンプレート（アルゴリズム）への参照を渡すために」

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

#include <boost/ref.hpp>
#include <boost/bind.hpp>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 

int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), boost::bind<bool>(boost::ref(is_repeated<char>()),_1)), s.end());
    std::cout << s;

    return 0;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top