Правильно ли я понимаю std::map и std::unordered_map?

Один вопрос на вопрос.

Да, std::map обычно реализуется в виде дерева, а std::unordered_map обычно реализуется в виде хеш-таблицы. Ни одна из реализаций не является требованием стандарта. См. карта и unordered_map.

Это также зависит от реализации.

@user12002570 user12002570 правильный ли мой вывод на 100%, когда мы говорим о реализации стандарта C++?

@ f877576 f877576 Некоторые/большинство поставщиков компиляторов могут реализовать их так, как вы описываете. Но стандарт C++ не налагает такого требования. Стандарт в основном касается наблюдаемого поведения программы. Детали реализации — это хорошие детали реализации.

Теоретически стандарт не требует какой-либо конкретной реализации, но на практике не существует хорошего способа реализации этих абстрактных типов данных, который существенно отличался бы от хеш-таблицы/сбалансированного дерева.

Тем не менее, @molbdnilo, std::unordered_map, в частности, имеет множество функций, которые как бы предлагают использовать реализацию на основе хеша. Конечно, я никогда ими не пользовался и понятия не имею, можно ли их легко подделать. Кроме того, API имеет хеш-функцию и проверку на равенство... Я думаю, что комитет по стандартам имел в виду конкретные реализации для каждого из своих контейнеров, а затем написал API и другие спецификации, такие как требования к производительности и аннулирование итераторов, вокруг этого...

Использует ли он хеш-функцию? да. Должно ли это быть двоичное дерево поиска? нет

@GeneralGrivance Новое название выглядит вводящим в заблуждение. std::map не использует хеширование, и ОП этого не утверждал.

@Raildex, но если мы реализуем std::map как двоичное дерево поиска, мы не будем использовать хеш-функцию, верно?

@user12002570 user12002570 Я не знаю ни одного правила, запрещающего вопросы типа «да/нет». Некоторым пользователям они не нравятся, и они отрицают правильные ответы, но, AFAIK, они соответствуют теме и могут быть полезны для будущих пользователей.

@user12002570 user12002570 Я бы понизил ответ только «да», потому что это не указано в стандарте. Данный ответ описывает ситуацию. Это хороший пример правильного вопроса «да/нет» и хорошего ответа.

@user12002570 user12002570 Вы не можете закрыть вопрос «да/нет». Близкой причины нет. Текущая причина закрытия неверна. Этот вопрос очень целенаправленный. Это ваше мнение, но я никогда не читал, чтобы вопросы типа «да/нет» были не по теме.

Может быть интересно: текущий уровень реализации std::map — это красно-черное дерево — но, как уже упоминалось, нигде не указано (даже дерево вообще). Вы можете построить дерево внутри массива (корень в 0 и для любого узла, расположенного в n левых/правых дочерних элементах, можно найти в 2\nn+1* и 2*n+2) – это работает до тех пор, пока массив не станет слишком маленьким. ; требуемое тогда перераспределение (O(n)!) нарушает требование O(logn) для вставки!!! Возможно, мог бы работать с базовым активом std::deque, но не буду анализировать дальше...

@ user12002570 Да, технически вы можете проголосовать за закрытие всех вопросов, но это не значит, что эти вопросы не по теме. Вы всегда можете написать «Мне не нравится пользователь или вопрос». Это не делает это веской близкой причиной.

@ChristianStieber - При определении требований комитет наверняка имел в виду возможную реализацию. Однако они не хотели об этом подробно говорить, потому что есть странный шанс, что позже будет изобретен лучший способ.

@user12002570 user12002570 По моему мнению, все вопросы, на которые можно дать полезные, одобренные и хорошие ответы, соответствуют теме.

Итак, если я вас правильно понял, вы полностью согласны со мной, что «std::unordered_map использует хэш-функцию в процессе вставки, чтобы определить, где будет расположен новый вставленный элемент. Однако std::map не использует хеш-функцию в процесс вставки и как определить местоположение нового вставленного элемента», верно?

@ f877576 Да, это правда.

извините за беспокойство, но я нашел эту таблицу, в которой упоминается, что карте не нужна хеш-функция, а unordered_map нужна хеш-функция. Информация в этой таблице полностью верна? @Caleth ссылка на таблицу

