[Uneex] GCC STL в 4.0: где hash_map?
Vladimir Prus
ghost на cs.msu.su
Чт Май 4 11:30:36 MSD 2006
On Wednesday 03 May 2006 14:43, Aleksey Fedoseev wrote:
> >>Лично мне проблема кажется надуманной. Написать свой контейнер для
> >>хэш-таблицы на основе готовых stl-контейнеров - дело 10 минут.
> >
> > Вы писали? Мне кажется это утверждение надуманным. Я уже проходил такое:
> > "да тут работы на 10 минут"
>
> Вот самый простой пример.
Мне кажется, что хотя приведенная реализация впролне пригодна для
использования, она все таки не вполне сопоставима по качеству со стандартной
реализацией hash_map.
1. Интерфейс.
Класс не предоставляет никаких итераторов.
2. Реализация.
> const size_t DNS_CACHE_HASH_SIZE = 256;
Использование фиксированного размера делает класс непригодным для
использования как хеш-таблица общего назначения. Кроме этого, использование
числа 256 означает, что из всего хеш-значения используются только младшие 8
бит. Для примера, в STL для размера таблицы всегда используется простое
число.
> bool has(const Key& key) {
> size_t index = make_hash(key);
> const EntryMap& map = hash_table[index];
> EMIter citer = map.find(key);
> if(citer != map.end()) {
> return true;
> } else {
> return false;
> }
> }
Этот метод должен быть обьявлет как const.
> bool find(const Key& key, Entry& entry) {
> size_t index = make_hash(key);
> const EntryMap& map = hash_table[index];
> EMIter citer = map.find(key);
> if(citer != map.end()) {
> entry = citer->second;
Здесь происходит "глубокое" копирование объекта, что может негативно сказаться
на производительности.
> /**
> * Hashe table with entry maps (used for find/add acceleration)
> */
> typedef typename std::map<Key, Value> EntryMap;
> typedef typename EntryMap::const_iterator EMIter;
> std::vector<EntryMap> hash_table;
Классическое решения для хеш-таблиц это вектор, в каждом элементе которого
находится список пар (ключ/значение). Использование std::map вместо списка
несколько странно. Если количество элементов в std::map мало, то от него мало
проку. Если количество элементов в std::map велико, то более эффективно будет
увеличить размер хеш-таблицы.
- Volodya
Подробная информация о списке рассылки Uneex