STL容器是个神奇的东西，今天学习图论算法的时候发现算法思想并不难理解，可是紫书上大量的STL容器代码着实令人头疼，只好先去学一下STL容器。
algorithm库的函数就不多说了，之前反复用过的，而且对于OIer来说非常顺手，因为其时间复杂度和自己手打的无异。
vector不定长数组：操作：clear(), 清空；empty(), //判断vector是否为空；push_back(), pop_back() //从末尾插入或弹出；insert() O(N) //插入元素，O(n)的复杂度；erase() O(N) //删除某个元素，O(n)的复杂度。
set集合：原理： 红黑树，一种平衡的二叉排序树insert() O(logn)。操作：erase() O(logn)；find() O(logn) ；lower_bound() O(logn) 查找第一个不小于k的元素；upper_bound() O(logn) 查找第一个大于k的元素；equal_range() O(logn) 返回pair。
map映射：原理：红黑树。操作： insert() O(logn)；erase() O(logn)；find() O(kn) 找不到返回a.end()；lower_bound() O(logn) 查找第一个不小于k的元素；upper_bound() O(logn) 查找第一个大于k的元素；equal_range() O(logn) 返回pair。
priority_queue优先队列：原理： 堆。操作：push() O(n)；pop() O(n)；top() O(1)。
有些STL函数复杂度很大就要考虑换种方法了，比如find()的复杂度比BruteForce还慢，那么就考虑使用线段树或者hash；
复杂的STL就不管了，STL容器的原理我也并不打算花时间深入了，就把这些当做模板记下来算了。。。
评论 (0)
