用于类似数据库搜索的容器

Question

我正在寻找一些 STL、boost 或类似的容器，以使用与数据库中使用索引相同的方式来使用这样的查询来搜索记录：

select * from table1 where field1 starting with 'X';

或者

select * from table1 where field1 like 'X%';

我考虑过使用 std::map，但我不能，因为我需要搜索“以”某些文本“开头”的字段，而不是“等于”的字段。除此之外，我需要它在多个字段上工作（例如，每个“记录”有 6 个字段），因此我需要为每个字段提供一个单独的 std::map 。

我可以创建一个排序向量或列表并使用二分搜索（通过读取中间的元素并查看它是否大于或小于“X”，在每个步骤中将集合分成 2 个），但我想知道是否有一些现成的-制作容器我可以使用而无需重新发明轮子？

Answer 1

Boost.Multi-Index 允许您管理多个索引，并实现 std::set/map 的 lower_bound 。您需要选择与该字段对应的索引，然后就像它是地图或集合一样。

Next 后面跟随一个通用函数，可用于获取几个迭代器，第一个是从给定前缀开始的第一个项目，第二个是从下一个前缀开始的第一个项目，即搜索结束，

template <typename SortedAssociateveContainer>
std::pair<typename SortedAssociateveContainer::iterator, 
          typename SortedAssociateveContainer::iterator> 
starts_with(
  SortedAssociateveContainer const& coll, 
  typename SortedAssociateveContainer::key_type const& k)
{
  return make_pair(coll.lower_bound(k), 
                   coll.lower_bound(next_prefix(k));
}

其中

• next_prefix 获取下一个使用基于 SortedAssociateveContainer 比较器的字典顺序的前缀（当然，此函数需要更多参数才能完全通用，请参阅 问题）。

starts_with 的结果可用于任何范围算法（请参阅 Boost.Range)

Answer 2

std::map 没问题，或者 std::set 如果除了字符串之外没有数据。将您的前缀字符串传递到 lower_bound 中以获取在该点或该点之后排序的第一个字符串。然后向前迭代地图，直到到达末尾或找到不以您的前缀开头的元素。