контейнер базы данных типа поиска

Question

Я ищу какой-то STL, Boost, или аналогичный контейнер, чтобы использовать один и тот же путь индексы используются в базах данных для поиска записи с помощью запроса, как это:

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

или

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

Я думал об использовании зОго :: карты, но я не могу, потому что мне нужен искать для полей, которые «начинаются с» каким-то текстом, а не те, которые «равен». Кроме того, мне нужно, чтобы он работал с несколькими полями (каждая «запись» имеет 6 полей, например), поэтому мне понадобится отдельная std :: map для каждого из них.

Я мог бы создать отсортированный вектор или список и использовать бинарный поиск (разбивая набор на 2 на каждом шаге, читая элемент посередине и видя, что он больше или меньше «X»), но мне интересно, это какой-то готовый контейнер, который я мог бы использовать, не изобретая колесо?

Answer 1

Boost.Multi-Index позволяет управлять несколькими индексами, и он реализует lower_bound как для std :: set/map. Вам нужно будет выбрать индекс, соответствующий полю, а затем сделать так, как если бы это была карта или набор.

Далее следует общая функция, которая может быть использована для получения пары итераторов, кулак для первого элемента, начинающегося с заданного префикса, второй первый элемент, начинающийся со следующего префикса, то есть конец поиска

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 (конечно, эта функция нуждается в большем количестве аргументов, чтобы быть полностью универсален, см question).

Результат starts_with может быть использован на любом алгоритме диапазона (см Boost.Range)

Answer 2

std::map - штраф, или std::set, если нет данных, кроме строки. Передайте свою префиксную строку в lower_bound, чтобы получить первую строку, которая сортируется после или после этой точки. Затем перейдите по карте до тех пор, пока вы не достигнете конца или не найдёте элемент, который не начинается с вашего префикса.