c++ - std::map、std::equal_range 和比较函数

Question

如果我有一个使用比较函数（函子）插入键的映射/多重映射，是否也可以将 map::equal_range 与比较函数一起使用？例如，如果我有一个 std::map m 和键：

sometype a.getVal == 101
sometype b.getVal == 112 <-first pair (using equal_range)
sometype c.getVal == 113
sometype d.getVal == 121 <-second pair (using equal_range)

我想得到一个范围/一组键 11* 这可能吗？

Answer 1

不能使用map::equal_range()自定义比较器有一个很好的理由：它会破坏容器的关联性。可以这样做，但算法将是 O(n) 而不是 O(log(n))，因为它必须比较所有map元素，而不管它们的位置如何。

我认为解决您的问题的最佳解决方案是使用自定义函数 map::lower_bound()并map::upper_bound()找到您的间隔限制。就像是：

typedef std::map<int>::iterator Iter;
std::pair<Iter, Iter> CustomEqualRange (const std::map<int>& theMap, int lowerBound, int range)
{
  Iter lower = theMap.lower_bound(lowerBound);
  Iter upper = theMap.upper_bound(lowerBound + range);
  return std::make_pair(lower, upper);
}

Answer 2

该equal_range函数不提供该功能，但您可以调用lower_bound使用 传递值getVal == 110和使用upper_bound传递值getVal == 120。这对迭代器应该代表半开范围 [110, 120) 中的所有值。