2

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

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 在运行时使用的比较（我认为这是非常糟糕的风格）或为我将在元组中拥有的所有类型实现 numeric_limits 等效项。

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

4

2 回答 2

2

map您可以在定义它时将“静态”比较函子传递给。默认排序tuple<...>是对类型的字典排序。

将键类型扩展到允许将字段标记为max或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参数的 s （我希望这样的元组隐式转换），并且您可以在调用时轻松地将 +inf 或 -inf 指定为特定字段的值lower_boundor upper_bound。

...

请注意，如果lower_bound采用模板参数并且只要求它以与现有排序一致的方式与地图中的元素兼容，那么麻烦会更少。:) 但遗憾的是，这不是真的。

于 2012-11-15T16:37:44.963 回答
1

您可以做的不是直接使用键类型，而是使用可选类型的三态版本：

  1. 如果设置了值，则比较只使用该值。
  2. 如果small设置了标志，则认为该值小于所有其他值。
  3. 如果large设置了标志，则认为该值大于任何其他值。

要找到下限，您将搜索，例如，使用以下small值：

map.lower_bound(srd::make_tuple(
    tristate<int>(17),
    tristate<std::string>(tristate_small)));

这适用于具有由 anint和 a组成的键的地图std::string，每个都可能被一个小值或大值替换。

于 2012-11-15T16:43:34.717 回答