类似数据库搜索的容器

Question

我正在寻找一些STL，Boost或类似的容器，以使用数据库中使用相同的索引来搜索记录：使用此类查询：

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

或者

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

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

我可以创建一个分类的向量或列表，并使用二进制搜索（通过阅读中间的元素并查看它是否比“ x'”或“ x'中的元素”中的第2个搜索（将集合分为2），但是我想知道是否有一些准备就绪 - 我可以在不重新发明轮子的情况下使用的容器？

Answer 1

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)

Answer 2

std::map 很好，或者 std::set 如果没有字符串以外没有数据。将您的前缀字符串传递到 lower_bound 要获取第一个字符串，该字符串处于或之后。然后通过地图向前迭代，直到击中末端或找到不从前缀开始的元素。