1

キーを事前に std::set<> に複製せずに、 std::map<> インスタンスのキーに対していくつかの集合交差操作を実行したいと思います。

API には記載されていませんが、O(1) 時間で std::map<> からキーを抽出して std::set<> に入れる方法はありますか?

4

3 に答える 3

4

最初にマップを返すイテレータ アダプタを作成し、それを で使用しset_intersectionます。

于 2013-01-17T23:34:08.127 に答える
3

O(1)まず、マップから一連のキーを取得する操作はありません。セットの構築は である必要がありますOmega(n)。

ただし、それがset_intersection何であれ、マップや他の範囲で直接やりたいことを行うことができます. テストされていないコード:

template <typename InputIterator, typename Map, typename OutputIterator>
void map_set_intersection(InputIterator first, InputIterator last, const Map &m, OutputIterator o) {
    std::set_intersection(
        first, last, 
        m.begin(), m.end(), 
        o, 
        KeyCompare<typename Map::value_type, typename std::iterator_traits<InputIterator>::value_type>()
    );
}

すべての魔法は KeyCompare 型にあります。

template <typename MapValue, typename SetValue>
struct KeyCompare {
    bool operator()(const MapValue &lhs, const SetValue &rhs) {
        return lhs.first < rhs;
    }
    bool operator()(const SetValue &lhs, const MapValue &rhs) {
        return lhs < rhs.first;
    }
};

std::set_difference指定された最初の範囲 (この場合は反復子によって定義された範囲)から値をコピーするように定義されています。最初の範囲の値と 2 番目の範囲の値をどちらの順序でも比較できる場合は、それを行うことができます (これは のおかげで可能KeyCompareです)。2 つの範囲は同じタイプである必要はないため、マップからの一連のキーは必要ありません。

の 6 パラメータ形式を既に使用している場合は、マップ エントリからキーを取り出した後、 の代わりにコンパレータを使用するようset_intersectionに変更する必要があります。KeyCompare<

カスタム コンパレータまたはオーバーロードを使用していてoperator< 、イテレータ範囲の値の型がマップの値の型と同じである場合、これは機能しません。KeyCompare型を使用して、引数が提供された順序、したがってどの順序から抽出する必要があるかを判断できなくなりましたfirst。これはあまり一般的なシナリオではないと思いますが、このアプローチを使用してそれから逃れることもできません。Crazy Eddie のソリューションが必要です。マップ イテレータを適応させます。これは、次の質問に相当します: C++ マップでキーを反復処理する

于 2013-01-18T00:14:28.783 に答える
0

マップ上で O(N) セットの交差を行うことができます。マップを反復処理する場合、キーは順番に並んでいるため、マージ操作と非常によく似たアルゴリズムを使用できることを覚えておいてください...

各マップにイテレータを維持し、キーが最小のものをインクリメントするだけです。キーが等しい場合はdeque、listまたはに追加できますvector(その場合、両方の反復子をインクリメントします)。イテレータの 1 つがそのマップの最後に到達するとすぐに、完了です。

于 2013-01-17T23:07:41.447 に答える