这里记录一些我认为初次接触STL时需要知道的一些点,各种API的使用去网上下载一份文档边写变查就行了【写的时候重要的是要知道这个模板存在这么一个操作】。。。
vector string stack什么就比较简单了,了解一下vector长度是倍增变化的即可【空间用完后以原来的1.5倍或2倍重新申请】
priority_queue
其实就是堆,默认是大根堆,小根堆可以直接这样写priority_queue<int,vector<int>,greater<int>> q;
【greater的作用可以这样记:当想要反转STL容器的比较方式时就可以传入这个参数】
为了方便最好还是直接记住,如果不想记,可以每次将插入的数都变成他的相反数(大小关系就反过来了,变相处理成小根堆),取出的时候再乘个-1变回来就行
deque
deque(双端队列),功能很多很强大,但是效率低,很慢,一般不用
pair
pair底层就是一个结构体,可以将pair当成结构体来用,一般存一个二元组(多元也行,pair套pair,疯狂套娃);
并且他已经帮你实现好了比较功能(第一关键字优先),写法又很简洁,省很多代码
set、multiset、map、multimap
基于AVL平衡二叉树(具体来说是红黑树),内部有序
其中虽说数组是int映射到其他类型,是特殊的map,但数组支持随机存取是O(1)的,map查找是O(logn)的【树高logn】
unorder_set、unorder_multiset、unorder_map、unorder_multimap
基于哈希实现,增删改查等大部分操作的复杂度都是O(1),但因为内部无序,故不支持lower_bound()和upper_bound(),也不支持迭代器的加或减【即所有和排序相关的操作都不行,享受好处就要付出代价hh 】
bitset
压位。bitset存储二进制数位。就像一个bool类型的数组一样,但是有空间优化——bool型元素占1B,bitset中的一个元素只需要1bit,相对于bool来说优化了八倍。存一个10000*10000的bool矩阵,直接存就超出空间限制,此时就可以用bitset来存。
一般使用中可以把bitset看成数组,每个元素只占1bit,支持与或非异或取等操作
一般来说bitset初始化就需要设置大小,如bitset<32> a;
就表示a中存了32个二进制位