如何获得std::: std::map的键集

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::set of 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::地图。我想在每个键的集合上执行一个集合交集(以查找两个映射的公共键)。在将来的某个时候，我想我可能也想在这里执行集合减法。幸运的是，STL包含了这两个操作的函数。问题是，我似乎无法从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::pair objects 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_crossroads()函数到映射中，因为映射公开了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中可用的大多数优秀模板技巧都不能使用。

9 个解决方案

#1

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检索所有键(或值)并将它们放入向量中?

#2

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:::map: value_type是std:::pair。您希望只复制对的第一部分，这意味着您需要一个std::transform。现在，由于您将在集合上使用insert_iterator，顺序无关紧要。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的select1，则不需要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; });

#3

Map does guarantee 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.

地图并保证秩序;这就是为什么它被称为排序关联容器。您可以使用set_crossroads与自定义比较器函数(这里列出的第二个变体)一起使用。

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

默认操作符< over对比较两个组件。由于您只需要对这对(映射键)的第一部分进行等价处理，所以您需要定义自己的比较运算符来提供这种关系(这就是上面的函数所做的)。

#4

In practice,

在实践中,

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

#5

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

最好的非sgi、非boost STL算法友好的解决方案是扩展map::

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

#6

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

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

#7

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

#8

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:::adapter:map_key来生成键，参见boost:::adapter:::map_key文档中的示例。这似乎是在Boost 1.43中引入的，并且应该是与c++ 2003兼容的，但是我不知道具体的VC++ 6，它来自c++ 98时代。

#9

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编译。

#1