c++ - std::map<tuple<int,int>.lower_bound/upper_bound 前缀搜索而不查找后缀的最小/最大元素

Question

我正在构建一个使用 std::map<tuple<...>> 的类作为查找数据结构。我希望能够在 map 上进行前缀搜索，以查找元组内共享某个前缀的所有元素。例如:

using namespace std;
map<tuple<int,int,int,string>,Value> index;
index.insert(make_tuple(1,1,1,"a"),Value());
index.insert(make_tuple(1,1,2,"b"),Value());
index.lower_bound(make_tuple(1,1,std::numeric_limits<int>::min(),""));

这正是我所需要的但是我必须手动(对于非 POD 类型)计算出最小值。更糟糕的是，当我想找到具有特定前缀的最高元素(我确实这样做)时，我必须找到特定类型的最大元素值，在 string 的情况下是比较有问题的。

理想情况下，我能够提供 map.find/lower_bound/upper_bound (不是 std::find ，它是 map 上的线性复杂性)具有单独的比较，不考虑后缀，但不幸的是这是不可能的，很可能是因为前缀搜索或多或少是唯一明智的应用程序。

我认为选项将修改 map 在运行时使用的比较(我认为这是非常糟糕的风格)或为我将在元组内部拥有的所有类型实现等效的 numeric_limits 。

是否有更好的选择来在 map /集合上进行前缀搜索？

Answer 1

您可以将“静态”比较仿函数传递给 map当你定义它的时候。默认排序为tuple<...>是类型的字典顺序。

将 key 类型扩展到允许将字段标记为 max 的 key 类型或min值，并提供接受它们的排序算法。

即，像这样:

template<typename T>
struct InfiniteExtensionOf
{
  enum ExtendedOrder {NegInfinity=-1, Normal=0, PosInfinity=1};
  ExtendedOrder order;
  T value;
  bool operator<(InfiniteExtensionOf const& other) const
  {
    if (order != other.order)
      return order<other.order;
    return value < other.value;
  }
  template<typename U>
  InfiniteExtensionOf( U&& u ):order(Normal),value(std::forward(u)) {}
  InfiniteExtensionOf( InfiniteExtensionOf&& other ):order(other.order),value(std::move(other.value)) {}
  InfiniteExtensionOf( InfiniteExtensionOf& other ):order(other.order),value(other.value) {}
  InfiniteExtensionOf( InfiniteExtensionOf const& other ):order(other.order),value(other.value) {}
  InfiniteExtensionOf( ExtendedOrder& eo ):order(eo), value() {}
  InfiniteExtensionOf( ExtendedOrder&& eo ):order(eo), value() {}
  InfiniteExtensionOf( ExtendedOrder const& eo ):order(eo), value() {}
};

然后像这样键入:

map<tuple<InfiniteExtensionOf<int>, InfiniteExtensionOf<int>, InfiniteExtensionOf<int>, InfiniteExtensionOf<string>>, Value> myMap;

应该接受tuple没有InfiniteExtensionOf参数(我希望这样的元组隐式转换)，并且您可以在调用 lower_bound 时轻松指定 +inf 或 -inf 作为特定字段的值或upper_bound .

...

请注意，如果 lower_bound采用模板参数，只要求它以符合现有顺序的方式与映射中的元素兼容，这样会少一些麻烦。 :) 但遗憾的是，事实并非如此。