有一段时间，这件事让我有点恼火。作为数学对象（函数）的映射默认是“无序的”，作为数据结构（又称关联数组或字典）的映射也是如此（python）。那么，为什么他们选择命名有序映射（通常是二叉搜索树）std::map和映射数据结构（通常是哈希图）std::unordered_map，而std::ordered_map有序映射和std::map映射数据结构更有意义？
为了进行比较，我不确定浏览器如何实现 ES6Map对象（标准似乎只需要亚线性时间操作），但它们只保留插入顺序，因此不是通常意义上的“有序”。
\endgroup
最佳答案
3
简短的回答是：历史原因。
Alexander Stepanov 的哲学始终是来类比。当数学家展示他们的工作时，他们通常从公理开始，然后向前推进。但当他们真正开发他们的工作时，他们通常从有趣的定理开始，然后向后推进。
标准模板库的故事也类似。他认为有趣的算法是第一位的，数据结构及其 API 都是围绕它们设计的。如果算法是通用的，这一点尤其重要。
最终成为标准模板库的库的最早版本（例如 Ada 通用库线性数据结构包）不包括关联容器，例如映射和多映射。值得注意的是，它们在中也没有向 C++ 标准委员会提出。
由于 Ada 通用库和原始标准模板库是围绕算法设计的，因此有趣的算法通常位于单一类型的容器上。例如，当您拥有单一类型的容器时，您或多或少会清楚“迭代器”应该是什么样子。
但关联容器有两种有趣的类型：“键”类型和“值”类型。那么通用算法“迭代”的是什么呢？键？键值对？我们知道 Stepanov 和 Lee 最终决定了什么，但这必须解决。
这只是容器和泛型算法之间的 API。API 的另一个困难部分是程序员应如何向 STL 呈现他们自己的用户定义类型。
C++ 具有用于重载小于和相等测试运算符的原生语法。并且需要先实现这些语法才能编写通用排序算法。与基数查询相比，程序员发现为其用户定义类型提供小于比较非常容易，这就是为什么“库”排序函数往往基于比较而不是基于基数的原因。
在这种情况下，很明显，实现基于比较的关联容器比基于哈希的关联容器更容易，争议更少。哈希表需要设计一个 API 来提供用户声明的哈希函数。与比较不同，C++ 没有“原生”哈希函数支持，因此需要进行设计，而且尚不清楚“正确”的设计应该是什么。
（这有点偏离主题，但同样值得注意的是，研究界也不清楚哈希表上的“通用”算法是否应该以某种方式
早期曾有人将哈希表添加到 C++ 标准库中，或多或少地效仿了 HP 的实现，但为时已晚，无法将其纳入 C++98 标准。与此同时，第三方供应商编写了自己的hash_map实现hash_set（以及多种变体），这些实现大体相似，但微妙地相互不兼容。
Boost 项目由 C++ 委员会成员于 1998 年启动，部分目的是作为测试实验室，用于测试即将添加到 C++ 标准库的新提案。大约在 2003 年，当需要试验哈希表时，Jeremy Maitin-Shepard 选择了unordered而不是hashBoost 的实现，主要是因为没有供应商选择这个名字，所以它们之间不会发生冲突。
Boost的提议最终被纳入TR1，随后又被纳入C++11。
TL;DR 版本：
Perl、Python 和 ECMAScript 等语言都是从数据结构开始，后来才做算法，这就是哈希表获得更简单名称的原因。C++ 都是从算法开始，后来才做数据结构，这就是有序搜索树获得更简单名称的原因。
\endgroup
3
-
\begingroup
有趣的历史。在我看来，在有数据结构支持算法之前就开始算法是没有意义的。很多时候，算法的有效实现在很大程度上取决于数据结构。
\endgroup
– -
1\begingroup
@qwr Stepanov 的关键观察是，算法并不依赖于特定的数据结构，而只依赖于他所谓的“迭代器类别”。快速排序、快速选择等都适用于随机访问容器，因此也适用于随机访问迭代器。同样，对单链表和双链表进行排序可以使用相同的算法。降序排序和升序排序也可以使用相同的算法，只是迭代器是反向的。而像“求和所有元素”这样的算法只需要通用的前向迭代。
\endgroup
–
-
\begingroup
@Pseudonym，这就是为什么 C++ 算法比大多数其他语言更先进、更灵活，但同时使用起来非常麻烦（基于迭代器对，而不是基于容器），而且对于新开发人员来说很难理解。Ranges 库试图让它们更容易使用，但与 Java 流或 C# LINQ 相比，Ranges 本身很难使用。
\endgroup
–
|
历史偶然。 是map批准的原始标准模板库的一部分。 随添加到 C++ 标准库中。std::unordered_map
\endgroup
|
我认为一个主要原因是 astd::map不是有序的，因此称其为 ordered_map 会造成混淆。术语有序映射通常是指按顺序保存项目的数据结构（如 alist或vector），并且还支持按键快速查找。顺序与键类型无关（并且不同的有序映射可能以不同的顺序包含相同的键和值）。
也许你可以调用std::map（sorted_map因为它存储按键排序的项目）
\endgroup
1
-
\begingroup
我会说它是有序的，因为维护的总顺序是在键上。Python 将其集合对象之一称为 OrderedDict，它像您的术语一样保留插入顺序。（显然是为了支持插入顺序和键查找，它有一个双向链接列表和该链接列表的第二个字典……）我完全同意 sorted_map 这个名字，它可能更清楚，但主要观点是，不合格的“映射”是无序/未排序的。
\endgroup
–
|
|