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

Question

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

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

или

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

Я подумал об использовании STD :: Map, но я не могу, потому что мне нужно искать поля, которые «начнутся с текста», а не те, которые «равны». Помимо этого, мне нужно, чтобы он работал на нескольких полях (каждая «запись» имеет 6 полей, например), поэтому мне понадобится отдельная STD :: MAP для каждого.

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

Answer 1

Boost.multi-index. Позволяет управлять с несколькими индексами, и он реализует in itele_bound as для 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 (конечно, эта функция требует большего количества аргументов, чтобы быть полностью универсальными, см. вопрос).

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

Answer 2

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