C++中map的内存占用大O复杂度是多少

核心结论 #

你混淆了时间复杂度与空间（内存）复杂度的概念，你看到的官方文档说明全部指向map构造操作的时间开销，和内存占用没有关联。

C++ 标准要求map为有序关联容器，业界普遍以红黑树作为其底层实现，它的内存占用为O(n)：每个元素对应一个红黑树节点，节点除存储key、value外，仅额外包含固定大小的指针、颜色标记等元数据，单节点额外开销不随元素总数n变化，因此总内存占用和数组同属线性复杂度，只是常系数远高于数组。

官方文档内容释义 #

你截取的文档内容描述的完全是构造map的时间开销：

空构造函数(1)和移动构造函数(4)的复杂度为常数（除非分配器与x的分配器不同）。对于其余情况，如果元素已经按照相同规则排序，迭代器区间拷贝构造的复杂度为线性；如果是未排序序列，复杂度为线性对数(N*logN)（排序、拷贝构造）。

对应逻辑如下：

• 空构造仅初始化容器的元数据结构，移动构造仅转移原有map的资源所有权，都不需要遍历处理元素，因此时间复杂度为O(1)
• 如果输入的迭代器区间元素已经按照map的排序规则完成排序，插入时不需要每次执行O(logn)的节点位置查找，可直接批量构建树结构，总时间复杂度为O(n)
• 如果输入的是未排序序列，每个元素插入时都要在红黑树中查找匹配的插入位置，单次查找时间为O(logn)，n个元素总插入时间就是O(nlogn)

内容的提问来源于stack exchange，提问作者Simon