@ f877576 f877576 Это почти правильно. Это не обязательно должно быть operator</operator==, это просто то, что используется по умолчанию при сравнении и равенстве соответственно.

@ f877576 f877576 источник, на который вы ссылаетесь, верен, когда вы используете std::map<K, V>, потому что на самом деле это то же самое, что std::map<K, V, std::less<K>, std::allocator<std::pair<const K, V>>>, а std::less - это тип функционального объекта, который сравнивается через <, но вы можете иметь карту с другим сравнением, например. std::map<K, V, std::greater<K>> — это std::map<K, V> в обратном порядке.

Хорошо . (Мне очень жаль, что я вас беспокою, но английский не мой родной язык, поэтому я хочу убедиться) Я отредактировал свой первый комментарий к вашему ответу (std::map не использует хеш-функцию в процессе вставки и определяет местоположение новый вставленный элемент) в (std::map не использует хэш-функцию в процессе вставки и как определить местоположение нового вставленного элемента), но, конечно, это редактирование не меняет того, что вы полностью согласны с моим выводом, который я написал в своем вопросе, да? @Калет

@f877576 для std::map позиция в дереве определяется с помощью функции сравнения

извини, что беспокою тебя. но я студент, поэтому мне нужно ваше подтверждение в последний раз и навсегда. Является ли мой вывод (который я написал в своем вопросе) на 100% точным? @Калет

@ f877576 Это правильно, если вам понятно, что означает «меньше» или «больше».

Вы имеете в виду (std::less) под «меньше» и (std::greater) под «больше», верно? @Калет

@ f877576 верно, аргумент шаблона Compare для std::map<K, V> по умолчанию равен std::less<K>, но вы можете указать другой тип для Compare, например. std::map<K, V, std::greater<K>> — другой тип, с другим порядком. Так что ваше утверждение не является ошибочным, но оно не охватывает все ситуации.

в моем вопросе «я имею в виду метод, с помощью которого определяется местоположение нового элемента в любом двоичном дереве поиска, например.. и т. д.», например, здесь означает, что я имею в виду, что есть другой способ (есть только два способа) а именно: если элемент больше текущего элемента, то идите влево, или если он меньше текущего элемента, то идите вправо. std::less и std::greater представляют собой эти два способа. И определенно, если вы используете созданный вами класс, вам необходимо перегрузить оператор < или >. теперь мой вывод на 100% верен и охватывает любую ситуацию, верно? @Калет

@ f877576 стандарт не указывает, что направления должны быть помечены как «влево» или «вправо». Используется только одно направление сравнения. greater(a, b) вместо этого не оценивается less(b, a).

я не понимаю этот комментарий @Caleth

«std::less и std::greater представляют эти два способа» нет, это все одно сравнение (std::less по умолчанию). Если comp(a, b) истинно, a заказывается перед b. Если comp(b, a) истинно, b упорядочивается перед a. Если ни одно из них не истинно, a равно b. «Иди налево» и «иди направо» применимы только в том случае, если вы рисуете диаграмму, на которой предметы расположены в порядке слева направо. Не требуется, чтобы элементы данных-указателей узлов дерева имели какие-либо конкретные имена.

когда вы сказали: «Если ни одно из них не истинно, a равно b», вы имеете в виду, что если ни одно из них не истинно, a равно b, то один из них заменит другой, когда они вставлены в std::map ( a заменит b или b заменит a, это зависит от того, какой из них будет вставлен первым), верно? @Калет

@f877576 std::map::insert не меняет карту, если ключ уже присутствует. std::map::insert_or_assign делает, как и присвоение результату std::map::operator[]

хорошо, тогда если ни одно из них не верно, a равно b, и в std::map будет вставлен только первый вставленный, верно? @Калет

@f877576 да, если ты звонишь insert

когда я сказал «std::less и std::greater представляют эти два способа», я имел в виду, что если вы хотите, чтобы a упорядочивалось до b, используйте std::less (comp(a, b)) и если вы хотите, чтобы b упорядочивалось перед a используйте std::greater (comp(a, b)) без изменения порядка аргументов (и, насколько я знаю, вы не можете изменить порядок аргументов в comp()). Извините, что продолжаю задавать вам вопросы, но независимо от имен членов данных указателей. теперь мой вывод на 100% верен и охватывает любую ситуацию? @Калет

