常见容器底层

常见容器底层

各种语言下,常见容器底层整理。

参考:

C++ STL容器底层数据结构总结 - 简书 (jianshu.com)

C++面试进阶(STL底层数据结构特点及实现) - 知乎 (zhihu.com)

1、C++

vector

其底层数据结构是数组,由于能动态扩容,所以也称动态数组

特点:

  • 随机访问:$O(1)$

  • 随机插入删除: $O(n)$,中间插入会引起后面数据的拷贝,尾部可快速增删

  • 扩容规则:

    • 新建时初始化一片空间
    • 插入元素引起扩容的时候,gcc会申请2倍的空间,拷贝原有数据
    • 释放原来空间
  • 在进行迭代器相关的修改操作时(包括扩容),所有迭代器和指针引用都会失效

map & multimap & set & multiset

map提供一对一key-value的数据处理能力;set可以理解为关键字即值,即只保存关键字的容器。

与multi的区别在于,multi允许关键字重复,而上面2个不允许重复。

底层数据结构均为红黑树,可以参考[教你透彻了解红黑树](The-Art-Of-Programming-By-July/03.01.md at master · julycoding/The-Art-Of-Programming-By-July (github.com))。

特点:

  • 访问、查找、删除:$O(logn)$

unordered_map & unordered_multimap & unordered_set & unordered_mutiset

顾名思义,以上容器是无序的,所以底层实现为哈希表,因此其查找时间复杂度理论上达到了O(n)

特点:

  • 访问、查找、删除:$O(1)$,但是实际上要考虑碰撞的问题

2、Go

Go 语言不添加其他包的话,只提供了一个 map 容器,不过其他容器适配器之类可以用万能的数组切片实现

map

底层数据结构是哈希表

特点:

  • 访问、查找、删除:$O(1)$
作者

SukiEva

发布于

2021-11-02

更新于

2021-12-22

许可协议

CC BY-NC-SA 4.0

评论


取次花丛懒回顾,半缘修道半缘君。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×