3

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

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

或者

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

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

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

4

2 回答 2

10

Boost.Multi-Index允许您管理多个索引，它实现了 std::set/map 的 lower_bound。您将需要选择与该字段对应的索引，然后将其视为地图或集合。

接下来是一个通用函数，可用于获取几个迭代器，第一个以给定前缀开头的第一项，第二个以下一个前缀开头的第一项，即搜索结束

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）

于 2010-04-22T11:17:23.977 回答
5

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

于 2010-04-22T10:40:10.673 回答