C++ 中的 std::map 内部是什么数据结构？

What data structure is inside std::map in C++?

提问by Mark

I'm beginner and learning C++ Having hard times to understand std::map concepts, because the code I'm playing with implies that the mapis a search tree, i.e. all the names of std::map objects have *tree in it as well as comments.

我是初学者和学习 C++ 很难理解 std::map 概念，因为我正在玩的代码暗示这map是一个搜索树，即 std::map 对象的所有名称都包含 *tree 作为以及评论。

However after reading this material http://www.cprogramming.com/tutorial/stl/stlmap.htmlI tend to think that std::map has nothing to do with tree or hash.

然而，在阅读了这份材料http://www.cprogramming.com/tutorial/stl/stlmap.html 后，我倾向于认为 std::map 与树或哈希无关。

So I`m confused -- either the variables and comment in the code lie to me, or the subject is more complex then I think it is :)

所以我很困惑——要么是代码中的变量和注释对我说谎，要么主题比我认为的更复杂:)

回答by Manu343726

std::mapis an associative container. The only requirement by the standard is that the container must have an associative container interface and behavior, the implementation is not defined. While the implementation fits the complexity and interface requirements, is a valid implementation.

std::map是一个关联容器。标准的唯一要求是容器必须具有关联的容器接口和行为，没有定义实现。虽然实现符合复杂性和接口要求，但它是一个有效的实现。

On the other hand, std::mapis usually implemented with a red-black tree, as the reference says.

另一方面，正如参考文献所说，std::map通常用红黑树实现。

回答by Emilio Garavaglia

Viewed externally a map is just an associative container: it behave externally as an "array" (supports an a[x]expression) where x can be whatever type (not necessarily integer) is "comparable by <" (hence ordered).

从外部看，地图只是一个关联容器：它在外部表现为“数组”（支持a[x]表达式），其中 x 可以是“可通过 < 进行比较”（因此有序）的任何类型（不一定是整数）。

But:

但：

• Because xcan be any value, it cannot be a plain array (otherwise it must support whatever index value: if you assign a[1] and a[100] you need also the 2..99 elements in the middle)
• Because it has to to be fast in insert and find at whatever position, it cannot be a "linear" structure (otherwise elements shold be shifted, and finding must be sequential, and the requirements are "less then proportional finding time".

• 因为x可以是任何值，所以它不能是普通数组（否则它必须支持任何索引值：如果你分配 a[1] 和 a[100] 你还需要中间的 2..99 个元素）
• 因为它必须快速插入并在任何位置查找，所以它不能是“线性”结构（否则元素应该移位，查找必须是顺序的，并且要求“小于比例查找时间”。

The most common implementation uses internally a self-balancing tree (each node is a key/value pair, and are linked togheter so that the left side has lower keys, and the right side has higer keys, so that seraching is re-conducted to a binary search), a multi-skip-list (fastest than tree in retrieval, slower in insert) or a hash-based table (where each x value is re-conducted to an index of an array)

最常见的实现在内部使用自平衡树（每个节点是一个键/值对，并链接在一起，使左侧具有较低的键，右侧具有较高的键，以便重新进行搜索以二分搜索）、多跳过列表（检索速度比树快，插入速度慢）或基于哈希的表（其中每个 x 值都重新执行到数组的索引）

回答by Adam Wulkiewicz

As chris have written, the standard doesn't define the internal structure of the std::map or std::set. It defines the interface and complexity requirements for operations like insertion of an element. Those data structures of course may be implemented as trees. For example the implementation shipped with VisualStudio is based on a red-black tree.

正如克里斯所写，标准没有定义 std::map 或 std::set 的内部结构。它定义了诸如插入元素之类的操作的接口和复杂性要求。这些数据结构当然可以实现为树。例如，VisualStudio 附带的实现基于红黑树。

回答by user1706047

Map internally uses self-balancing BST . Please have a look on this link.self-balancing binary search trees

Map 内部使用自平衡 BST 。请查看此链接。自平衡二叉搜索树

回答by Napalidon

I would say that if you think of a map as a pair you can't go wrong. Map can be implemented as a tree or a hash map, but the way it is implemented is not as important since you can be sure any implementation is STL is an efficient one.

我会说，如果您将地图视为一对，您就不会出错。Map 可以实现为树或哈希图，但它的实现方式并不重要，因为您可以确定任何实现都是 STL 是一种高效的实现。