1

假设我正在使用一个使用三个字符串作为键的映射。这是一个简单的示例结构：

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_boundand upper_bound。如果我想找到由任何 key0、任何以“ab”开头的 key1 和任何以“cd”开头的 key2 形成的值的范围，分别使用这两个函数和ExampleMapKey("", "ab", "cd")和ExampleMapKey("", "ac", "ce")将让我遍历不满足我的键要求。或者我会错过这样做的钥匙吗？无论哪种方式，都是错误的。

看来我需要的是一个数据结构，它可以按每个键显式索引，并且还允许我执行潜在的复杂lower_bound和upper_bound迭代。有这样的事吗？我不一定使用字符串，也不限于只有 3 个键，所以它需要是 STL 样式或类似的通用。

4

2 回答 2

2

  1. Boost 多索引容器库可以提供帮助。

    更新：重读您的问题后，我认为您可能必须做 db 课程中所教的内容；您必须使用其中一个索引来创建临时结果，并根据您的第二个约束修剪该结果（或者，您可以在每个索引上运行每个约束，加入结果）。Boost Multi-index Containers AFAIK 一次只允许查找一个索引。

  2. 对于您询问的特定类型的查询，您可以通过在索引分区上添加索引来提供非常专业的数据结构来提供帮助。也就是说，例如，您取第二个索引，将其分成两半，为前半部分和第二部分重写第三个索引。然后你将每一半分开并重复。这样，您可以选择第二个索引的一部分，然后选择第三个索引的一部分（大约）在第二个索引的该部分内。但我不知道有任何图书馆这样做。

  3. 另一种方法可能是某种多维数据结构，尽管我不熟悉将这种结构与非数字键一起使用。例如，假设您的键是整数，您可以使用 3D kd-tree或其他空间索引，并查询三次范围。例如：（使用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}。

std::map<>你必须找到每个key0的范围，然后在给定的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 回答