数据结构操作效率
| 数据结构 |
查找 |
插入 |
删除 |
遍历 |
| 数组 |
O(N) |
O(1) |
O(N) |
— |
| 有序数组 |
O(logN) |
O(N) |
O(N) |
O(N) |
| 链表 |
O(N) |
O(1) |
O(N) |
— |
| 有序链表 |
O(N) |
O(N) |
O(N) |
O(N) |
| 二叉树（一般情况） |
O(logN) |
O(logN) |
O(logN) |
O(N) |
| 二叉树（最坏情况） |
O(N) |
O(N) |
O(N) |
O(N) |
| 平衡树（一般情况和最坏情况） |
O(logN) |
O(logN) |
O(logN) |
O(N) |
| 哈希表 |
O(1) |
O(1) |
O(1) |
— |
| 栈 |
— |
O(1) |
O(1) |
— |
| 队列 |
— |
O(1) |
O(1) |
— |
| 优先队列（堆） |
— |
O(logN) |
O(logN) |
— |
上表源自:常用数据结构各个常用操作的性能对比
数组与链表的性能分析
|
插入/删除(时间复杂度) |
查询(时间复杂度) |
| 数组 |
O(n) |
O(1) |
| 链表 |
O(1) |
O(n) |
哈希结构
| 集合 |
底层实现 |
是否有序 |
数值是否可以重复 |
十分可以更改数值 |
查询效率 |
增删效率 |
| set |
红黑树 |
有序 |
否 |
否 |
O(logN) |
O(logN) |
| multiset |
红黑树 |
有序 |
是 |
否 |
O(logN) |
O(logN) |
| unordered_set |
哈希表 |
无序 |
否 |
否 |
O(1) |
O(1) |
| 映射 |
底层实现 |
是否有序 |
数值是否可以重复 |
十分可以更改数值 |
查询效率 |
增删效率 |
| map |
红黑树 |
key有序 |
key不可重复 |
key不可修改 |
O(logN) |
O(logN) |
| multimap |
红黑树 |
key有序 |
key可重复 |
key不可修改 |
O(logN) |
O(logN) |
| unordered_map |
哈希表 |
key无序 |
key不可重复 |
key不可修改 |
O(1) |
O(1) |
