抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

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

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)$,但是实际上要考虑碰撞的问题

Go

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

Map

底层数据结构是哈希表

特点:

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

评论



Modify from Volantis theme Powered by Hexo