http://blog.csdn.net/jenus1/archive/2008/03/29/2227691.aspx 1 vector 内部实现: 数组 // 就是没有固定大小的数组,vector直接翻译是向量的意思 支持操作: begin(), //取首个元素,返回一个iterator end(), //取末尾(最后一个元素的下一个存储空间的地址) size(), //就是数组大小的意思 clear(), //清空 empty(), //判断vector是否为空 [] //很神奇的东东,可以和数组一样操作 //举例: vector a; //定义了一个vector //然后我们就可以用a[i]来直接访问a中的第i + 1个元素!和数组的下标一模一样! push_back(), pop_back() //从末尾插入或弹出 insert() O(N) //插入元素,O(n)的复杂度 erase() O(N) //删除某个元素,O(n)的复杂度 可以用于数组大小不定且空间紧张的情况 2 deque 类似 //双端队列,两头都支持进出 支持push_front()和pop_front() 是的精简版:) //栈,只支持从末尾进出 支持push(), pop(), top() 是的精简版 //单端队列,就是我们平时所说的队列,一头进,另一头出 支持push(), pop(), front(), back() 3 list 内部实现: 双向链表 //作用和vector差不多,但内部是用链表实现 支持操作: begin(), end(), size(), clear(), empty() push_back(), pop_back() //从末尾插入或删除元素 push_front(), pop_front() insert() O(1) //链表实现,所以插入和删除的复杂度的O(1) erase() O(1) sort() O(nlogn)(logn) 找不到返 //不支持[ ]操作! 4 set 内部实现: 红黑树 //Red-Black Tree,一种平衡的二叉排序树 //又是一个Compare函数,类似于qsort函数里的那个Compare函数,作为红黑树在内部实现的比较方式 insert() O(logn) erase() O(logn) find() O回a.end() lower_bound() O(logn) 查找第一个不小于k的元素 upper_bound() O(logn) 查找第一个大于k的元素 equal_range() O(logn) 返回pair 5 multiset 允许重复元素的 6 map 内部实现: pair组成的红黑树 //map中文意思:印射!! //就是很多pair 组成一个红黑树 insert() O(logn) erase() O(logn) find() O(logn) 找不到返回a.end() lower_bound() O(logn) 查找第一个不小于k的元素 upper_bound() O(logn) 查找第一个大于k的元素 equal_range() O(logn) 返回pair [key]运算符 O(logn) *** //这个..太猛了,怎么说呢,数组有一个下标,如a[i],这里i是int型的。数组可以认为是从int印射到另一个类型的印射,而map是一个任意的印射,所以i可以是任何类型的! 7 multimap 允许重复元素, 没有[]运算符 8 priority_queue 内部实现: 堆 //优先队列 支持操作: push() O(n) pop() O(n) top() O(1) See also: push_heap(), pop_heap() … in 9 hash_map 内部实现: Hash表//内部用哈希表实现的map 重载HashFcn和EqualKey 支持操作: insert(); O(1) earse(); O(1) [ ]; O(1) 1.sort() void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp); 区间[first,last) Quicksort,复杂度O(nlogn) (n=last-first,平均情况和最坏情况) 用法举例: 1.从小到大排序(int, double, char, string, etc) const int N = 5; int main() { int a[N] = {4,3,2,6,1}; string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”}; sort(a,a+N); sort(str,str+N); return 0; } 2.从大到小排序(需要自己写comp函数) const int N = 5; int cmp(int a,int b) {return a > b;} int main() { int a[N] = {4,3,2,6,1}; sort(a,a+N,cmp); return 0; } 3. 对结构体排序 struct SS {int first,second;}; int cmp(SS a,SS b) { if (a.first != b.first) return a.first < b.first; return a.second < b.second; } v.s. qsort() in C (平均情况O(nlogn),最坏情况O(n^2)) //qsort中的cmp函数写起来就麻烦多了! int cmp(const void *a,const void *b) { if (((SS*)a)->first != ((SS*)b)->first) return ((SS*)a)->first – ((SS*)b)->first; return ((SS*)a)->second – ((SS*)b)->second; } qsort(array,n,sizeof(array[0]),cmp); sort()系列: stable_sort(first,last,cmp); //稳定排序 partial_sort(first,middle,last,cmp);//部分排序 将前(middle-first)个元素放在[first,middle)中,其余元素位置不定 e.g. int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5}; partial_sort(A, A + 5, A + 12); // 结果是 "1 2 3 4 5 11 12 10 9 8 7 6". Detail: Heapsort , O((last-first)*log(middle-first)) sort()系列: partial_sort_copy(first, last, result_first, result_last, cmp); //输入到另一个容器,不破坏原有序列 bool is_sorted(first, last, cmp); //判断是否已经有序 nth_element(first, nth, last, cmp); //使[first,nth)的元素不大于[nth,last), O(N) e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5 nth_element(A,A+6,A+12); Output: 5 2 6 1 4 3 7 8 9 10 11 12 2. binary_search() bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp); 在[first,last)中查找value,如果找到返回Ture,否则返回False 二分检索,复杂度O(log(last-first)) v.s. bsearch() in C Binary_search()系列 itr upper_bound(first, last, value, cmp); //itr指向大于value的第一个值(或容器末尾) itr lower_bound(first, last, value, cmp); //itr指向不小于valude的第一个值(或容器末尾) pair equal_range(first, last, value, cmp); //找出等于value的值的范围 O(2*log(last – first)) int A[N] = {1,2,3,3,3,5,8} *upper_bound(A,A+N,3) == 5 *lower_bound(A,A+N,3) == 3 make_heap(first,last,cmp) O(n) push_heap(first,last,cmp) O(logn) pop_heap(first,last,cmp) O(logn) is_heap(first,last,cmp) O(n) e.g: vector vi; while (scanf(“%d”,&n) != EOF) { vi.push_back(n); push_heap(vi.begin(),vi.end()); } Others interesting: next_permutation(first, last, cmp) prev_permutation(first, last, cmp) //both O(N) min(a,b); max(a,b); min_element(first, last, cmp); max_element(first, last, cmp); Others interesting: fill(first, last, value) reverse(first, last) rotate(first,middle,last); itr unique(first, last); //返回指针指向合并后的末尾处 random_shuffle(first, last, rand) Some Others: More container: Rope, Slist, Bitset … More about iterator Memory allocation Function object
|