第四节 容器适配器
容器适配器没有迭代器！
1.stack
stack是后进先出的数据结构，只能插入、删除和访问栈顶的元素。可以用vector、list和deque来实现，缺省使用deque实现。用vector和deque实现，比用list实现性能好。
template<class T, class Cont = deque<T> >
class stack{ };
stack可以进行下面的操作：
（1）push：插入元素；
（2）pop：弹出元素；
（3）top：返回栈顶元素的引用。
2.Queue
和stack基本类似，可以用list和deque实现，缺省情况下使用deque实现。
template<class T, class Cont = deque<T> >
class queue{ };
同样有push，pop和top函数。但是push在队尾，pop和top在队头。因为是先进先出。有back成员函数可以返回队尾元素的引用。
3.priority_queue
template <class T, class Container = vector<T>. class Compare = less<T> >
class priority_queue;
和queue类似，可以用vector和deque实现。缺省情况下用vector实现。
priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面，即执行pop操作时，删除的是最大的元素；执行top操作时，返回的是最大元素的常引用。默认元素比较器是less<T>。
push/pop的时间复杂度是O(logn)，top()的时间复杂度是O(1)。
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue<double> p1;
p1.push(3.2);p1.push(9.8);p1.push(9.8);p1.push(5.4);
while(!p1.empty()){
cout<<p1.top()<<” “;
p1.pop();
}//输出9.8 9.8 5.4 3.2
cout<<endl;
priority_queue<double,vector<double>,greater<double> p2;
p2.push(3.2);p2.push(9.8);p2.push(9.8);p2.push(5.4);
while(!p1.empty()){
cout<<p1.top()<<” “;
p2.pop();
}//输出3.2 5.4 9.8 9.8
return 0;
}
stack/queue/priority_queue都有：empty()（用于判断适配器是否为空）和size()（返回适配器中元素个数。）
第五节 算法
STL中的算法大致可以分为以下七类：
（1）不变序列算法
（2）变值算法
（3）删除算法
（4）变序算法
（5）排序算法
（6）有序区间算法
（7）数值算法
大多数重载的算法都是有两个版本：一个版本是用“==”判断元素是否相等，或用“<”来比较大小；还有一个版本是多出一个类型参数Pred和函数形参Pred op，通过表达式op(x,y)的返回值true/false来判断x是否等于y或者x是否小于y或者x是否大于y。
1.不变序列算法
此类算法不会修改算法所作用的容器或对象，适用于所有容器（特别是顺序容器和关联容器）。它的时间复杂度是O(n)的。它包括以下算法：
表5.1 不变序列算法中的算法
| 算法名称 | 功能 |
| min | 求两个对象中较小的（可自定义比较器） |
| max | 求两个对象中较大的（可自定义比较器） |
| min_element | 求区间中的最小值（可自定义比较器） |
| max_element | 求区间中的最大值（可自定义比较器） |
| for_each | 对区间中的每个元素都做这种操作（不能改变数值） |
| count | 计算区间中等于某值的元素个数 |
| count_if | 计算区间中符合某种条件的元素个数 |
| find | 在区间中查找等于某值的元素 |
| find_if | 在区间中查找符合某条件的元素 |
| find_end | 在区间中查找另一个区间最后一次出现的位置（可自定义比较器） |
| find_first_of | 在区间中查找第一个出现在另一个区间中的元素（可自定义比较器） |
| adjacent_find | 在区间中寻找第一次出现连续两个相等元素的位置（可自定义比较器） |
| search | 在区间中查找另一个区间第一次出现的位置（可自定义比较器） |
| search_n | 在区间中查找第一次出现等于某值的连续n个元素（可自定义比较器） |
| equal | 判断两区间是否相等（可自定义比较器） |
| mismatch | 逐个比较两个区间元素，返回第一次发生不相等的两个元素的位置（可自定义比较器） |
| lexicographical_compare | 按字典序比较两个区间的大小（可自定义比较器） |
我们具体来看：
（1）find：
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
返回区间[first,last)中的迭代器i，使得*i==val。
（2）find_if：
template<class InIt, class Pred>
InIt find_if(InIt first, InIt last,Pred pr);
返回区间[first,last)中的迭代器i，使得pr(*i)==true。
（3）for_each：
template<clas InIt, classFun>
Fun for)each(InIt first, InIt last, Fun f);
对区间[first,last)中的每个元素e，执行f(e)，要求f(e)不能改变e。
（4）count：
template<class InIt, class T>
size_t count(InIt first, InIt last, const T& val);
计算[first,last) 中等于val的元素个数。
（5）count_if
template<class InIt, class Pred>
size_t count_if(InIt first, InIt last, Pred pr);
计算[first,last) 中符合pr(e) == true 的元素 e的个数。
（6）min_element：
template<class FwdIt>
FwdIt min_element(FwdIt first, FwdIt last);
返回[first,last) 中最小元素的迭代器,以 “< ”作比较器。最小指没有元素比它小，而不是它比别的不同元素都小。因为即便a!= b, a<b 和b<a有可能都不成立
（7）max_element：
template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
返回[first,last) 中最大元素(它不小于任何其他元素，但不见得其他不同元素都小于它）的迭代器,以 “< ”作比较器。
2.变值算法
此类算法会修改源区间或目标区间元素的值。值被修改的那个区间，不可以是属于关联容器的（因为关联容器是排好序的算法，如果直接值被修改，容器中顺序被打破，再去执行别的操作可能结果就不是预期结果）。
表5.2 变值算法的算法
| 算法名称 | 算法功能 |
| for_each | 对区间中的每个元素都做某种操作（可以改变数值） |
| copy | 复制一个区间到别处 |
| copy_backward | 复制一个区间到别处，但目标区前是从后往前被修改的 |
| transform | 将一个区间的元素变形后拷贝到另一个区间 |
| swap_ranges | 交换两个区间内容 |
| fill | 用某个值填充区间 |
| fill_n | 用某个值替换区间中的n个元素 |
| generate | 用某个操作的结果填充区间 |
| generate_n | 用某个操作的结果替换区间中的n个元素 |
| replace | 将区间中的某个值替换为另一个值 |
| replace_if | 将区间中符合某种条件的值替换成另一个值 |
| replace_copy | 将一个区间拷贝到另一个区间，拷贝时某个值要换成新值拷过去 |
| replace_copy_if | 将一个区间拷贝到另一个区间，拷贝时符合某条件的值要换成新值拷过去 |
我们来具体看一下：
（1）transform
template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x, Unop uop);
对[first,last)中的每个迭代器 I，执行 uop( * I ) ; 并将结果依次放入从x开始的地方。要求uop( * I )不得改变 * I 的值。本模板返回值是个迭代器，即 x + (last-first)，x 可以和 first相等。
（2）copy
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
本函数对每个在区间[0,last-first)中的N执行一次*(x+N)=*(first+N)，返回x+N。copy的源代码如下：
template<class _II, class _OI>
inline _OI copy(_II_F, _II_L, __OI_X)
{
for(;_F!=_L;++_X,++_F)
*_X = *_F;
return(_X);
}
它有两个类型，一个是II一个是OI，暗示分别是输入和输出。函数的三个参数的前两个是区间的开始和结束，后面则可以是某个位置。这个函数做的就是在从_F走到_L的过程中，把*_F的值赋给*_X，然后_F和_X不断后移。
对于copy(v.begin(), v.end(), output);first和last的类型是vecotr<int>::const_iterator，output的类型是osream_iterator<int>。
3.删除算法
删除算法会删除一个容器里的某些元素。这里所说的 “删除”，并不会使容器里的元素减少，其工作过程是：将所有应该被删除的元素看做空位子，然后用留下的元素从后往前移，依次去填空位子。元素往前移后，它原来的位置也就算是空位子，也应由后面的留下的元素来填上。最后，没有被填上的空位子，维持其原来的值不变。删除算法不应作用于关联容器。
表5.3 删除算法的算法
| 算法名称 | 算法功能 |
| remove | 删除区间中等于某个值的元素 |
| remove_if | 删除区间中满足某种条件的元素 |
| remove_copy | 拷贝区间到另一个区间。等于某个值的元素不拷贝 |
| remove_copy_if | 拷贝区间到另一个区间。符合某种条件的元素不拷贝 |
| uqique | 删除区间中连续相等的元素，只留下一个(可自定义比较器) |
| unique_copy | 拷贝区间到另一个区间。连续相等的元素，只拷贝第一个到目标区间 (可自定义比较器) |
算法复杂度均为O(n)。
我们具体来看：
（1）unique
template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
用 == 比较是否等
template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);用 pr 比较是否等
返回值是迭代器，指向元素删除后的区间的最后一个元素的后面。
int main()
{
int a[5] = {1,2,3,2,5};
int b[6] = {1,2,3,2,5,6};
ostream_iterator<int> oit(cout,”,”);
int * p = remove(a,a+5,2);
//输出语句，输出1,3,2,5
cout<<“2)”<<p-a<<endl;//输出2)3。是指的元素中剩余的有效元素还有3个，删除了首地址的元素。
vector<int> v(b,b+6);
remove(v.begin().v.end(),2);
//输出语句，结果为1,3,5,6,5,6
return 0;
}
之所以第一次输出的结果为1,3,2,5是因为，当我们删除第一个2的时候，后面的3移过来，然后后面的2页被删了，再后面的5移过来，这样最后面空了2个位置，则这两个位置的原来的值保持不变。
4.变序算法
变序算法改变容器中元素的顺序，但是不改变元素的值。变序算法不适用于关联容器。此类算法复杂度都是O(n)的。
表5.4 变序算法的算法
| 算法名称 | 算法功能 |
| reverse | 颠倒区间的前后次序 |
| reverse_copy | 把一个区间颠倒后的结果拷贝到另一个区间，源区间不变 |
| rotate | 将区间进行循环左移 |
| rotate_copy | 将区间以首尾相接的形式进行旋转后的结果拷贝到另一个区间，源区间不变 |
| next_permutation | 将区间改为下一个排列(可自定义比较器) |
| prev_permutation | 将区间改为上一个排列(可自定义比较器) |
| random_shuffle | 随机打乱区间内元素的顺序 |
| partition | 把区间内满足某个条件的元素移到前面，不满足该条件的移到后面 |
| stable_patition | 把区间内满足某个条件的元素移到前面，不满足该条件的移到后面。而且对这两部分元素，分别保持它们原来的先后次序不变 |
我们来具体看一下：
（1）random_shuffle
template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
随机打乱[first,last) 中的元素，适用于能随机访问的容器。用之前要初始化伪随机数种子：
srand(unsigned(time(NULL)));//需要#include<ctime>
（2）reverse
template<class BidIt>
void reverse(BidIt first, BidIt last);
颠倒区间[first,last)顺序。
（3）next_permutation
template<class InIt>
bool next_permutaion (Init first,Init last);
求下一个排列。
例程：
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
string str = “231”;
char szStr[] = “324”;
while (next_permutation(str.begin(), str.end())){
cout << str << endl;//输出312 321
}
cout << “****” << endl;
while (next_permutation(szStr,szStr + 3))
{
cout << szStr << endl;
}
sort(str.begin(),str.end());
cout << “****” << endl;
while (next_permutation(str.begin(), str.end())){
cout << str << endl;
}
return 0;
}
5.排序算法
排序算法比前面的变序算法复杂度更高，一般是O(n×log(n))。排序算法需要随机访问迭代器的支持，因而不适用于关联容器和list。
表5.5 排序算法的算法
| 算法名称 | 算法功能 |
| sort | 将区间从小到大排序(可自定义比较器)。 |
| stable_sort | 将区间从小到大排序，并保持相等元素间的相对次序(可自定义比较器)。 |
| partial_sort | 对区间部分排序，直到最小的n个元素就位(可自定义比较器)。 |
| partial_sort_copy | 将区间前n个元素的排序结果拷贝到别处。源区间不变(可自定义比较器)。 |
| nth_element | 对区间部分排序，使得第n小的元素（n从0开始算）就位，而且比它小的都在它前面，比它大的都在它后面(可自定义比较器)。 |
| make_heap | 使区间成为一个“堆”(可自定义比较器)。 |
| push_heap | 将元素加入一个是“堆”区间(可自定义比较器)。 |
| pop_heap | 从 “堆”区间删除堆顶元素(可自定义比较器)。 |
| sort_heap | 将一个“堆”区间进行排序，排序结束后，该区间就是普通的有序区间，不再是 “堆”了(可自定义比较器)。 |
我们来具体看一下：
（1）sort 快速排序
template<class RanIt>
void sort(RanIt first, RanIt last);
按升序排序。判断x是否应比y靠前，就看 x < y 是否为true。
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
按升序排序。判断x是否应比y靠前，就看 pr(x,y) 是否为true
sort 实际上是快速排序，时间复杂度 O(n*log(n))；平均性能最优。但是最坏的情况下，性能可能非常差。如果要保证“最坏情况下”的性能，那么可以使用stable_sort。stable_sort 实际上是归并排序，特点是能保持相等元素之间的先后次序。在有足够存储空间的情况下，复杂度为 n * log(n)，否则复杂度为 n * log(n) * log(n)。stable_sort 用法和 sort相同。排序算法要求随机存取迭代器的支持，所以list 不能使用排序算法，要使用list::sort。
此外，其它排序算法：
partial_sort：部分排序，直到前n个元素就位即可。
nth_element：排序，直到第 n个元素就位，并保证比第n个元素小的元素都在第n个元素之前即可。
partition：改变元素次序，使符合某准则的元素放在前面。
6.有序区间算法
有序区间算法要求所操作的区间是已经从小到大排好序的，而且需要随机访问迭代器的支持。所以有序区间算法不能用于关联容器和list。
表5.6 有序区间算法的算法
| 算法名称 | 功能 |
| binary_search | 判断区间中是否包含某个元素。 |
| includes | 判断是否一个区间中的每个元素，都在另一个区间中。 |
| lower_bound | 查找最后一个不小于某值的元素的位置。 |
| upper_bound | 查找第一个大于某值的元素的位置。 |
| equal_range | 同时获取lower_bound和upper_bound。 |
| merge | 合并两个有序区间到第三个区间。 |
| set_union | 将两个有序区间的并拷贝到第三个区间。 |
| set_intersection | 将两个有序区间的交拷贝到第三个区间。 |
| set_difference | 将两个有序区间的差拷贝到第三个区间。 |
| set_symmetric_difference | 将两个有序区间的对称差拷贝到第三个区间。 |
| inplace_merge | 将两个连续的有序区间原地合并为一个有序区间。 |
我们来具体看一下：
（1）binary_search 二分查找
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last, const T& val);
上面这个版本，比较两个元素x,y大小时,看 x < y。
template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr);
上面这个版本，比较两个元素x,y大小时,若pr(x,y) 为true，则认为x小于y。
（2）merge
template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);用<作比较器
template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);用pr做比较器
把[first1,last1),[first2,last2)两个升序序列合并，形成第3个升序序列，第3个升序序列以x开头。（空间必须得充足）
（3）includes
template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
判断[first2,last2)中的每个元素，是否都在[first1,last1)中第一个用<作比较器，第二个用pr作比较器,pr(x,y)==true说明x,y相等。
（4）set_difference
template<class InIt1, class InIt2, class OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
求出[first1,last1)中，不在[first2,last2)中的元素，放到从x开始的地方。如果[first1,last1)里有多个相等元素不在[first2,last2)中，则这多个元素也都会被放入x代表的目标区间里。
（5）set_intersection
template<class InIt1, class InIt2, class OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
求出[first1,last1)和[first2,last2)中共有的元素，放到从x开始的地方。若某个元素e在[first1,last1)里出现n1次，在[first2,last2)里出现n2次，则该元素在目标区间里出现min(n1,n2)次。
（6）set_symmetric_difference
template<class InIt1, class InIt2, class OutIt>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
把两个区间里相互不在另一区间里的元素放入x开始的地方。
（7）set_union
图5.1 set_union
7.bitset（非数值算法，是类模板）
template<size_t N>
class bitset {};
是实现标志位。实际使用的时候，N是个整型常数如：
bitset<40> bst;
bst是一个由40位组成的对象，用bitset的函数可以方便地访问任何一位。
bitset的成员函数如下：
bitset<N>& operator&=(const bitset<N>& rhs);
bitset<N>& operator|=(const bitset<N>& rhs);
bitset<N>& operator^=(const bitset<N>& rhs);
bitset<N>& operator<<=(size_t num);
bitset<N>& operator>>=(size_t num);
bitset<N>& set(); //全部设成1
bitset<N>& set(size_t pos, bool val = true); //设置某位
bitset<N>& reset(); //全部设成0
bitset<N>& reset(size_t pos); //某位设成0
bitset<N>& flip(); //全部翻转
bitset<N>& flip(size_t pos); //翻转某位
reference operator[](size_t pos); //返回对某位的引用
bool operator[](size_t pos) const; //判断某位是否为1
reference at(size_t pos);
bool at(size_t pos) const;
unsigned long to_ulong() const; //转换成整数
string to_string() const; //转换成字符串
size_t count() const; //计算1的个数
size_t size() const;
bool operator==(const bitset<N>& rhs) const;
bool operator!=(const bitset<N>& rhs) const;
bool test(size_t pos) const; //测试某位是否为1
bool any() const; //是否有某位为1
bool none() const; //是否全部为0
bitset<N> operator<<(size_t pos) const;
bitset<N> operator>>(size_t pos) const;
bitset<N> operator~();
static const size_t bitset_size = N;
注意：第0位在最右边。