Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

Hash - таблица - C++

21.06.2013, 20:46. Просмотров 782. Ответов 11
Метки нет (Все метки)

Собственно всегда считал, что map - обычная хеш-таблица, оказалось нет, это какое-то древовидная упорядоченная хэш-таблица (без понятия, как это, но в общем сложность O(logN) на вставку, удаление и поиск.
Для моей задачи было бы предпочтительнее использовать обычную хеш-таблицу со сложностью O(1).
Вопрос: есть ли она (хеш-таблица с O(1) ) в STL и что за "древовидная упорядоченная" map?
Пожалуйста, не говорите, что ручками написать несложно хеш-таблицу обычную >_<
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 20:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Hash - таблица (C++):

Hash+++ - C++
Скажите пожалуйста где скачать Hash subj и Hash on coure it

Std::hash<.> - C++
а для чего конкретно он применяется? читал на с++/reference, не особо понял...

PERFECT HASH FUNCTION - C++
Вопрос таков, подскажите хэш функцию: формат AcccAA- где A-заглавные буквы,c-цифры. всего 1500 сегментов. Мин сумма символов 339 и...

списки, вектора, map, Hash - C++
интересует информация о следующих &quot;типах&quot; std::vector и std::deque Списки, деревья std::list, std::set, std::map, hash_set, hash_map ...

Перегрузить операторы = и [] для hash - C++
есть оператор который возвращает значение по ключу, как правильно написать оператор = для возможности писать такое hash = &quot;Moto...

Консольный HASH под *nix - C++
Приветствую! Есть задачка выдавать некий HASH в консоли. например как это делает PING, что бы в командной строке писали &quot;my_func...

11
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,018
21.06.2013, 20:50 #2
@nexen, она реализована на К.Ч. деревьях - бинарные деревья с автобалансировкой. Можете почитать про них на досуге где-нибудь.

hash

Добавлено через 2 минуты
std::unordered_set на ней основан, поиск в среднем за O(1)
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.06.2013, 07:31  [ТС] #3
@MrGluck, но та ссылка, что вы дали, рассказывает о функции, что считает хэш, а не о контейнере, который позволяет по ключу (хешу) получить элемент/ы
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,018
22.06.2013, 18:31 #4
@nexen, std::hash_set и std::hash_map но это из С++11
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.06.2013, 18:49  [ТС] #5
@MrGluck, то есть в 3-ке нету хеш-таблиц? :0 Вообще?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,018
22.06.2013, 19:04 #6
@nexen, нет. Буст вам в помощь boost/functional/hash.hpp, boost/unordered_set.hpp, насчет hash_set не знаю.
1
Убежденный
Системный программист
Эксперт С++
15633 / 7143 / 1130
Регистрация: 02.05.2013
Сообщений: 11,582
Записей в блоге: 1
Завершенные тесты: 1
22.06.2013, 19:13 #7
Цитата Сообщение от nexen Посмотреть сообщение
то есть в 3-ке нету хеш-таблиц?
По стандарту - нет. Но в некоторых реализациях хэш-таблицы все же есть.
Например, в Microsoft C++ Compiler им уже лет десять от роду, не меньше.
Правда, они не стандартны, так что переносимость не гарантируется.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.06.2013, 19:17  [ТС] #8
@Убежденный, @MrGluck, а у boost разве переносимость гарантируется?
0
Убежденный
Системный программист
Эксперт С++
15633 / 7143 / 1130
Регистрация: 02.05.2013
Сообщений: 11,582
Записей в блоге: 1
Завершенные тесты: 1
22.06.2013, 19:20 #9
Цитата Сообщение от nexen Посмотреть сообщение
а у boost разве переносимость гарантируется?
Еще как !
Взято отсюда: http://www.boost.org/users/history/version_1_53_0.html
Compilers Tested

Boost's primary test compilers are:
Linux:

GCC: 4.1.2, 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.2

GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.2

Intel: 11.1, 12.1

LLVM Clang: 2.8

LLVM Clang, with libc++: 3.2
OS X:

GCC: 4.4.7

GCC, C++11 mode: 4.4.4

Intel: 11.1, 12.0
Windows:

Visual C++: 9.0, 10.0
FreeBSD:

GCC: 4.2.1, 32 and 64 bit

Boost's additional test compilers include:
Linux:

Cray: 4.6.1

Clang: from subversion

LLVM Clang, with libc++: 3.2

GCC: 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.1

GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.1, 4.7.2

pgCC: 11.9

Intel: 10.1, 11.1, 12.1

Intel, C++11 mode: 13.0.1

Visual Age:
OS X:

Clang: from subversion

Clang, C++11 mode: from subversion

Intel: 11.1, 12.0

GCC: 4.4.7

GCC, C++11 mode: 4.4.4
Windows:

Visual C++: 10.0, 11.0

Visual C++ with STLport: 9.0

Visual C++, Windows Mobile 5, with STLport: 9.0
AIX:

IBM XL C/C++ Enterprise Edition: V12.1.0.1
1
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,018
22.06.2013, 19:35 #10
@nexen, а как вы думаете, какая переносимость у кроссплатформенной библиотеки?
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
22.06.2013, 20:52  [ТС] #11
@MrGluck, ну мало ли что..
0
Jupiter
Каратель
Эксперт С++
6556 / 3977 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
22.06.2013, 21:13 #12
Цитата Сообщение от nexen Посмотреть сообщение
ну мало ли что..
что?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2013, 21:13
Привет! Вот еще темы с ответами:

multi-hash -массив с несколькими индексами - C++
Возможно ли? Для примера, hash_mas == hash_mas == hash_mas А для разнотипных ключей (индексов)? hash_mas == has_mas == has_mas ...

Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017) - C++
Вот код, для наглядности (cyberforum.ru - не сохраняет оригинал кода! может не компилироваться) комментарии не удалял... #include...

Что такое hash-таблицы, и зачем они нужны? - C++
Обьясните пожалуста по простому что такое хеш таблици и зачем они надо... пытался разобратся с ними сам, но ничего не получилось....

Error C2338: The C++ Standard doesn't provide a hash for this type - C++
Хеш таблицы в руках впервые, необходима неупорядоченность. #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;string&gt; #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Yandex
Объявления
22.06.2013, 21:13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru