参考书籍：C++ 标准程序库 - 自修教程与参考手册
基础概念 STL（标准模板库 Standard Template Library）
STL 组件：容器，迭代器，算法
容器：用来管理某类对象的集合。
迭代器：用来在在一个对象群集的元素上进行遍历操作。
算法：用来处理群集内的元素。
STL：将数据和操作分离。数据由容器类别加以管理，操作由可定制的算法定义之。
常见容器 序列式容器与关联式容器 序列式容器 其中每个元素均有固定的位置 ——–取决于插入时机与地点，和元素值无关。如：vector，deque，list
序列式容器 添加元素都用 .push_back () 向尾部添加一个元素。
List 与 deque 还可以使用 .push_front () 向头部添加一个元素，vector 没有是因为效率太差 (所有元素都需要移动)
可通过 i <coll.size () 来遍历
关联式容器 元素位置决定于特定的排序准则，也就是说位置取决于元素的值。如：set，multiset，map，multimap 关联式容器也可被视作特殊的序列式容器
添加元素都用 .insert () 无法使用.push_back () 与 .push_front () 他们在这里毫无意义 因为你无法指定新元素的位置。
需要注意的是 使用 map 或 multimap 添加元素 .insert (make_pair (1,”e”)); 利用辅助函数 make_pair () 是最快的做法
如果你向取出值 使用 pos->first 或 pos->second 也可协作 (*pos).first …
通过 map [“key”] = element 来修改值时 如果 key 拼写出错将会创建一个新的键值对。
Vector Vector 在尾部附加或移除元素非常快速 在中部和头部则比较慢 允许随机存取 （类似顺序表的性质）
Deque Deque 在头部和尾部安插元素都非常快 在中间部分慢
List List 由双向链表实作而成 任何位置安插或删除元素都非常快 但不支持随机存取 读取元素性能较差
迭代器 定义
1 2 C++ list<char>::iterator pos;
pos.begin () : 指向容器的起点 也就是第一个元素
pos.end () : 指向容器的终点 在最后一个元素之后，形成左闭右开区间
[注意 1] 如果使用 const_iterator 则无法改变迭代器常量的值
[注意 2]
1 2 3 C++ for(pos = coll.begin();pos != coll.end();++pos) cout<<*pos;
前置式递增 ++pos 比，后置式递增 pos++ 效率要高 , 后者需要一个额外的临时对象 因为他必须有放迭代器原本的位置并将他返回。
迭代器的分类
双向迭代器（list set map）
随机存取迭代器 （vector deque strings）
[注意 3] 最好使用 pos != coll.end () 而不是使用 pos < coll.end () 遍历，因为 operator < 只有随机存取迭代器才支持，也就是说 list、set、map 都无法运作。
特殊的迭代器 —- 配接器
Insert iterator 安插型迭代器
Stream iterator 流迭代器
Reverse iterator 逆向迭代器
算法 头文件 ： algorithm
更易型算法 —- 删除或重排或修改元素
[注意 4] 如果你需要以单一语句来删除元素请用： Coll.erase(remove(coll.begin(),coll.end(),3),coll.end());
[注意 5] 关联式容器可直接用成员函数 erase 移除元素
[注意 6] 如果高效率是你的最高目标，你应该永远优先选用成员函数
小技巧 1 2 3 4 5 6 C++ // 读入 vector<int> coll((istream_iterator<int>(cin)),(istream_iterator<int>())); // 输出 copy(coll.begin(),coll.end(),ostream_iterator<int>(cout,"\n"));
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 C++ Sort(coll.begin(),coll.end(),cmp); //缺省的是 operator < 所以sort将容器以递增排序 C++ Find(coll.begin(),coll.end(),3); //如果成功 将返回3的位置 否则将返回 .end() C++ Reverse(coll.begin(),coll.end()); //反转区间内的元素 C++ Equal(coll.begin(),coll.end(),coll2.begin(),coll2.end()); //处理多个区间 须保证区间元素个数相等 C++ Coll.erase(remove(coll.begin(),coll.end(),3),coll.end()); //如果你需要以单一语句来删除元素请用： vec.erase(remove_if(vec.begin(), vec.end(), [](int x){return x == 3;}), vec.end()); // 用lambad C++ // 需加头文件 iterator 读入与输出 vector<int> coll((istream_iterator<int>(cin)),(istream_iterator<int>())); //读入 copy(coll.begin(),coll.end(),ostream_iterator<int>(cout,"\n")); // 输出 C++ // for_each 遍历用法 void print(int elem){ cout<<elem<<" "; } for_each(coll.begin(),coll.end(),print);
迭代器的相关辅助函数 1.advance () 可让迭代器向前
1 2 3 C++ advance(pos,3) //前进3 advance(pos.-1) //后退1
2.distance () 处理迭代器之间的距离
1 2 3 4 5 C++ distance(coll.begin(),pos) // 开始到pos的距离 并返回距离 // 早期版本 distance(pos1,pos2,d) // long d = 0; d为long
3.iter_swap () 交换两个迭代器所指的内容
1 2 C++ Iter_swap(coll.begin(),--coll.begin());
迭代器的配接器 1. 逆向迭代器
2. 插入迭代器
1 2 C++ ::back_insert_iterator <vector<int> > iter(coll);
3. 流迭代器
1 2 3 4 C++ ostream_iterator<T> coutPos(cout,”\n”); Istream_iterator<T> cinPos(cin);
仿函数（函数对象） 预定义的仿函数 (详细见 P305)
需包含头文件 include
1 2 3 4 5 6 7 8 9 10 C++ greater<type>() p1 > p2 less<type>() p1 < p2 (默认的仿函数) greater_equal<type>() p1 >= p2 less_equal<type>() p1 <= p2 logical_not/and/or ! p1 / p1 && p2 / p1 || p2
预定义的函数配接器
bind2nd(op,value) op(value,param)
not1(op) !op(param)
not2(op) !op(param1,param2)
配接器实际将一些二元仿函数转换为一元仿函数 它通常将第二参数传给由第一参数指出的二元仿函数作为后者的第二参数 ！
针对成员函数的函数配接器 mem_fun_ref (op) 调用 op 那是对象的一个 const 成员函数
针对一般函数的函数配接器 ptr_fun(op) op(param) op(param1,param2)
部分应用 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 C++ // coll元素都乘10插入coll2 transform(coll.begin(),coll.end(),back_inserter(coll2),bind2nd(multiplies<int>(),10)); // coll元素都乘-1 transform(coll.begin(),coll.end(),coll.begin(),negate<int>()); // coll元素平方 transform(coll.begin(),coll.end(),coll.begin(),coll.begin(),multiplies<int>()); //检查某个int值是否大于42 vector<int>::iterator pos; pos = find_if(coll.begin(),coll.end(),bind2nd(greater<int>(),42)); cout<<*pos<<endl; // 找出第一个为偶数的元素位置 pos = find_if(coll.begin(),coll.end(),not1(bind2nd(modulus<int>(),2))); // 找出第一个为奇数的元素位置 pos = find_if(coll.begin(),coll.end(),bind2nd(modulus<int>(),2));
STL 算法 算法的分类
尾词 _if : 有尾词 if 的算法用来接收仿函数
尾词 _copy：用来表示词算法中，元素不光被操作，还会被复制到目标区间
非变动性算法
变动性算法
移除性算法
遍序性算法
排序算法
已序区间算法
数值算法
最重要的算之一便是 for_each 算法 他将调用者提供的操作施加于每一个元素身上。
例如你可以用 for_each 来打印区间内的每个元素 也可以用来变动元素。
for_each() for_each(beg,end,op)
参数解释：
对区间的每个元素调用 op (elem)
for_each () 如需变动参数 必须以 by reference 方式传递
实例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 C++ void print(int elem){ cout<<elem<<" "; } void square(int &elem){ elem *= elem; } for_each(coll.begin(),coll.end(),square);
非变动性算法 1. 元素计数
count(beg,end,const T& value)
count_if(beg,end,op)
参数解释：
第一形式会计算区间 [beg,end) 中元素值等于 value 的元素个数
第二形式会计算区间 [beg,end) 中令一元判断式 OP (elem) 结果为 true 的元素个数
OP 不应改动传进来的参数 也不能改变自身状态
关联式容器 (set,multisets,maps 和 multimaps) 提供了一个等效的成员函数 count ()
实例
1 2 3 4 5 6 7 8 9 10 11 C++ // 值等于4的元素个数 cout<< count(coll.begin(),coll.end(),4)<<endl; // 为偶数的元素个数 cout<< count_if(coll.begin(),coll.end(),cmp)<<endl; // 大于4的元素个数 cout<<count_if(coll.begin(),coll.end(),bind2nd(greater<int>(),4))<<endl;
2. 最大值和最小值
min_element(beg,end)
min_element(beg,end,op)
参数解释：
如果存在多个最大最小值 则返回的是第一个最大最小值
所有形式都返回区间内最大 / 最小元素的位置
Op 应该用来比较两个元素
如果第一个元素小于第二个元素 应当返回 true
实例
1 2 3 4 5 6 7 8 9 C++ // 可变更 < 符号 bool abls(int elem1,int elem2){ return abs(elem1) < abs(elem2); } // 求绝对值的最大值 cout<<*max_element(coll.begin(),coll.end(),abls);
3. 搜寻元素
搜索第一个匹配的元素
find(beg,end,value);
find_if(beg,end,op);
参数解释：
第一形式返回区间中元素等于 value 的元素位置
第二形式返回区间令一元判断式结果为 true 的第一个元素
如果没有找到匹配元素则都返回 end
关联式容器 提供了一个等效的成员函数 find 拥有对数复杂度而非线性复杂度
实例
1 2 3 4 5 6 7 8 9 10 11 C++ //检查某个int值是否大于42 vector<int>::iterator pos; pos = find_if(coll.begin(),coll.end(),bind2nd(greater<int>(),42)); cout<<*pos<<endl; // 找出第一个为偶数的元素位置 pos = find_if(coll.begin(),coll.end(),not1(bind2nd(modulus<int>(),2))); // 找出第一个为奇数的元素位置 pos = find_if(coll.begin(),coll.end(),bind2nd(modulus<int>(),2));
4. 搜索前 n 个连续匹配值
Search_n(beg,end,size count,value);
Search_n(beg,end,size count,value,op);
参数解释：
第一形式返回区间连续 count 个元素值全等于 value 元素的位置
第二形式返回区间连续 count 个元素造成以下二元判断式结果为 true 的元素位置
如果没有匹配都返回 end
实例
1 2 3 4 5 6 7 8 C++ // 连续4个等于3的元素 pos = search_n(coll.begin(),coll.end(),4,3); // 连续4个大于3的元素 pos = search_n(coll.begin(),coll.end(),4,3,greater<int>()); cout<<distance(coll.begin(),pos)<<endl;
5. 搜索第一个子区间
Search(beg,end,searchBeg,searchEnd)；
Search(beg,end,searchBeg,searchEnd,op)；
参数解释：
两种形式都返回 2 区间完全吻合的第一个子区间的第一个元素位置
第一形式 子区间元素必须完全等于 [searchBeg,searchEnd) 中的元素
第二形式 子区间的元素 和 [searchBeg,searchEnd) 对应元素必须满足二元判断式 op (elem,searchElem) 结果为 true
如果没有找到都返回 end
实例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 C++ // 求出coll中包含coll2的第一个元素位置 pos = search(coll.begin(),coll.end(),coll2.begin(),coll2.end()); cout<<distance(coll.begin(),pos)<<endl; // elem 对应第一区间 even对应第二区间 bool check(int elem,bool even){ if(even) return elem % 2 == 0; else return elem % 2 == 1; } bool args[3] = {true,false,true}; // 偶数奇数排序的子序列 pos = search(coll.begin(),coll.end(),args,args+3,check); cout<<distance(coll.begin(),pos)<<endl;
6. 搜索某些元素第一次出现的地点
find_first_of(beg,end,searchBeg,searchEnd);
find_first_of(beg,end,searchBeg,searchEnd,OP);
参数解释：
第一形式区间返回第一个既在区间 1 中出现又在区间 2 中出现的元素位置
第二形式返回 [beg,end) 中第一个这样的元素 他和第二区间每个元素进行 op (elem,searchElem) 动作果都是 true
如果没有都返回 end
你可以用逆向迭代器来搜索最后这样的一个元素
7. 搜索两个连续且相当的元素
adjacent_find(beg,end)
adjacent_find(beg,end,op)
参数解释：
第一形式返回区间中第一对连续两个相当元素之中第一元素的位置
第二形式返回区间中第一对连续两个元素均使以下二元判断式 op (elem,nextElem) 的结构为 true 中第一元素的位置
没有找到都返回 end
实例
1 2 3 4 5 6 7 C++ bool doubled(int elem,int elem2){ return elem *= elem2; } Pos = adjacent_find(coll.begin(),coll.end()); Pos = adjacent_find(coll.begin(),coll.end(),doubled);
8. 区间的比较
Equal(beg,end,cmpBeg);
Equal(beg,end,cmpBeg,Op);
9. 搜索第一处不同点
Mismatch(beg,end,cmpBeg)
Mismatch(beg,end,cmpBeg,Op)
10. 检验 “小于” (字典次序)
Bool lexicographical_compare(beg1,end1,beg2,end2)
Bool lexicographical_compare(beg1,end1,beg2,end2,op)
变动性算法 变动性算法要不直接改变元素值，要不就在复制到另一区间的过程中改变元素值。
最基本的变动性算法就是 for_each () 和 transform () 两者都可以变动序列中所有的元素值。
[注意 7] 变动性算法不能是关联式容器
运用某些操作 改操作返回被改动后的参数 此间奥妙在于他可以被用来将结果复制给元素值 如：
1 2 3 4 5 6 7 8 C++ void square(int elem){ elem *= elem; } transform(coll.begin(),coll.end(), // source range coll.begin(), // destination range square); // operation
一些技巧 It has been 540 days since the last update, the content of the article may be outdated.
printf 格式化输出 1 2 3 C++ printf("%md"); // 不足m位 以m位进行对右输出 高位空格补齐 printf("%0md"); // 不足
读入与输出 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 C++ // 字符数组 char str[100]; cin.getline(str,100); // 字符串 string str; getline(cin,str); getline(cin,str); // getline 以回车为结束符 如果使用getline 之前还 使用了cin 那么getline 会读入回车 必须先使用 cin.ignore()忽略 或 cin.get();先读取 cin.getline(char *,int len) // 用来处理字符型 第二个参数是字符长度 // 不能用cin处理大数据 必须用scanf("%lld") 处理long long PTA-A1065**
double 精度 1 2 3 4 5 6 7 C++ //eps 精度修正 const double eps = 1e-8 //10的-8次方 #define Equ(a,b) ((fabs((a)-(b)))<(eps)) // π const double Pi = acos(-1.0);
静态链表 此类静态链表题目注意事项：
队列使用 1 2 C list.push_back(arr[firstAddress]);
对于上述这类代码，特别是使用 queue 时，当最后是需要修改元素而不仅仅是访问时，可以只入队下标，而不入队元素本身。
1 2 3 C++ list.push_back(firstAddress); arr[list.back()]; //输出最后一个元素
二分查找与其扩展 mid = (left + right)/2 中 left + right 超过 int 导致溢出
用 mid = left + (right - left)/2
快速幂迭代与递归写法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 C++ #include<iostream> using namespace std; typedef long long LL; // 求a的b次方与m取余的结果 递归 LL binaryPow(LL a,LL b,LL m){ if(b == 0) // a的0次方 return 1; if(b & 1){ // 次方为奇数 如 2的5次方 则为 a*a的四次方 return a*binaryPow(a,b-1,m)%m; } else{ LL num = binaryPow(a,b >> 1,m); // b>>=1 等价 b/2 return num*num%m; } } // LL binaryPow2(LL a,LL b,LL m){ if(a == 1 || b == 0) return 1; LL ans = 1; while(b > 0){ if(b & 1){ ans = ans*a%m; // 10 = 2的3次方 + 2的一次方 101 } a = a*a%m; // 每次都需要a的平方 b >>= 1; } return ans; } int main(){ cout<<"快速幂的递归法："<<binaryPow(2,15,10007)<<endl; cout<<"快速幂的迭代法："<<binaryPow2(2,15,10007)<<endl; return 0; }
two pointers 问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 C++ /* 给定一个正整数序列M，求序列中两个不同位置数a和b 使他们和恰好等于M 输出所有满足条件的方案。 如 序列 {1,2,3,4,5,6} M=8 存在{2,6} 和 {3,5} */ #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int main(){ int a[]={1,2,3,4,5,6,7,8,9}; int M = 9; int i=0,j=sizeof(a)/sizeof(a[0]); while(i < j){ if(a[i] + a[j] == M){ printf("%d + %d = %d\n",a[i],a[j],M); i++; j--; } else if(a[i] + a[j] > M){ j--; } else{ i++; } } return 0; }
素数快排全排列模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 C++ #include<iostream> #include<cmath> #include<algorithm> using namespace std; /* 素数算法 概述: 质数只会是 6x-1 或 6x+1 n：被检测的数 */ bool isprime(int n) { if(n==0 || n==1) //先判断这些小于5的数 return false; if(n==2 || n==3) return true; if(n%6!=1 && n%6!=5) //判断数是否是6x-1或者6x+1 return false; for(int i=5;i<=sqrt(n);i+=6) { if(n%i==0 || n%(i+2)==0) //每次只用判断是否是它两的倍数 (i 对应 6i-1 i+2 对应 6i+1) return false; } return true; //都满足了，即为质数 } /* 快速排序 */ int partition(int a[],int start,int end){ // 分割数列 int i = start; // 基准点坐标 int j = end; int x = a[i]; while(true){ while(a[++i] < x && i < end); while(a[--j] > x); if( i < j ){ swap(a[i],a[j]); } else break; } swap(a[start],a[j]); // 由于j最后会指向比基准点小的数 i会指向比基准点大的数 而且此时 j < i 所以是交换 基准点坐标与j坐标对应的值 // a[start] 就是旧基准点的值 与 a[j] 交换之后 a[j]的左边所有数都比a[j]小 a[j]的右边所有数都比j大 j已经不用排序了 for(int i=0;i<7;++i){ cout<<a[i]<<" "; } cout<<endl; return j; // 此时j就是基准点坐标 } // 区间 左闭右开 void quicksort(int a[],int start,int end){ if(start < end){ int pos = partition(a,start,end); // 得到基准点坐标 quicksort(a,start,pos-1); // 基准点之前的排列 quicksort(a,pos+1,end); // 基准点之后的排列 } } /* 全排列手动模板 */ long long ans = 0; int a[10] = {0,1,2,3,4,5,6,7,8,9}; bool check(){ return true; } void dfs(int step) { // 出口 if(step == 10){ if(check()){ ans++; } return ; } for(int i=step;i<=9;++i){ swap(a[i],a[step]); dfs(step+1); swap(a[i],a[step]); } } int main(){ // dfs(0); // cout<<ans<<endl; int a[]={21,25,5,17,9,23,30}; quicksort(a,0,7); return 0; }
