1

我想对 std::map<> 实例的键进行一些设置交集操作，而无需事先将键复制到 std::set<> 中。

它没有记录在 API 中，但是有什么方法可以在 O(1) 时间内从 std::map<> 中提取密钥并将它们放入 std::set<> 中？

4

3 回答 3

4

创建一个迭代器适配器，它首先为地图返回并将其与set_intersection.

于 2013-01-17T23:34:08.127 回答
3

首先不，没有O(1)从地图中获取一组键的操作。构造集合必须是Omega(n).

但是，您可以set_intersection直接在地图和其他范围上执行您想要的操作，无论是什么。未经测试的代码：

template <typename InputIterator, typename Map, typename OutputIterator>
void map_set_intersection(InputIterator first, InputIterator last, const Map &m, OutputIterator o) {
    std::set_intersection(
        first, last, 
        m.begin(), m.end(), 
        o, 
        KeyCompare<typename Map::value_type, typename std::iterator_traits<InputIterator>::value_type>()
    );
}

所有的魔法都在 KeyCompare 类型中：

template <typename MapValue, typename SetValue>
struct KeyCompare {
    bool operator()(const MapValue &lhs, const SetValue &rhs) {
        return lhs.first < rhs;
    }
    bool operator()(const SetValue &lhs, const MapValue &rhs) {
        return lhs < rhs.first;
    }
};

std::set_difference被定义为从指定的第一个范围复制值，在本例中是迭代器定义的范围。它可以做到这一点，前提是它可以按任意顺序将第一个范围内的值与第二个范围内的值进行比较（它可以，这要归功于KeyCompare）。这两个范围不需要具有相同的类型，因此您不需要地图中的一组键。

如果您已经在使用 6 参数形式set_intersection，那么您需要进行更改KeyCompare，以便在将键从映射条目中取出后，它使用您的比较器而不是<.

如果您正在使用自定义比较器或重载operator< 并且迭代器范围的值类型与映射的值类型相同，那么这不起作用。KeyCompare不能再使用这些类型来计算提供参数的顺序，因此它应该从哪一个中提取first。我不认为这是一个非常常见的场景，但我也没有看到使用这种方法来逃避它。您需要 Crazy Eddie 的解决方案，调整地图迭代器。这相当于这个问题：Iterate keys in a C++ map

于 2013-01-18T00:14:28.783 回答
0

你可以在你的地图上做一个 O(N) 集合的交叉点。请记住，当您遍历映射时，键是按顺序排列的，因此您可以使用非常类似于合并操作的算法...

您所做的就是在每个映射中维护一个迭代器，并递增键最小的那个。如果键相等，您可以添加到 adeque或list（vector在这种情况下，您将增加两个迭代器）。一旦其中一个迭代器到达其映射的末尾，您就完成了。

于 2013-01-17T23:07:41.447 回答