1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 int Visit(int v) // 遍历算子函数 6 { 7     cout << v << " "; 8     return 1; 9 }10 class MultInt // 定义遍历算子类11 {12     private:13     int factor;14     public:15     MultInt(int f) : factor(f){}16     void operator()(int &elem) const17     {18         elem *= factor;19     }20 };21 int main()22 {23     vector<int> L;24     for (int i=0; i<10; i++) 25         L.push_back(i);26     for_each(L.begin(), L.end(), Visit);27         cout << endl;28     for_each(L.begin(), L.end(), MultInt(2));29     for_each(L.begin(), L.end(), Visit);30     cout << endl;31     return 0;32 }

 1 using namespace std; 2 int main() 3 { 4     vector<int> L; 5     for (int i=0; i<10; i++)  6         L.push_back(i); 7     vector<int>::iterator min_it = min_element(L.begin(),L.end()); 8     vector<int>::iterator max_it = max_element(L.begin(),L.end()); 9     cout << "Min is " << *min_it << endl;10     cout << "Max is " << *max_it << endl;11     return 1;12 }

 1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4  5 #include <iostream> 6 #include <vector> 7 #include <algorithm> 8 using namespace std; 9 void Print(vector<int> &L)10 {11     for (vector<int>::iterator it=L.begin(); it!=L.end();it++)12     cout << *it << " ";13     cout << endl;14 }15 int main()16 {17     vector<int> L;18     for (int i=0; i<5; i++) 19         L.push_back(i);20     for (int i=9; i>=5; i--) 21         L.push_back(i);22     Print(L);23     sort(L.begin(), L.end());24     Print(L);25     sort(L.begin(), L.end(), greater<int>()); // 按降序排序26     Print(L);27     return 0;28 }

 1 #include <vector> 2 #include <algorithm> 3 #include <iostream> 4 using namespace std; 5 int main() 6 { 7     // 先初始化两个向量v1 和v2 8     vector <int> v1, v2; 9     for (int i=0; i<=5; i++) 10         v1.push_back(10*i);11     for (int i=0; i<=10; i++) 12         v2.push_back(3*i);13     cout << "v1 = ( " ;14     for (vector <int>::iterator it=v1.begin(); it!=v1.end();it++)15         cout << *it << " ";16     cout << ")" << endl;17     cout << "v2 = ( " ;18     for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)19         cout << *it << " ";20     cout << ")" << endl;21     // 将v1 的前三个元素复制到v2 的中间22     copy(v1.begin(), v1.begin()+3, v2.begin()+4);23     cout << "v2 with v1 insert = ( " ;24     for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)25         cout << *it << " ";26     cout << ")" << endl;27     // 在v2 内部进行复制，注意参数2 表示结束位置，结束位置不参与复制28     copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);29     cout << "v2 with shifted insert = ( " ;30     for (vector <int>::iterator it=v2.begin(); it!=v2.end();it++)31     cout << *it << " ";32     cout << ")" << endl;33     return 1;34 }

 1 begin(), //取首个元素，返回一个iterator 2 end(), //取末尾（最后一个元素的下一个存储空间的地址） 3 size(), //就是数组大小的意思 4 clear(), //清空 5 empty(), //判断vector 是否为空 6 [ ] //很神奇的东东，可以和数组一样操作 7 //举例： vector a; //定义了一个vector 8 //然后我们就可以用a[i]来直接访问a 中的第i + 1 个元素！和数组的下标一模一样！ 9 push_back(), pop_back() //从末尾插入或弹出10 insert() O(N) //插入元素，O(n)的复杂度11 erase() O(N) //删除某个元素，O(n)的复杂度

 1 int main() 2 { 3     int n,i; 4     vector vi; //类似于我们定义一个数组，同 int vi[1000]; 但vector的大小是自动调整的 5     vector ::iterator itr; //两个冒号 6     while (scanf("%d",&n) != EOF) 7         vi.push_back(n); 8     for (i = 0 ; i < vi.size() ; i++)  9         printf("%d\n",vi[i]);10     for (itr = vi.begin() ; itr != vi.end() ; itr++)11         printf("%d\n",*itr);12     return 0;13 }

  1 是的精简版:) //栈，只支持从末尾进出  2 支持push(), pop(), top()  3 是的精简版 //单端队列，就是我们平时所说的队列，一头进，另一头出  4 支持push(), pop(), front(), back()  5 内部实现: 双向链表 //作用和vector 差不多，但内部是用链表实现  6 list  7 支持操作:  8 begin(), end(), size(), clear(), empty()  9 push_back(), pop_back() //从末尾插入或删除元素 10 push_front(), pop_front() 11 insert() O(1) //链表实现，所以插入和删除的复杂度的O(1) 12 erase() O(1) 13 sort() O(nlogn),不同于中的sort 14 //不支持[ ]操作！ 15 内部实现: 红黑树 //Red-Black Tree，一种平衡的二叉排序树 16 set //又是一个Compare 函数，类似于qsort 函数里的那个Compare 函数， 17 作为红黑树在内部实现的比较方式 18 insert() O(logn) 19 erase() O(logn) 20 find() O(logn) 找不到返回a.end() 21 lower_bound() O(logn) 查找第一个不小于k 的元素 22 upper_bound() O(logn) 查找第一个大于k 的元素 23 equal_range() O(logn) 返回pair 24 42 25 允许重复元素的 26 的用法及Compare 函数示例: 27 struct SS {int x,y;}; 28 struct ltstr { 29 bool operator() (SS a, SS b) 30 {return a.x < b.x;} //注意，按C 语言习惯，double 型要写成这样： 31 return a.x < b.x ? 1 : 0; 32 }; 33 int main() { 34 set st; 35 … 36 } 37 内部实现: pair 组成的红黑树 //map 中文意思：映射！！ 38 map //就是很多pair 组成一个红黑树 39 insert() O(logn) 40 erase() O(logn) 41 find() O(logn) 找不到返回a.end() 42 lower_bound() O(logn) 查找第一个不小于k 的元素 43 upper_bound() O(logn) 查找第一个大于k 的元素 44 equal_range() O(logn) 返回pair 45 [key]运算符 O(logn) *** //这个..太猛了，怎么说呢，数组有一个下标，如a[i],这里i 是int 型的。数组可以认为是从int 印射到另一个类型的印射，而map 是一个任意的印射，所以i 可以是任何类型的！允许重复元素, 没有[]运算符 46 内部实现: 堆 //优先队列，听RoBa 讲得，似乎知道原理了，但不明白干什么用的 47 priority_queue 48 支持操作: 49 push() O(n) 50 pop() O(n) 51 top() O(1) 52 See also: push_heap(), pop_heap() … in 53 用法举例: 54 priority_queue maxheap; //int 最大堆 55 struct ltstr { //又是这么个Compare 函数，重载运算符？？？不明白为什么要这么写...反正这个Compare 函数对我来说是相当之神奇。RoBa 56 说了，照着这么写就是了。 57 bool operator()(int a,int b) 58 {return a > b;} 59 }; 60 priority_queue <INT,VECTOR,ltstr> minheap; //int 最小堆 61 1.sort() 62 void sort(RandomAccessIterator first, RandomAccessIterator 63 last); 64 void sort(RandomAccessIterator first, RandomAccessIterator 65 last, StrictWeakOrdering comp); 66 区间[first,last) 67 Quicksort,复杂度O(nlogn) 68 (n=last-first,平均情况和最坏情况) 69 用法举例: 70 1.从小到大排序(int, double, char, string, etc) 71 const int N = 5; 72 int main() 73 { 74 int a[N] = {4,3,2,6,1}; 75 string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”}; 76 sort(a,a+N); 77 sort(str,str+N); 78 return 0; 79 } 80 2.从大到小排序（需要自己写comp 函数) 81 const int N = 5; 82 int cmp(int a,int b)  83 { 84     return a > b; 85 } 86 int main() 87 { 88     int a[N] = {4,3,2,6,1}; 89     sort(a,a+N,cmp);     90     return 0; 91 } 92 3. 对结构体排序 93 struct SS {int first,second;}; 94 int cmp(SS a,SS b)  95 { 96     if (a.first != b.first)  97         return a.first < b.first; 98     return a.second < b.second; 99 }100 v.s. qsort() in C (平均情况O(nlogn)，最坏情况101 O(n^2)) //qsort 中的cmp 函数写起来就麻烦多了！102 int cmp(const void *a,const void *b) {103 if (((SS*)a)->first != ((SS*)b)->first)104 return ((SS*)a)->first – ((SS*)b)->first;105 return ((SS*)a)->second – ((SS*)b)->second;106 }107 qsort(array,n,sizeof(array[0]),cmp);108 sort()系列:109 stable_sort(first,last,cmp); //稳定排序110 partial_sort(first,middle,last,cmp);//部分排序111 将前(middle-first)个元素放在[first,middle)中，其余元素位置不定112 e.g.113 int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};114 partial_sort(A, A + 5, A + 12);115 // 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".116 Detail: Heapsort ,117 O((last-first)*log(middle-first))118 sort()系列:119 partial_sort_copy(first, last, result_first, result_last,120 cmp);121 //输入到另一个容器，不破坏原有序列122 bool is_sorted(first, last, cmp);123 //判断是否已经有序124 nth_element(first, nth, last, cmp);125 //使[first,nth)的元素不大于[nth,last), O(N)126 e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5127 nth_element(A,A+6,A+12);128 Output: 5 2 6 1 4 3 7 8 9 10 11 12129 2. binary_search()130 bool binary_search(ForwardIterator first, ForwardIterator131 last, const LessThanComparable& value);132 bool binary_search(ForwardIterator first, ForwardIterator133 last, const T& value, StrictWeakOrdering comp);134 在[first,last)中查找value，如果找到返回Ture,否则返回False135 二分检索，复杂度O(log(last-first))136 v.s. bsearch() in C137 Binary_search()系列138 itr upper_bound(first, last, value, cmp);139 //itr 指向大于value 的第一个值(或容器末尾)140 itr lower_bound(first, last, value, cmp);141 //itr 指向不小于valude 的第一个值(或容器末尾)142 pair equal_range(first, last, value, cmp);143 //找出等于value 的值的范围 O(2*log(last – first))144 int A[N] = {1,2,3,3,3,5,8}145 *upper_bound(A,A+N,3) == 5146 *lower_bound(A,A+N,3) == 3147 make_heap(first,last,cmp) O(n)148 push_heap(first,last,cmp) O(logn)149 pop_heap(first,last,cmp) O(logn)150 is_heap(first,last,cmp) O(n)151 e.g:152 vector vi;153 while (scanf(“%d”,&n) != EOF) 154 {155     vi.push_back(n);156     push_heap(vi.begin(),vi.end());157 }158 Others interesting:159 next_permutation(first, last, cmp)160 prev_permutation(first, last, cmp)161 //both O(N)162 min(a,b);163 max(a,b);164 min_element(first, last, cmp);165 max_element(first, last, cmp);166 Others interesting:167 fill(first, last, value)168 reverse(first, last)169 rotate(first,middle,last);170 itr unique(first, last);171 //返回指针指向合并后的末尾处172 random_shuffle(first, last, rand)173 //头文件174 #include <vector>175 #include <list>176 #include <map>177 #include <set>178 #include <deque>179 #include <stack>180 #include <bitset>181 #include <algorithm>182 #include <functional>183 #include <numeric>184 #include <utility>185 #include <sstream>186 #include <iostream>187 #include <iomanip>188 #include <cstdio>189 #include <cmath>190 #include <cstdlib>191 #include <ctime>192 using namespace std;