2

std::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ではなく）提供できますが、残念ながらこれは不可能です。おそらく、プレフィックス検索が多かれ少なかれ賢明なアプリケーションのみ。

オプションは、実行時にマップで使用される比較を変更するか（これは非常に悪いスタイルだと思います）、タプル内にあるすべてのタイプに相当する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これは引数なしで s を受け入れる必要がありInfiniteExtensionOf(そのようなタプルは暗黙的に変換されることを願っています)、 or を呼び出すときに特定のフィールドの値として +inf または -inf を簡単に指定できlower_boundます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)));

intこれは、とで構成されるキーを持つマップ用でstd::string、それぞれが小さな値または大きな値に置き換えられる可能性があります。

于 2012-11-15T16:43:34.717 に答える