STL简析.ppt

next_permutation/pre_permutation 根据当前排列生成上一个或下一个排列 效率高，约是直接回溯的2倍。 int a[4] = {0,1,2,3}, count = 0; do{ count++; }while(next_permutation(a, a + 4)); 其他可能也有用的算法 is_heap, make_heap, push_heap, pop_heap,heap_sort nth_element partition/stable_partition copy / copy_if set_intersection, set_union, set_difference, set_symmectric_difference includes random_shuffle merge, inplace_merge partial_sort binary_search 注意点 效率：用还是不用？如果用，用什么？ 销毁容器前delete容器中通过new获得的指针 使用“交换技巧”来修整过剩容量string().swap(a) 了解相等和等价的区别 a==b 与(!(ab) !(ba)) 严格弱序化: 永远让比较函数对相等的值返回false 避免原地修改set的键 对比map::operator[]和map-insert []先检查存在与否，不存在则插入默认值 erase-remove/erase-unique惯用法 count/find/binary_search/lower_bound/ upper_bound和equal_range的区别 OVER C++ 标准程序库(简体中文).pdf STL_Programmer_Guide.chm Felix_STL整理.rar (有点小错) chaeyeons stl.rar 深入: Effective STL STL源码剖析 Standard Template LibrarySTL简析 By Felix021 @什么是STL Standard Template Library标准模板库 包含可复用的(模板化的)容器、算法等。 容器(最常用的数据结构)：存放数据 序列容器, vector, deque, list, ... 关联容器, map, set, ... *迭代器 算法：处理数据 查找, 排序, 统计, 堆, 集合, 排列... 效率，正确性，可读性，代码速度 什么是模板(Template) 抽象地看待代码，分离出变化的和不变的。 ~不变的：模板 ~变化的：模板参数 template typename T T add(T a, T b) { return (a + b); } ... cout add(1, 2) endl; cout add(1.1, 2.2) endl; 什么是迭代器(iterator) 定义(GOF)：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。 C++ Iterator Input Iterators(只读, e.g. istream_iterator封装cin) Output Iterators(只写, e.g. 封装cout) Forward Iterators(前向, e.g. 单链表) Bidirectional Iterators(双向, e.g. list) Random Access Iterators(双向, e.g. vector) *指针 *iter, iter-elem, iter++, iter--, iter+3 STL中的区间(range) [begin, end) 左闭右开 begin指向第一个元素 end 指向最后一个元素之后的那个空的位置 begin == end 表示空区间 e.g. sort(vec.begin(), vec.end()); sort(arr, arr + n); 比较函数 重载operator bool intgreater(const int a, const int b){ return (a b); } sort(a, a + 5, intgreater); ------------------------ struct T{ int v; bool operator(const T a)const{ return (v a.v); } } = T a, b; if(a b) ... ; 仿函数(functor, 函数对象) 重载()操作符的类 struct cmp{