Container
Feb 10th, 2020 - Now
Container
Vector
Operations | Meanings |
---|---|
constructors | create vectors and initialize them with some data |
operators | compare, assign, and access elements of a vector |
assign | assign elements to a vector |
at, index | returns an element at a specific location |
back | returns a reference to last element of a vector |
begin | returns an iterator to the beginning of the vector |
capacity | returns the number of elements that vector can hold |
clear | removes all elements from the vector |
empty | returns true if the vector has no elements |
end | returns an iterator to the first element of a vector |
erase | remove elements from a vector |
front | returns a reference to the first element of a vector |
insert | inserts elements into the vector |
max_size | returns the maximum number of elements that vector can hold |
pop_back | removes the last element of a vector |
push_back | add an element to the end of the vector |
rbegin | returns a reverse iterator to the end of the vector |
rend | returns a reverse iterator to the beginning of the vector |
reserve | sets the minimum capacity of the vector |
resize | changes the size of the vector |
size | returns the number of elements in the vector |
swap | swaps the contents of this vector with another |
Constructor 相关
常用函数
排序
遍历访问
修改内容 访问下标方式:
迭代器方式:
去除重复值
e.g.
为什么扩容选择 1.5X or 2X https://www.drdobbs.com/c-made-easier-how-vectors-grow/184401375 https://www.zhihu.com/question/36538542/answer/67929747 由于扩容时会发生空间的重新配置,因此指向原vector的迭代器会失效, 因此注意当迭代器遍历的时候尽量不要插入新数据
vector 还提供 reference front() 和 reference back() 函数, 返回第一个/最后一个值的引用,因此 v.front() 和 *v.front() 值是一样的
erase() 会引起数据的拷贝
List
List 内部指针为 void* 类型指针,且有 prev 和 next,是一个双向链表 因此迭代器返回的是 bidirectional iterator
由于 List 不会引起空间的重新配置,因此在插入和拼接时不会发生迭代器失效 内部对迭代器的 ++/-- 进行了运算符重载使得其向前向后移动更加方便
List 内部刻意内置了一个空接点 node 并指向自身成环,这样的好处是:
一个 node 即可表示整个链表
node 所在位置即链表的 end(),更加符合前闭后开区间的要求
判断 empty() 更加方便:node->next == node
List 的 insert 会 insert 到当前迭代器的位置上,从结果来看即从迭代器开始数据后移 如: 1,2,3,4,5 在 *(ite)=3 时 insert(ite, 0) 会得到 1,2,0,3,4,5 的结果
Unique 操作是 移除连续且相同的值,对于不连续的值无法删除 如: 1,2,3,3,4,3 unique 操作后得到 1,2,3,4,3
transfer(iterator position, iterator begin, iterator end) 迁移操作是内部非公开函数 用来辅助 List 的 splice, merge, reverse, sort 等 具体作用是将 [begin(), end()) 的值 移动 插入到 position 处 由于 STL::sort 仅支持 RandomAccessIterator 因此需要调用自己的 member function list.sort() list.sort() 深度解析:https://www.cnblogs.com/avota/archive/2016/04/13/5388865.html
deque
双向 vector,实现极其繁琐,本质为维护指向buffer的指针,在buffer中进行操作 相比于 vector 而言,在前端插入不会引起数据的移动,作为 stack 和 queue 的底层支持 但是排序操作会非常费时,考虑到不同的 buffer 之间的指针的移动
stack & queue
stack:先进后出,底层用 deque,禁用了其前端出入的特性 queue:先进先出,底层用 deque,禁用了其前端入后端出的特性 两者都可以用 list 作为底层实现,方式为 stack<int, list> 两者都不提供迭代器,因为只有单一出口方式 stack:top() 返回顶部的值,pop() 无返回值 queue:front() 返回前端的值,back() 返回后端的值,push() 将元素从后端加入,pop() 将元素从前端取出
Priority_queue
Operations | Meanings |
---|---|
constructors | create priority_queue and initialize them with some features |
empty | returns true if the vector has no elements |
size | returns the number of elements in the vector |
pop | removes the top element of a priority queue, no return value |
push | adds an element to the end of the priority queue |
top | returns the top element of the priority queue |
排序
map/unordered_map
两者的对比:
特性 | map | unordered_map |
---|---|---|
内部组织 | 红黑树 | 哈希表 |
组织特性 | 自动排序 | 插入查找迅速 |
运行效率 | 较低 | 较高 |
占用内存 | 较低 | 较高 |
时间大头 | 查询删除 | 插入 |
使用场景 | 要求内部有序稳定的查找速率,内存需要考虑 | 不需要容器内有序,快速查找删除,不担心内存占用 |
RB_tree
红黑树查找的时间复杂度为 O(lgn) 的证明: https://blog.csdn.net/cxyj666/article/details/88636854
hash_table
桶+红黑树解决哈希冲突
multimap/multiset
允许出现重复 key 的 map/set,区别在于底层调用了 insert_equal() 而不是 insert_unique()
Map
Operations | Meanings |
---|---|
begin | returns an iterator to the beginning of the vector |
clear | removes all elements from the vector |
count | returns the number of occurrences of key in the map |
empty | returns true if the vector has no elements |
end | returns an iterator to the first element of a vector |
equal_range | pair<iterator, iterator> equal_range( const key_type& key ) return two iterators one to the first element that contains key another to a point just after the last element that contains key. |
erase | remove elements from a vector |
find | returns an iterator to key if found or an iterator to the end of the map if not found |
insert | inserts elements into the vector |
key_comp | returns the function that compares keys |
lower_bound | returns an iterator to the first element which has a value greater than or equal to key |
max_size | returns the maximum number of elements that vector can hold |
rbegin | returns a reverse iterator to the end of the vector |
rend | returns a reverse iterator to the beginning of the vector |
size | returns the number of elements in the vector |
swap | swaps the contents of this vector with another |
upper_bound | returns an iterator to the first element in the map with a key greater than key. |
value_comp | returns the function that compares values |
Map 的内部使用红黑树实现,保证了时刻的有序性,所以其自带用比较函数实现的一些功能,如: lower_bound()
和 upper_bound()
。特别要注意不要被英文名弄乱,lower_bound()
其实就是大于等于,upper_bound()
就是大于。
在 Leetcode No.699 中使用到 lower_bound() 来寻找最前相交的方块。
STL_Feature
iterator & reverse_iterator
迭代器和反向迭代器 他们居然不是同一个类 在实现上面反向迭代器完全就是根据迭代器实现的,反向迭代器从尾部元素开始,到首元素的前一个(空元素)结束,反向迭代器++相当于内部维护的迭代器--。 但是,因为 reverse_iterator 和iterator 不是一个东西,所以很多地方传入的参数需要的是 迭代器类型,而不是 反向迭代器类型,就需要通过新建一个迭代器然后取遍历到达反向迭代器所指元素。
具体使用的话在 LeetCode 218 SkyLine 中用过一次。
使用 iterator 安全删除容器元素
当我们想要在遍历的时候删除容器内的元素时,由于对iterator的特性不熟悉容易导致iterator乱飘出现漏删或者跳跃的问题,这里统一一下方法:
it++ 的操作既保留了当前需要删除的迭代器指向的副本,又将it指向了正确的下一个迭代器的位置,美哉。
Reference
《CPP STL Reference Manual》
Algorithm
lower_bound & upper_bound
lower_bound 插入使得依然有序的最早位置 upper_bound 插入使得依然有序的最晚位置 E.g. 1 2 2 2 3 插入 2 lower_bound: 1 | 2 2 2 3 upper_bound: 1 2 2 2 | 3 Caution: 自定义comp函数要严格小于,小于等于会出现问题
sort
https://mp.weixin.qq.com/s/6h1R6UoDDZwfIkBEAt63ew 包含 __introsort_loop 内省排序 和 __final_insertion_sort 插入排序 内省排序会根据元素的长度给出一个快速排序的深度限制 超过深度限制时会直接使用堆排序结束剩下的部分 当内省排序的数组长度小于 threshold==16 时返回给插入排序解决剩下的部分 快速排序使用了尾递归的方式减少了一半的递归调用,具体地只对后半部分进行递归操作,前半部分留给while循环操作 堆排序函数详解 https://www.jianshu.com/p/22fe785d607b copy_backward也是一种整体移动的优化,避免了one by one的调整移动,底层调用memmove来高效实现。
Last updated