手机付费咨询网站建设,婚恋网站开发,搜外网 seo教程,广东公布最新传染了1 C STL类型及实现原理
1.1 顺序容器
容器中的元素为有序排列,可以指定元素插入位置.
1.1.1 vector
顺序存储, 初始化过程会分配一定量空间, 在尾部插入会很快, 但是在中间插入元素, 会把之后所有元素向后平移, 所以较慢(中间删除元素同理). 如果元素个数超过当前限制, 会重…1 C STL类型及实现原理
1.1 顺序容器
容器中的元素为有序排列,可以指定元素插入位置.
1.1.1 vector
顺序存储, 初始化过程会分配一定量空间, 在尾部插入会很快, 但是在中间插入元素, 会把之后所有元素向后平移, 所以较慢(中间删除元素同理). 如果元素个数超过当前限制, 会重新分配更大空间, 再把原容器中所有元素都拷贝到新的容器中.
优点: 支持随机访问(用下标访问), 性能较好缺点: 除了操作尾部元素, 增删中间元素性能较差
1.1.2 deque
同vector类似, 最大的好处是在头尾增删元素性能较好. 其元素存储在一组连续的内存中, 并在一个结构中存储这些内存追踪, 并不是像vector一样元素存在一块连续的内存中.
优点: 支持随机访问(用下标访问), 增删首元素性能好于vector, 缺点: 随机访问性能不如vector, 增删性能不如list.
1.1.3 list
本质是双向链表, 增删元素速度较快, 但是并不支持用下标直接访问元素.
优点: 首尾中间元素增删性能较好.缺点: 不支持随机访问.
1.2 关联容器
容器中的元素插入时无法指定其位置, 如果需要修改元素值时, 不可以直接修改, 需要先找到该元素并删掉, 再把所需的新元素插入. 其内部一般是通过红黑树实现的, 所以增删及查找操作性能较好.
1.2.1 set(multiset)和map(multimap)
内部元素为顺序排好的, set不允许存两个相同的元素, 而multiset同set相比允许存在相同的元素. ,map内部元素为pairkey, value, 其内部是按照key进行排好序的. map不允许存两个相同key值的元素, 而multimap同map相比允许存在相同的key值的元素.
1.2.2 哈希容器 --- unordered_set和unordered_map
STL中基于哈希表原理(https://blog.csdn.net/Michael__Wu/article/details/110480600), 其中unordered_set和unordered_map都是用的开链法解决通过哈希函数获取的哈希地址相同的多个元素的存储问题. 图中的各个链表成为bucket(桶).
1.2.4 (multi)set/map与unordered_set/map对比
由于(multi)set/map的实现原理为红黑树, 所以其查找和增删元素的时间复杂度均为O(log(n)), 而unordered_set/map的实现原理为哈希表, 所以其查找和增删元素的时间复杂度均为O(1). 但是unordered_set/map所占用的内存更高, 且根据元素数量不同, 时间消耗也不一定小于(multi)set/map.
1.3 特殊容器(容器适配器)
在顺序容器的基础上实现, 屏蔽了部分功能, 增加了另一部分功能. 其中queue默认由deque实现, priority_queue默认由vector 实现。priority_queue 是“优先队列”。它和普通队列的区别在于优先队列的队头元素总是最大的——即执行 pop 操作时删除的总是最大的元素执行 top 操作时返回的是最大元素的引用。
1.3.1 stack
1.3.2 queue
1.3.3 priority_queue
1.4 string
2 接口类型
2.1 公共接口
所有的容器类都有以下接口:
int size(): 返回容器对象中所含有的元素的个数.
bool empty(): 返回容器对象是否为空.
2.2 顺序容器
2.3 关联容器
2.3.1 set map
2.3.2 multiset multimap
2.3.3 unordered_set unordered_map
bucket_count() 返回当前容器底层存储键值(对)时使用桶的数量。max_bucket_count() 返回当前系统中unordered_set(unordered_map)容器底层最多可以使用多少个桶。bucket_size(n) 返回第 n 个桶中存储键值对的数量。bucket(key) 返回以 key 为键的键值对所在桶的编号。load_factor() 返回 unordered_map 容器中当前的负载因子。(负载因子 容器存储的总键值对 / 桶数)max_load_factor() 返回或者设置当前 unordered_map 容器的最大负载因子。rehash(n) 尝试重新调整桶的数量为等于或大于 n 的值。如果 n 大于当前容器使用的桶数则该方法会是容器重新哈希该容器新的桶数将等于或大于 n。反之如果 n 的值小于当前容器使用的桶数则调用此方法可能没有任何作用。reserve(n) 将容器使用的桶数bucket_count() 方法的返回值设置为最适合存储 n 个元素的桶数。hash_function() 返回当前容器使用的哈希函数对象。
2.4 特殊容器(容器适配器)
2.4.1 取出一个元素
stack: 只能通过T top();取到栈顶元素的引用queue: 只能通过S.top()返回队头元素的引用priority_queue: 同queue
2.4.2 插入一个元素
stack: 只能通过void push (const T x);在栈顶放入元素queue: 只能通过S.push()在队尾插入元素priority_queue: 同queue
2.4.3 删除一个元素
stack: 只能通过void pop();弹出栈顶元素queue: 只能通过S.pop()弹出队首元素priority_queue: 同queue
3 迭代器(特殊容器: stack、queue 和 priority_queue 没有迭代器)
3.1 迭代器种类
正向迭代器 容器类名::iterator 迭代器变量;(用的最多)常量正向迭代器 容器类名::const_iterator 迭代器变量;反向迭代器 容器类名::reverse_iterator 迭代器变量;常量反向迭代器 容器类名::const_reverse_iterator 迭代器变量;
3.2 用法
假如一个正向迭代器变量为iter.
*iter 取iter指向的元素iter 指向下一个元素
