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 回答