Ускорьте поиск частичного индекса multi_index_container на основе результатов частичного_index_search

Чтобы проиллюстрировать свой вопрос, я скопировал приведенный ниже код из примера «Телефонная книга» справочного документа Boost.

struct phonebook_entry
{
  std::string family_name;
  std::string given_name;
  std::string ssn;
  std::string phone_number;
}

И я могу сделать частичный поиск, как показано ниже

// search for Dorothea White's number
phonebook::iterator it=pb.find(boost::make_tuple("White","Dorothea"));

Однако, если мне нужно подсчитать количество людей с фамилией «Белые», а затем найти, сколько «Белых» имеют «Доротею» в качестве имени, то как лучше всего это сделать? Я думаю, что могу выполнить два частичных запроса с помощью pb.find(boost::make_tuple("White") и pb.find(boost::make_tuple("White","Dorothea"). Но меня беспокоит, не вызовет ли это проблема с производительностью? Поскольку второй запрос не знает первого запроса и просто выполняет поиск по всему контейнеру. Предоставляет ли Boost что-то вроде следующего:

std::pair<iterator,iterator> partialResults=pb.equal_range("White");
std::pair<iterator, iterator> partialOfPartial=pb.equal_range("Dorothea", partialResults);

Или есть более разумный способ сделать это? Не только с точки зрения удобства, но и с точки зрения производительности.


c++ boost stl boost-multi-index equal-range
person Michael    schedule 19.07.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Поскольку phonebook имеет составной ключ, он сортируется по заданным именам в пределах фамилий. Таким образом, вы можете вызвать обычный std::equal_range в первом результате поиска для соответствует фиктивному phonebook_entry, в котором определено только "Дороти":

int main() 
{
    phonebook pb; // no initializer_list support for multi_index_container yet
    pb.insert({ "White", "Dorothy", "1" });  
    pb.insert({ "Black", "Dorothy", "2" });  
    pb.insert({ "White", "John",    "3" });  
    pb.insert({ "Black", "John",    "4" });  
    pb.insert({ "White", "Dorothy", "5" });  

   auto const w = pb.equal_range("White");
   auto const d = phonebook_entry{"", "Dorothy", ""};
   auto const wd = std::equal_range(w.first, w.second, d, [](phonebook_entry const& lhs, phonebook_entry const& rhs) {
       return lhs.given_name < rhs.given_name; 
   });
   std::for_each(wd.first, wd.second, [](phonebook_entry const& pbe) { 
       std::cout << pbe.phone_number << "\n"; 
   });
}

Телефонные номера для "White, Dorothy" 1 и 5.

person TemplateRex    schedule 19.07.2013
comment
Спасибо за ваш ответ. У меня есть еще один вопрос. Будут ли std::equal_range и pb.equal_range иметь производительность? Вышеприведенное было просто образцом, реальная работа, которую я собираюсь сделать, будет содержать 100 миллионов записей. Повлияет ли такое количество записей на производительность multi_index_container? - person Michael; 20.07.2013
comment
@Michael, нет проблем, было приятно узнать, как использовать эту библиотеку Boost, я давно хотел этого :-) - person TemplateRex; 20.07.2013
comment
@Michael относительно производительности: equal_range (как член контейнера, так и версия STL, не являющаяся членом) имеет сложность O(log N) при отсортированном вводе, что довольно хорошо. Если вам нужны более быстрые алгоритмы, вы можете перейти на хешированный ключ (в рамках multi_index). Это дало бы сложность поиска в среднем O(1), но это может произойти за счет немного более высокой схемы памяти (проверьте документы для точных спецификаций). Второй подпоиск по заданному имени может стать линейным, если диапазон не отсортирован (не уверен, проверьте документы). Вы должны указать, какая версия лучше всего подходит для вашего приложения. - person TemplateRex; 20.07.2013