Контейнер для поиска в базе данных - PullRequest
Новая
       14

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

3 голосов
/ 22 апреля 2010

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

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

или 

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

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

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

Ответы [ 2 ]

10 голосов
/ 22 апреля 2010

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

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

5 голосов
/ 22 апреля 2010

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

...