Замените вектор и хэш-таблицу с помощью Boost.Bimap - PullRequest
Новая
       57

Замените вектор и хэш-таблицу с помощью Boost.Bimap

8 голосов
/ 16 ноября 2010

Я собираюсь заменить строку сопоставления vector<string> и boost::unordered_map<string, size_t> на индексы в первом на boost::bimap.

Какой экземпляр bimap следует использовать?До сих пор я придумал 

typedef bimap<
    unordered_set_of<size_t>,
    vector_of<string>
> StringMap;

, но я не уверен, изменил ли я сейчас типы коллекций.Кроме того, мне интересно, стоит ли менять коллекцию отношений типа .vector_of_relation будет моим лучшим выбором, или set_of_relation, или просто пойдет по умолчанию?

1 Ответ

4 голосов
/ 04 июня 2011

Чтобы получить разметку между size_t и std :: string, где у вас есть ~ константа (вплоть до стоимости хеширования и любых потенциальных столкновений), вам нужно использовать unordered_set_of: 

#include <boost/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <string>
#include <iostream>
#include <typeinfo>

int main(int argc, char* argv[]) {

  typedef boost::bimap< boost::bimaps::unordered_set_of<size_t>, boost::bimaps::unordered_set_of<std::string> > StringMap;
  StringMap map;
  map.insert(StringMap::value_type(1,std::string("Cheese")));
  map.insert(StringMap::value_type(2,std::string("Cheese2")));

  typedef StringMap::left_map::const_iterator const_iter_type;
  const const_iter_type end = map.left.end();

  for ( const_iter_type iter = map.left.begin(); iter != end; iter++ ) {
    std::cout << iter->first << " " << map.left.at(iter->first) << "\n";
  }

}

, возвращает: 

1 Cheese
2 Cheese2

unordered_set - это расширенная версия набора, которая использует хеш-таблицы вместо деревьев для хранения элементов, см. Boost Unordered docs .

Просмотр комментариев от одногоиз примеров bimap в пример Bimap , у нас есть:

Вид левой карты работает как std :: unordered_map , учитывая имястрана, которую мы можем использовать для поиска населения в постоянное время

...