c++ - C++ 中 std::map 的内存分配和工作

Question

我正在阅读有关 map C++ 字典实现的信息。我在网上某处读到一段代码，其中包含以下几行。

map <int, int> A[100005];
A[1][2]=1;

请您解释一下内存是如何分配的。是和二维数组一样还是在插入的时候动态增加。

在给定第二行代码的情况下， map 中的插入是如何发生的。

Answer 1

std::map 通常是自平衡二叉搜索树¹。这是一个基于节点的数据结构，与数组完全不同。通常，数据是动态分配的。你在这里有什么:

map <int, int> A[100005];

是一个具有自动存储功能的映射数组，因此是一个包含 100005 个二叉搜索树的普通数组，在退出声明它的范围时会被销毁。

所以这个

A[1][2]=1;

正在将键值对 (2,1) 添加到数组中的第二个映射。

^{C++标准并没有规定一个std::map究竟应该如何实现，而是对各种操作的复杂度和迭代器的有效性提出了条件，这意味着它确实被实现了作为自平衡 BST，通常是 red-black tree .}