Vector

Deque

List

Set

Multiset

map

Multimap

典型内部

结构

dynamic

array

Array of arrays

Doubly

Linked list

Binary tree

Binary tree

Binary tree

Binary tree

元素

Value

Value

Value

Value

Value

Key/value

pair

Key/value

pair

元素

可重复

是

是

是

否

是

对key而言否

是

可随机

存取

是

是

否

否

否

对key而言是

否

迭代器

类型

随机存取

随机存取

双向

双向元素被视为常数

双向元素被视为常数

双向key被视为常数

双向key被视为常数

元素搜寻

速度

慢

慢

非常慢

快

快

对key而言快

对key而言快

快速

安插移除

尾端

头尾两端

任何位置

---

---

---

---

安插移除

导致无效iterators,pointers,

references

重新分配时

总是如此

绝不会

绝不会

绝不会

绝不会

绝不会

释放被移

除元素之

内存

绝不会

有时会

总是如此

总是如此

总是如此

总是如此

总是如此

允许

保留内存

是

否

---

---

---

---

---

交易安全

若失败带

来任何影响

尾端push/pop时

头尾两端push/pop时

任何时候除了排序和赋值

任何时候除了多元素安插

任何时候除了多元素安插

任何时候除了多元素安插

任何时候除了多元素安插