C++ 如何获得 std::map 的 std::set 键

how can I get a std::set of keys to a std::map

提问by rmeador

I was writing an algorithm this morning and I ran into a curious situation. I have two std::maps. I want to perform a set intersection on the sets of the keys of each (to find which keys are common to both maps). At some point in the future, I think it's likely I'll also want to perform set subtraction here as well. Luckily, the STL includes functions for both of those operations. The problem is, I can't seem to get a std::setof the keys out of a std::map. Is there any way to do this? I'm looking for something that would be this simple, like it is in Java:

今天早上我正在写一个算法，我遇到了一个奇怪的情况。我有两个std::map。我想对每个键的集合执行集合交集（以找到两个映射共有的键）。在未来的某个时候，我认为我很可能也想在这里执行集合减法。幸运的是，STL 包括这两种操作的函数。问题是，我似乎无法得到std::set密钥的出来的std::map。有没有办法做到这一点？我正在寻找这样简单的东西，就像在 Java 中一样：

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

My understanding is that I can't use the std::set_intersection()function directly on iterators into the maps because the maps expose std::pairobjects instead of just keys. Also, I don't think the map guarantees order. I'm also interested in performing this same operation on a pair of std::multimaps, if that makes any difference.

我的理解是我不能std::set_intersection()直接在迭代器上使用该函数到映射中，因为映射公开std::pair对象而不仅仅是键。另外，我认为地图不能保证顺序。我也有兴趣对一对std::multimaps执行相同的操作，如果这有什么不同的话。

EDIT: I forgot to mention initially that due to the age of the compiler I'm forced to use (MSVC++ 6), most of the nifty template tricks that are available in boost can not be used.

编辑：我最初忘记提及，由于我被迫使用的编译器的年龄（MSVC++ 6），大多数在 boost 中可用的漂亮模板技巧都无法使用。

采纳答案by amit

You can use the versatile boost::transform_iterator to return an iterator that returns only the keys (and not the values). See How to retrieve all keys (or values) from a std::map and put them into a vector?

您可以使用通用的 boost::transform_iterator 来返回一个只返回键（而不是值）的迭代器。请参阅如何从 std::map 检索所有键（或值）并将它们放入向量中？

回答by MSalters

What you basically want is a copy, as std::map doesn't keep the keys in a std::set. std::copy assumes that the value types are compatible, which isn't the case here. The std::map::value_type is a std::pair. You want to copy only the first part of the pair, which means you need a std::transform. Now, since you will be using an insert_iterator on the set, order doesn't matter. The std::set will sort on insertion, even though the map was already sorted.

您基本上想要的是一个副本，因为 std::map 不会将键保存在 std::set 中。std::copy 假定值类型是兼容的，但此处并非如此。std::map::value_type 是一个 std::pair。您只想复制该对的第一部分，这意味着您需要一个 std::transform。现在，由于您将在集合上使用 insert_iterator，因此顺序无关紧要。即使地图已经排序， std::set 也会在插入时排序。

[edit] Code might be easier. Top of my head, not compiled.

[编辑] 代码可能更容易。我的头顶，没有编译。

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

If you've got SGI's select1st, you don't need the boost::bind.

如果你有 SGI 的 select1st，你就不需要 boost::bind。

[edit] Updated for C++14

[编辑] 为 C++14 更新

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

回答by zvrba

Map doesguarantee order; that's why it's called a sorted associative container. You can use set_intersection with a custom comparator function, the second variant listed here.

Map确实保证顺序；这就是为什么它被称为排序关联容器。您可以将 set_intersection 与自定义比较器函数一起使用，此处列出了第二个变体。

So, something like

所以，像

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);

should do the trick. (It is also possible to use boost::lambda and bind to avoid writing a temporary function.)

应该做的伎俩。（也可以使用 boost::lambda 和 bind 来避免编写临时函数。）

The default operator< over pairs compares both components. Since you need equivalence only over the first part of the pair (the map key), you need to define your own comparison operator that provides such relation (which is what the function above does).

默认 operator< over pair 比较两个组件。由于您只需要对的第一部分（映射键）等价，您需要定义自己的比较运算符来提供这种关系（这就是上面的函数所做的）。

回答by Antti Huima

In practice,

在实践中，

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

回答by Marius

The best non-SGI, non-boost STL algorithm-friendly solution is to extend map::iterator like so:

最好的非 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());
}

and then use them like so:

然后像这样使用它们：

        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));

回答by Darius Kucinskas

I found good link for your question here

我在这里找到了您的问题的好链接

and have some code for your problem:

并为您的问题提供一些代码：

    #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;
    }

回答by rlbond

You can just iterate through and add each key to a set. Sets and maps are both ordered, unordered variants are not.

您可以遍历并将每个键添加到集合中。集合和映射都是有序的，无序变体不是。

回答by YitzikC

You could perhaps create an iterator for a map which only yields the keys using boost::adapters::map_key, see example in the boost::adapters::map_key documentation. This appears to have been introduced in Boost 1.43, and is supposed to be C++ 2003 compatible, but I don't know about VC++ 6 specifically, which is from the C++ 98 era.

您也许可以为仅使用 boost::adapters::map_key 生成键的映射创建迭代器，请参阅boost::adapters::map_key 文档中的示例。这似乎是在 Boost 1.43 中引入的，应该是 C++ 2003 兼容的，但我不知道 VC++ 6 具体是什么，它来自 C++ 98 时代。

回答by ivannaz

Building up from the answer from zvrba and the comment from dianot:

根据 zvrba 的回答和 dianot 的评论：

Just make the receiving collection be a vector of pairs instead of a map, and the problem pointed by dianot is over. So, using zvrba example:

只要让接收集合成为成对的向量而不是映射，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;});

So without constructing intermediate copies or sets we can get efficiently the intersection of two maps. This construction compiles with gcc5.3.

因此，无需构建中间副本或集合，我们就可以有效地获得两个映射的交集。此结构使用 gcc5.3 编译。