Комментарии 12
Упорядоченная map— это map, которая запоминает порядок элементов. Map можно итерировать для извлечения элементов в том порядке, в котором они были добавлены.
Точно так? А не в порядке возрастания ключей, как это во всех других известных мне языках программирования?
Это где так? Обычно итерация происходит в одном из двух порядков:
В порядке добавления ключей.
В неопределённом порядке, оно же в порядке, в каком данные располагаются в map (т.е. по сути что‐то вроде «в порядке возрастания остатков от деления хэшей на размер map», если не учитывать коллизий).
Оба порядка — это «в каком порядке удобно делать итерацию при данной реализации map», и «в порядке возрастания ключей» удобно делать, только если map — это дерево вроде BTreeMap, а не хэш‐таблица.
Помимо этого есть lua, где таблицы одновременно ещё и массивы и другие языки со схожими идеями, где, в зависимости от ключа, значение окажется либо во внутреннем массиве, либо в хэш‐таблице, но даже у lua порядок никак не гарантируется даже для числовых индексов (вероятно, т.к. вы вполне можете засунуть числовой индекс в хэш‐таблицу, а не в массив).
https://en.cppreference.com/w/cpp/container/map
вот тут например ключи сортируются а не хранятся в порядке добавления. Но это там названо просто map, в то же время в плюсах есть unordered map, где порядок добавления не запоминается.
Но кажется в плане употребления термина Ordered вы правы, потому что сортированные по ключам структуры данных стоит называть с приставкой Sorted, а Ordered это как раз про порядок.
Так например названо в C#, где OrderedDictionary запоминает порядок добавления ключей, а SortedDictionary - сортирует их
По ссылке же:
Keys are sorted by using the comparison function Compare
Не в порядке добавления. А в порядке возрастания ключей в C++.
В C# я думал как раз про SortedDictionary. Все-таки по ключам. В Жаве тоже есть SortedMap, Тоже по ключам.
Кажется вы не поняли мое предложение про плюсы. У меня написано так:
вот тут например ключи сортируются а не хранятся в порядке добавления
В C# Dictionary без Sorted не сортирует по ключам. Интерфейс Map в Java не требует определённого порядка. Если это более скриптовый язык, где словари являются частью основного синтаксиса, то внутри почти наверняка будет хэш‐таблица, которые с сортировкой по ключам не очень дружат.
Собственно под «обычно» я думал скорее про них — я обычно использую Rust или такие скриптовые языки и в Rust есть, к примеру, HashMap и BTreeMap, но у обоих название вида ImplementationMap и нельзя сказать, что есть какие‐то предпочтения на уровне языка или стандартной библиотеки. HashMap, впрочем, используется чаще, потому что за сортировку по ключам вы платите скоростью всех операций в данном случае.
Вероятно автор подсмотрел идею в PHP, где "array", если используется как мапа, запоминает порядок элементов как их добавляли.
Кстати, так и есть:
Не только PHP. Современный Python, Ruby и (могу ошибаться) JavaScript тоже гарантируют итерацию в порядке добавления.
Ruby и Python — да. В javascript похоже засунули в стандарт оптимизацию, используемую для таблиц lua (скорее не саму оптимизацию, но её последствия в части того, как удобнее всего реализовывать итерацию по object): MDN в документации for..in утверждает
The traversal order, as of modern ECMAScript specification, is well-defined and consistent across implementations. Within each component of the prototype chain, all non-negative integer keys (those that can be array indices) will be traversed first in ascending order by value, then other string keys in ascending chronological order of property creation.
Где это написано в собственно спецификации ECMAScript я не нашёл, но в этом тексте написано сначала цифровые индексы по порядку, потом строковые ключи таки в порядке добавления.
Если уж речь зашла про map и Go версии не ниже 1.23, то почему бы сразу не использовать https://pkg.go.dev/iter ? И реализовать совместимость с https://pkg.go.dev/maps , чтобы это можно было "прозрачно" использовать с другим кодом на Go
:-)
Ordered map на Go