Editing Associative array (section)

== Ordered dictionary ==
The basic definition of a dictionary does not mandate an order. To guarantee a fixed order of enumeration, ordered versions of the associative array are often used. There are two senses of an ordered dictionary:

* The order of enumeration is always deterministic for a given set of keys by sorting. This is the case for tree-based implementations, one representative being the {{code|<map>}} container of C++.<ref>{{cite web |title=std::map |url=https://en.cppreference.com/w/cpp/container/map |website=en.cppreference.com}}</ref>
* The order of enumeration is key-independent and is instead based on the order of insertion. This is the case for the "ordered dictionary" in [[.NET Framework]], the LinkedHashMap of [[Java (programming language)|Java]] and [[Python (programming language)|Python]].<ref>{{cite web |title=OrderedDictionary Class (System.Collections.Specialized) |url=https://docs.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?view=netframework-4.8 |website=MS Docs |language=en-us}}</ref><ref>{{cite web |title=LinkedHashMap |url=https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/LinkedHashMap.html}}</ref><ref>{{cite web |title=collections — Container datatypes — Python 3.9.0a3 documentation |url=https://docs.python.org/3.9/library/collections.html#collections.OrderedDict |website=docs.python.org}}</ref>

The latter is more common. Such ordered dictionaries can be implemented using an [[association list]], by overlaying a [[doubly linked list]] on top of a normal dictionary, or by moving the actual data out of the sparse (unordered) array and into a dense insertion-ordered one.