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

Question

今天早上我正在写一个算法,我遇到了一个奇怪的情况.我有两个std::map.我想在每个键的各组键上执行一组交集(找到两个键共有的键).在未来的某个时刻,我认为我也可能也希望在这里执行set减法.幸运的是,STL包含了这两种操作的功能.问题是,我似乎无法从中得到一把std::set钥匙std::map.有没有办法做到这一点？我正在寻找一些简单的东西,就像在Java中一样:

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

我的理解是我不能std::set_intersection()直接在迭代器上使用函数到地图中,因为地图暴露了std::pair对象而不仅仅是键.此外,我不认为地图保证顺序.我也有兴趣在一对std::multimaps 上执行相同的操作,如果这有任何区别的话.

编辑:我最初忘了提到由于我被迫使用的编译器的年龄(MSVC++ 6),大多数在boost中可用的漂亮模板技巧都无法使用.

Answer 1

你基本上想要的是一个副本,因为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.

[edit]更新了C++ 14

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

Answer 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来避免编写临时函数.)

默认运算符<over pairs比较两个组件.由于您只需要在对的第一部分(映射键)上进行等效,因此您需要定义自己的比较运算符来提供这种关系(这是上面的函数所做的).

Answer 3

在实践中,

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

Answer 4

您可以使用通用的boost :: transform_iterator返回仅返回键(而不是值)的迭代器.请参阅如何从std :: map中检索所有键(或值)并将它们放入向量中？

Answer 5

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