1

3つの文字列をキーとして使用するマップを使用しているとしましょう。構造体の簡単な例を次に示します。

struct ExampleMapKey
{
 std::string key0;
 std::string key1;
 std::string key2;

 bool operator<(const ExampleMapKey& other) const
 {
  if (key0 < other.key0) return true;
  else if (key0 > other.key0) return false;

  if (key1 < other.key1) return true;
  else if (key1 > other.key1) return false;

  return key2 < other.key2;
 }
}

さて、これは私が使いたいと決めるまではうまくいきlower_boundますupper_bound。key0、 "ab"で始まるkey1、および "cd"で始まるkey2によって形成される値の範囲を見つけたい場合は、これら2つの関数をそれぞれとで使用するとExampleMapKey("", "ab", "cd")、ExampleMapKey("", "ac", "ce")自分の要件。それとも、そうするキーを見逃しますか？いずれにせよ、それは間違っています。

私が必要としているのは、各キーによって明示的にインデックスを付け、潜在的に複雑な反復を実行できるようにするデータ構造であるように思われlower_boundますupper_bound。そんなことありますか？私は必ずしも文字列を使用しているわけではなく、3つのキーのみに制限されているわけでもないため、STLスタイルまたは同様の汎用である必要があります。

4

2 に答える 2

2

  1. Boost Multi-indexContainersLibraryが役に立ちます。

    更新：質問を読み直した後、dbクラスで教えられていることをしなければならないかもしれないと思います。インデックスの1つを使用して一時的な結果を作成し、2番目の制約に基づいてその結果を整理する必要があります（または、各インデックスで各制約を実行して結果を結合することもできます）。Boost Multi-index Containersは、一度に1つのインデックスのみを検索できます。

  2. あなたが尋ねた特定のタイプのクエリについては、インデックスのパーティションにインデックスを追加することで、役立つ非常に特殊なデータ構造を思い付くことができるかもしれません。つまり、たとえば、2番目のインデックスを取得し、それを半分に分割し、前半と後半の3番目のインデックスを書き換えます。次に、各半分を分割して繰り返します。このようにして、2番目のインデックスのセクションを選択し、続いて2番目のインデックスのその部分内にある（ほぼ）3番目のインデックスの部分を選択できます。しかし、私はこれを行うライブラリを知りません。

  3. 別のアプローチは、ある種の多次元データ構造かもしれませんが、私はそのような構造を非数値キーで使用することに慣れていません。たとえば、キーが整数であると想像してください。3Dkdツリーまたはその他の空間インデックスを使用して、3次範囲をクエリできます。例:( libssrckdtreeを使用すると、文字列でも機能する可能性があります）：

（3）のコード：

#include <ssrc/spatial/kd_tree.h>

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <cassert>

#include <string>

typedef std::array<std::string, 3> Point;

typedef ssrc::spatial::kd_tree<Point, Point> Tree;

int main()
{
  Tree tree;

  Point point = {{"any1","aa1","cc1"}};
  tree[point] = point;

  point = {{"any2","ab1","cc1"}};
  tree[point] = point;

  point = {{"any3","ab1","cd1"}};
  tree[point] = point;
  point = {{"any4","ab1","cd2"}};
  tree[point] = point;
  point = {{"any5","ab1","cd3"}};
  tree[point] = point;


  point = {{"any22","ac1","cc1"}};
  tree[point] = point;

  point = {{"any33","ac1","cd1"}};
  tree[point] = point;
  point = {{"any44","ac1","cd2"}};
  tree[point] = point;
  point = {{"any55","ac1","cd3"}};
  tree[point] = point;


  point = {{"any6","aa1","cd2"}};
  tree[point] = point;
  point = {{"any7","aa1","cd3"}};
  tree[point] = point;

  Point lower{ { "any0", "ab", "cd" } }, upper{ { "any9", "ac", "cd2" } };

  for(Tree::const_iterator it = tree.begin(lower, upper), end = tree.end();
      it != end; ++it)
  {
    Point point = it->first;
    Point value = it->second;
    std::cout << point[0] << ", " << point[1] << ", " << point[2] << std::endl;
  }


  return 0;
}

出力：

any3, ab1, cd1
any4, ab1, cd2
于 2012-09-24T17:53:45.577 に答える
0

そのようなstd::map場合、単一の範囲は存在せず、範囲のセットになります。

そのようなキーを検討してください（コンパレータオブジェクトによって定義されたとおりにソートされます）。

#0 {"aa", "aa", "cb" },
#1 {"aa", "ab", "cd" },
#2 {"aa", "abb", "cdd" },
#3 {"ab", "aa", "cb" },
#4 {"ab", "ab", "cd" },
#5 {"ab", "abb", "cdd" },

制約に一致する範囲は、{1.2}と{4,5}です。

すべてのkey0std::map<>の範囲を見つける必要があるので、指定されたkey0内で-key1に対してlower / upper_boundを実行し、次にkey2に対して同じことを実行します。ただし、そうするには、次の場所からマップを再定義します。

std::map<ExampleKey, T>

に

std::map<std::string, std::map<std::string, std::map<std::string, T> > >:

そして、すべての一致する範囲を見つけるには、次のようにします。

for (auto it0 = theMap.begin(); it0 != theMap.end(); ++it0)
{
    auto it1lower = it0->second.lower_bound("ab");
    auto it1upper = it0->second.upper_bound("ac");
    for (auto it1 = it1lower; it1 != it1upper; ++it)
    {
       auto it2lower = it1->second.lower_bound("cd");
       auto it2upper = it1->second.upper_bound("ce");
       // and now we have on of matching ranges:
    }
}
于 2012-09-24T19:02:59.483 に答える