c++ - 查找一张地图是否是另一张地图的子集

Question

我有两张 STL 地图std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}};和std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};

我想知道 bar 是否是 foo 的子集。

由于元素是在地图中排序的，我想从 foo 中的 bar 中找到第一个元素，然后从该位置的 foo 中的 bar 中找到连续的元素。

这里的问题是我无法找到一种方法来使用 cpp 中的 STL 映射来做到这一点。对于从地图中的某个位置到地图末尾的每个查找，我可以减少地图中的搜索范围吗？

我希望我解释了这个问题。

Answer 1

将std::includes算法与仅比较键的自定义比较器一起使用：

#include <map>
#include <algorithm>
#include <iostream>

int main()
{
    std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}};
    std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};
    typedef std::pair<int,int> pair;

    std::cout <<
       std::includes(foo.begin(), foo.end(), bar.begin(), bar.end(),
           [](const pair& p1, const pair& p2)
           {
               return p1.first < p2.first;
           });
}

Answer 2

您可以提取两个映射（和）的键集（set1和） ，只要它们是排序的，您就可以执行以下操作：set2foobar

if (std::includes(set1.begin(), set1.end(),
                  set2.begin(), set2.end())) {
  // ...
}

见std::includes。

Answer 3

一个简单的方法是结合使用Boost.Rangeboost::includes：

using namespace boost::adaptors;
bool result = includes(foo | map_keys, bar | map_keys);

下面是一个最小的、完整的程序的样子（映射值被忽略）：

#include <map>
#include <iostream>
#include <boost/range.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>

int main()
{
    std::map<int, int> foo = {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}};
    std::map<int, int> bar = {{2, 0}, {4, 0}, {5, 0}};

    using namespace boost::adaptors;
    std::cout << includes(foo | map_keys, bar | map_keys);
}

这是一个活生生的例子。