Hexo

STL基础

六大部件

分配器：为容器分配内存

迭代器：算法只能通过迭代器访问容器

容器

Array

定长数组

_M_instance：指向数组首元素的指针（int a[10]的a）

iterator为指针，traits通过指针特化处理

Vector

变长数组

start（4B）：指向第一个元素的指针

finish（4B）：指向最后一个元素的下一个指针

end_of_storage（4B）：容器申请的内存空间的最后一个元素的下一个地址

若内存空间不够则申请当前空间两倍的空间

iterator为指针，traits通过指针特化处理

List

双向链表

node（4B）：指向头节点的指针

iterator里的node为指向当前节点的指针

Forward List

单向链表

Deque

双端队列

queue在内存中每个buffer块离散存储，通过map表记录各buffer块的地址

start（16B）：指向首元素的iterator

finish（16B）：指向尾巴元素下一个块的iterator

map（4B）：指向map首元素的指针

map_size：map占用内存的大小

cur：指向当前元素的指针

first：指向当前buffer块首元素的指针

last：指向当前buffer块尾元素下一个块的指针

node：指向map对应元素的指针

Queue

队列

不允许遍历也不提供iterator

可选择list或deque作为底层存储

不可选择vector作为底层存储

Stack

栈

不允许遍历也不提供iterator

可选择list或deque或vector作为底层存储

Set

集合

t：红黑树

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加

Map

键值对集合

t：红黑树

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的

Functors

Todo

Iterator Traits

由于算法需要得到iterator的某些属性，对于非指针iterator的结构包含属性，但对于指针类型无法获取。通过iterator traits对于iterator处理