Объект словаря/Хеш-таблицы в C++?
Я ищу реализацию HashTable или Словаря в C++, который имеет схожую функциональность к той в C#? STL содержит объект как это и как я использовал бы его?
4 ответа
На самом деле, чтобы быть точно таким же, как .NET Dictionary / Hashtable, вам нужно hash_map или unordered_map ( std :: map реализован как двоичное дерево), hash_map является расширением SC ++ L. Большинство известных мне компиляторов поставляются с hash_map , а boost, очевидно, имеет unordered_map , пока C ++ 0x не станет доступен во всех компиляторах, так что вы должны просто иметь возможность использовать его без беда.
STL std :: map может использоваться для создания словаря. std :: map обычно реализуется как дерево поиска, а не хеш-таблица. Это означает, что и поиск, и вставка имеют другие характеристики производительности, чем C # HashMap - для очень больших карт средний поиск будет медленнее, особенно если объекты на карте фрагментированы в памяти.
В TR1 нового стандарта C ++ у вас есть std :: tr1 :: unordered_map и std :: tr1 :: unordered_multimap , которые обычно реализуются с использованием хэша. стол. Если ваш компилятор не предоставляет эти библиотеки, вы можете использовать реализацию из http://www.boost.org/ .
Еще одна альтернатива - sparse_hash от Google.