7

s1 と s2 はセットです (Python セットまたは C++ std::set)
s2 の要素を s1 に追加するには (セット ユニオン)、次のようにします。

Python: s1.update(s2)

C++: s1.insert(s2.begin(), s2.end());

s1 から s2 の要素を削除するには (集合の差)、次のようにします。

Python: s1.difference_update(s2)

これに相当する C++ は何ですか? コード

s1.erase(s2.begin(), s2.end());

s1.erase() は s1 からの反復子を必要とするため、機能しません。コード

std::set<T> s3;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.end());
s1.swap(s3);

動作しますが、少なくとも Python と比較すると、過度に複雑に見えます。

もっと簡単な方法はありますか？

4

5 に答える 5

5

Usingstd::set_differenceは、C++ でこれを行う慣用的な方法です。C++/STL と他の多くの言語との主な違い (しゃれを意図したもの) の 1 つに出くわしました。STL は、操作をデータ構造に直接バンドルしません。std::setこれが、差分ルーチンを実装しない理由です。

std::set_difference基本的に、操作の結果を別のオブジェクトに書き込むなどのアルゴリズム。興味深いことに、このアルゴリズムでは、オペランドのいずれかまたは両方が実際に である必要はありませんstd::set。アルゴリズムの定義は次のとおりです。

効果[first1, last1): 範囲内に存在しない範囲の要素を で[first2, last2)始まる範囲にコピーしresultます。構築された範囲内の要素がソートされます。

Requires : 結果の範囲は、元の範囲のいずれとも重複してはなりません。入力範囲は、同じ順に並べる必要がありますoperator<。

戻り値: 構築された範囲の終わり。

複雑さ: せいぜい2 * ((last1 - first1) + (last2 - first2)) - 1比較

興味深い違いは、C++ バージョンは任意の 2 つのソート範囲に適用できることです。ほとんどの言語では、 set differenceアルゴリズムにアクセスする前に、呼び出し元のオブジェクト (左側のオペランド) を強制的にセットに変換する必要があります。

これはあなたの質問にはあまり関係ありませんが、これが、さまざまなセットアルゴリズムがメンバーメソッドではなく独立したアルゴリズムとしてモデル化されている理由です。

于 2011-05-22T11:16:09.687 に答える
4

2 番目のセットを繰り返す必要があります。

for( set< T >::iterator iter = s2.begin(); iter != s2.end(); ++iter )
{
    s1.erase( *iter );
}

これは 、一意のオブジェクトを新しいコンテナーにコピーしますが、直線的なstd::set_difference時間set_differenceがかかりますが、何もコピーしませんが、..eraseO(n * log( n ) )

言い換えれば、コンテナーに応じて、方法を選択することができます。

ご指摘ありがとうございます David Rodríguez - dribeas！(:

編集：ドー！最初に BOOST_FOREACH について考えましたが、使用できないと間違っていました..-イテレータは必要ありませんが、値だけが必要です.. user763305 が自分で言ったように。

于 2011-05-22T10:59:17.297 に答える
4

C++ ではdifference、セットにメソッドはありません。2 つのセットに違いを適用するよりも一般的であるため、これset_differenceははるかにぎこちなく見えます。もちろん、セットのインプレース差分の独自のバージョンを実装できます。

template <typename T, typename Compare, typename Allocator>
void my_set_difference( std::set<T,Compare,Allocator>& lhs, std::set<T,Compare,Allocator> const & rhs )
{
    typedef std::set<T,Comapre,Allocator> set_t;
    typedef typename set_t::iterator iterator;
    typedef typename set_t::const_iterator const_iterator;

    const_iterator rit = rhs.begin(), rend = rhs.end();
    iterator it = lhs.begin(), end = lhs.end();
    while ( it != end && rit != rend )
    {
        if ( lhs.key_comp( *it, *rit ) ) {
            ++it;
        } else if ( lhs.key_comp( *rit, *it ) ) {
            ++rit;
        } else {
            ++rit;
            lhs.erase( it++ );
        }
    }
}

このアルゴリズムのパフォーマンスは、引数のサイズに比例し、最初の引数をその場で変更するため、追加のコピーは必要ありません。

于 2011-05-22T11:58:04.083 に答える
1

remove_ifセット内の存在をテストするための独自のファンクターを作成してそれを行うこともできます。

std::remove_if(s1.begin(), s1.end(), ExistIn(s2));

set_differenceおそらく両方のセットを一度だけスキャンするので、より効率的だと思います

于 2011-05-22T16:36:24.353 に答える
1

Python set は順序付けされておらず、順序付けられている std::set よりも C++ std::unordered_set に相当します。

David Rodríguez のアルゴリズムは、std::set が順序付けられているという事実に依存しているため、lhs セットと rhs セットは、アルゴリズムで示されている方法でトラバースできます。

順序付きセットと順序なしセットの両方で機能するより一般的なソリューションについては、Python セットの「非順序性」の性質を強制/維持する場合は、Kiril Kirov のアルゴリズムを採用するのが安全です。

于 2013-06-03T19:49:15.073 に答える