Самый быстрый предварительно упакованный поиск пары ключ-значение - PullRequest
Новая
       9

Самый быстрый предварительно упакованный поиск пары ключ-значение

0 голосов
/ 10 марта 2011

Я хотел бы реализовать следующую структуру данных в c ++ (псевдокод): 

Map<Integer, Integer>    // Key->Value pairs

Map.put(1,6);
Map.put(2,5);
Map.put(6,89);
Map.put(7,23);
... etc ...

Map.get(2) .... returns 5

Другими словами, учитывая пары целых чисел, где одно из них является ключом поиска, чтосамая быстрая реализация библиотеки, которая позволяет мне извлечь значение из одного из ключей?Поиск значения Value-> Key в обратном направлении не требуется.

Размер этой карты, вероятно, будет порядка 10 000 элементов.

Я предполагаю, что поиск в двоичном дереве даст самый быстрый поиск.время поиска?Является ли std: map лучшим инструментом для использования?Boost представляет какие-нибудь альтернативы?

1 Ответ

6 голосов
/ 10 марта 2011

Используйте unordered_map (hashmap) или map (двоичное дерево) - скорее всего, unordered_map будет быстрее. Кроме того, если значение вашего ключа ограничено 10000, vector<int> гарантирует поиск в постоянном времени - используйте «магическое» значение для векторных элементов, которые должны «отсутствовать».

unordered_map является частью TR1 и c ++ 0x - это не стандарт в c ++ 03. Хотя многие реализации поддерживают это. Boost также имеет unordered_map.

map и vector являются стандартными.

  • map соответствует Java TreeMap
  • unordered_map соответствует Java HashMap
  • vector соответствует Java ArrayList
...