c++ - std::mapへのキーのstd::setを取得するにはどうすればよいですか

Question

今朝アルゴリズムを書いていたところ、不思議な状況に遭遇しました。私は2つ持っていstd::mapます。それぞれのキーのセットに対してセット交差を実行したいと思います（両方のマップに共通するキーを見つけるため）。将来的には、ここでもセット減算を実行したいと思うでしょう。幸い、STLにはこれら両方の操作の関数が含まれています。std::set問題は、からキーを取得できないように見えることですstd::map。これを行う方法はありますか？Javaの場合のように、これほど単純なものを探しています。

std::set<Foo> keys = myMap.getKeySet();

私の理解では、マップはキーだけでなくオブジェクトをstd::set_intersection()公開しているため、マップへのイテレータでこの関数を直接使用することはできません。std::pairまた、地図は順序を保証するとは思いません。std::multimap違いがあれば、この同じ操作をsのペアで実行することにも興味があります。

編集：私が使用することを余儀なくされたコンパイラ（MSVC ++ 6）の時代のために、ブーストで利用可能な気の利いたテンプレートトリックのほとんどは使用できないことを最初に言及するのを忘れました。

score 22 · Accepted Answer

std::map はキーを std::set に保持しないため、基本的に必要なのはコピーです。std::copy は、値の型に互換性があると想定していますが、ここではそうではありません。std::map::value_type は std::pair です。ペアの最初の部分だけをコピーしたいので、std::transform が必要です。セットで insert_iterator を使用するため、順序は関係ありません。マップが既にソートされていても、std::set は挿入時にソートします。

[編集] コードはもっと簡単かもしれません。頭のてっぺん、コンパイルされていません。

std::transform(MyMap.begin(), MyMap.end(),
    std::inserter(MySet, MySet.end()),
    boost::bind(&std::pair<Key,Value>::first, _1));

SGI の select1st がある場合は、boost::bind は必要ありません。

[編集] C++14 用に更新

std::transform(MyMap.begin(), MyMap.end(),
    std::inserter(MySet, MySet.end()),
    [](auto pair){ return pair.first; });

score 12 · Accepted Answer

Mapは順序を保証します。そのため、並べ替えられた連想コンテナーと呼ばれます。ここにリストされている 2 番目のバリアントであるカスタムコンパレータ関数で set_intersection を使用できます。

だから、次のようなもの

bool your_less(const your_map::value_type &v1, const your_map::value_type &v2)
{ return v1.first < v2.first; }

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), your_output_it, your_less);

トリックを行う必要があります。(boost::lambda と bind を使用して、一時的な関数の記述を回避することもできます。)

デフォルトの operator< over ペアは、両方のコンポーネントを比較します。ペアの最初の部分 (マップキー) に対してのみ等価性が必要なため、そのような関係を提供する独自の比較演算子を定義する必要があります (上記の関数はこれを行います)。

score 9 · Accepted Answer

実際には、

yourmap::const_iterator mi;
set<key_type> k;
for (mi = yourmap.begin(); mi != yourmap.end(); ++mi)
  k.insert(mi->first);
return k;

score 8 · Accepted Answer

汎用性の高い boost::transform_iterator を使用して、キーのみを返す (値は返さない) イテレータを返すことができます。std::map からすべてのキー (または値) を取得してベクターに入れる方法を参照してください。

score 5 · Accepted Answer

非 SGI、非ブースト STL アルゴリズムに最適なソリューションは、次のように map::iterator を拡張することです。

template<typename map_type>
class key_iterator : public map_type::iterator
{
public:
    typedef typename map_type::iterator map_iterator;
    typedef typename map_iterator::value_type::first_type key_type;

    key_iterator(const map_iterator& other) : map_type::iterator(other) {} ;

    key_type& operator *()
    {
        return map_type::iterator::operator*().first;
    }
};

// helpers to create iterators easier:
template<typename map_type>
key_iterator<map_type> key_begin(map_type& m)
{
    return key_iterator<map_type>(m.begin());
}
template<typename map_type>
key_iterator<map_type> key_end(map_type& m)
{
    return key_iterator<map_type>(m.end());
}

そして、次のように使用します。

        map<string,int> test;
        test["one"] = 1;
        test["two"] = 2;

        set<string> keys;

//      // method one
//      key_iterator<map<string,int> > kb(test.begin());
//      key_iterator<map<string,int> > ke(test.end());
//      keys.insert(kb, ke);

//      // method two
//      keys.insert(
//           key_iterator<map<string,int> >(test.begin()),
//           key_iterator<map<string,int> >(test.end()));

        // method three (with helpers)
        keys.insert(key_begin(test), key_end(test));

score 2 · Accepted Answer

ここであなたの質問の良いリンクを見つけました

あなたの問題のためのいくつかのコードがあります：

    #include <iostream>
    #include <map>
    #include <set>
    #include <iterator>

    typedef std::map<std::string, int> MyMap;

    // also known as select1st in SGI STL implementation
    template<typename T_PAIR>
    struct GetKey: public std::unary_function<T_PAIR, typename T_PAIR::first_type>
    {
        const typename T_PAIR::first_type& operator()(const T_PAIR& item) const
        {
            return item.first;
        }
    };

    int main(int argc, char** argv)
    {
        MyMap m1,m2;

        m1["a"] = 1;
        m1["b"] = 2;
        m2["c"] = 3;
        m2["b"] = 3;

        std::set<std::string> s;
        std::transform(m1.begin(), m1.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>());
        std::transform(m2.begin(), m2.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>());
        std::copy(s.begin(), s.end(), std::ostream_iterator<std::string>(std::cout, " "));
        std::cout << std::endl;
        return 0;
    }

score 2 · Accepted Answer

各キーを反復してセットに追加するだけです。セットとマップはどちらも順序付けされていますが、順序付けられていないバリアントはそうではありません。

score 1 · Accepted Answer

zvrba からの回答と dianot からのコメントから構築します。

受信コレクションをマップではなくペアのベクトルにするだけで、dianot が指摘する問題は解決します。したがって、zvrba の例を使用すると、次のようになります。

std::vector<std::pair<keytype, valtype>> v;

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(),
std::back_inserter(v), []( std::pair<keytype, valtype> const & a,
std::pair<keytype, valtype> const & b){return a.first < b.first;});

したがって、中間のコピーやセットを作成しなくても、2 つのマップの交点を効率的に取得できます。この構造は gcc5.3 でコンパイルされます。

c++ - std::mapへのキーのstd::setを取得するにはどうすればよいですか

10 に答える 10

Related

Reference