«100% правильно и охватывает любую ситуацию». Вы можете использовать другие сравнения, кроме std::less и std::greater, например: std::owner_less давайте упорядочим std::shared_ptr по объекту, владельцем которого они являются, а не по объекту, на который они указывают, вы можете написать для std::string компаратор, который выполняет сравнение без учета регистра и т. д.

хорошо . но когда я говорю: «std::unordered_map использует хэш-функцию в процессе вставки, чтобы определить, где будет расположен новый вставленный элемент. С другой стороны, std::map не использует хеш-функцию в процессе вставки и как определить местоположение нового вставленного элемента (std::map использует сравнение (сравнить как std::less или std::greater) в процессе вставки, чтобы определить, где будет расположен новый вставленный элемент) " этот абзац на 100% верен и точно, верно @Caleth

@ f877576 да, это правда

@ f877576 «std::unordered_map использует хеш-функцию в процессе вставки, чтобы определить, где будет расположен новый вставленный элемент». верно, но также вводит в заблуждение - да, при определении используется хеш-функция, но сама хеш-функция не определяет, где будет расположен элемент - корректируется возвращаемое значение хеш-функции - перенос значений выше Bucket_count() обратно в доступные сегменты . Обычно это работает следующим образом: size_t h = Hash(key); size_t bucket_index = h % bucket_count(); но реализации обычно добавляют некоторую оптимизацию производительности.

@Tony Delroy, если я правильно вас понял, вы имеете в виду, что «в std::unordered_map перед использованием возвращаемого значения хеш-функции для определения того, где будет расположен новый элемент, это значение (возвращаемое значение хеш-функции) должно быть скорректировано, чтобы убедиться, что оно (возвращаемое значение хеш-функции) может быть допустимым индексом в массиве. «Вы именно это имеете в виду?

@ f877576: ну, «необходимо отрегулировать, чтобы убедиться, что оно (возвращаемое значение хеш-функции) может быть действительным индексом в массиве» - в качестве подвески, после того, как корректировка больше не является возвращаемым значением хеш-функции», но я Полагаю, вы понимаете, и да, это верно для неупорядоченных контейнеров C++. Ожидается, что хеш-функции возвращают значение типа size_t, но это может быть любое значение size_t; сами хеш-функции не имеют представления, сколько сегментов имеет хеш-таблица, поэтому возвращаемое значение должно быть «сложено» на количество сегментов, чтобы сформировать действительный индекс сегмента.

Когда вы сказали «подвеской, после корректировки больше не является возвращаемым значением хеш-функции», вы имели в виду, что в std::unordered_map после корректировки возвращаемого значения хеш-функции. создается новое значение (это новое значение создается путем выполнения математического процесса над возвращаемым значением хеш-функции), и это новое значение должно быть допустимым индексом в массиве, и это новое значение используется для определения местоположения нового элемента, который вставляется в std::unordered_map @TonyDelroy

вы просто имеете в виду, что мы не можем назвать это новое значение возвращаемым значением хеш-функции, потому что это не возвращаемое значение хеш-функции, а новое значение, хотя это новое значение создается путем выполнения математического процесса над возвращаемым значением хеш-функции, верно? @ТониДелрой

@ f877576 да, верно.

Я правильно понимаю все ваши комментарии? @ТониДелрой

@ f877576: Я так думаю - насколько я могу судить по тому, что ты написал - именно поэтому я написал "да, это правда" ;-).

И, конечно же, std::map не использует хеш-функцию для определения местоположения нового элемента (новый элемент, который вставляется в std::map), а std::map не использует хеш-функцию в Процесс вставки, а std::map не использует хэш-функцию ни в одной операции, верно? @ТониДелрой

@ f877576: единственные хеш-таблицы в стандартной библиотеке C++ — это unordered_set, unordered_map, unordered_multiset и unordered_multimap - никакие другие стандартные контейнеры вообще не используют хеш-функции.