第四节 容器适配器

容器适配器没有迭代器！ 1.stack stack是后进先出的数据结构，只能插入、删除和访问栈顶的元素。可以用vector、list和deque来实现，缺省使用deque实现。用vector和deque实现，比用list实现性能好。 template<class T, class Cont = deque > class stack{ }; stack可以进行下面的操作： （1）push：插入元素； （2）pop：弹出元素； （3）top：返回栈顶元素的引用。 2.Queue 和stack基本类似，可以用list和deque实现，缺省情况下使用deque实现。 template<class T, class Cont = deque > class queue{ }; 同样有push，pop和top函数。但是push在队尾，pop和top在队头。因为是先进先出。有back成员函数可以返回队尾元素的引用。 3.priority_queue template <class T, class Container = vector. class Compare = less > class priority_queue; 和queue类似，可以用vector和deque实现。缺省情况下用vector实现。 priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面，即执行pop操作时，删除的是最大的元素；执行top操作时，返回的是最大元素的常引用。默认元素比较器是less。 push/pop的时间复杂度是O(logn)，top()的时间复杂度是O(1)。 #include #include using namespace std; int main() { priority_queue 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,greater 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 InIt find(InIt first, InIt last, const T& val); 返回区间[first,last)中的迭代器i，使得*i==val。 （2）find_if： template InIt find_if(InIt first, InIt last,Pred pr); 返回区间[first,last)中的迭代器i，使得pr(*i)==true。 （3）for_each： template Fun for)each(InIt first, InIt last, Fun f); 对区间[first,last)中的每个元素e，执行f(e)，要求f(e)不能改变e。 （4）count： template size_t count(InIt first, InIt last, const T& val); 计算[first,last) 中等于val的元素个数。 （5）count_if template size_t count_if(InIt first, InIt last, Pred pr); 计算[first,last) 中符合pr(e) == true 的元素 e的个数。 （6）min_element： template FwdIt min_element(FwdIt first, FwdIt last); 返回[first,last) 中最小元素的迭代器,以 “< ”作比较器。最小指没有元素比它小，而不是它比别的不同元素都小。因为即便a!= b, a<b 和b<a有可能都不成立 （7）max_element： template 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 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 OutIt copy(InIt first, InIt last, OutIt x); 本函数对每个在区间[0,last-first)中的N执行一次(x+N)=(first+N)，返回x+N。copy的源代码如下： template 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::const_iterator，output的类型是osream_iterator。 3.**删除算法 删除算法会删除一个容器里的某些元素。这里所说的 “删除”，并不会使容器里的元素减少，其工作过程是：将所有应该被删除的元素看做空位子，然后用留下的元素从后往前移，依次去填空位子。元素往前移后，它原来的位置也就算是空位子，也应由后面的留下的元素来填上。最后，没有被填上的空位子，维持其原来的值不变。删除算法不应作用于关联容器**。 表5.3 删除算法的算法

算法名称

算法功能

remove

删除区间中等于某个值的元素

remove_if

删除区间中满足某种条件的元素

remove_copy

拷贝区间到另一个区间。等于某个值的元素不拷贝

remove_copy_if

拷贝区间到另一个区间。符合某种条件的元素不拷贝

uqique

删除区间中连续相等的元素，只留下一个(可自定义比较器)

unique_copy

拷贝区间到另一个区间。连续相等的元素，只拷贝第一个到目标区间 (可自定义比较器)

算法复杂度均为O(n)。 我们具体来看： （1）unique template FwdIt unique(FwdIt first, FwdIt last); 用 == 比较是否等 template 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 oit(cout,”,”); int p = remove(a,a+5,2); //输出语句，输出1,3,2,5 cout<<”2)”<<p-a<<endl;//输出2)3。是指的元素中剩余的有效元素还有3个，删除了首地址的元素。 vector 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 void random_shuffle(RanIt first, RanIt last); 随机打乱[first,last) 中的元素，适用于能随机访问的容器。用之前要初始化伪随机数种子： srand(unsigned(time(NULL)));//**需要**#include （2）reverse template void reverse(BidIt first, BidIt last); 颠倒区间[first,last)顺序。 （3）next_permutation template bool next_permutaion (Init first,Init last); 求下一个排列。 例程： #include #include #include 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 void sort(RanIt first, RanIt last); 按升序排序。判断x是否应比y靠前，就看 x < y 是否为true。 template void sort(RanIt first, RanIt last, Pred pr); 按升序排序。判断x是否应比y靠前，就看 pr(x,y) 是否为true sort 实际上是快速排序，时间复杂度 O(nlog(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 bool binary_search(FwdIt first, FwdIt last, const T& val); 上面这个版本，比较两个元素x,y大小时,看 x < y。 template bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr); 上面这个版本，比较两个元素x,y大小时,若pr(x,y) 为true，则认为x小于y。 （2）merge template OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);用<作比较器 template 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 bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2); template 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 OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); template 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 OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); template 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 OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x); template 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& operator&=(const bitset& rhs); bitset& operator|=(const bitset& rhs); bitset& operator^=(const bitset& rhs); bitset& operator<<=(size_t num); bitset& operator>>=(size_t num); bitset& set(); //全部设成1 bitset& set(size_t pos, bool val = true); //设置某位 bitset& reset(); //全部设成0 bitset& reset(size_t pos); //某位设成0 bitset& flip(); //全部翻转 bitset& 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& rhs) const; bool operator!=(const bitset& rhs) const; bool test(size_t pos) const; //测试某位是否为1 bool any() const; //是否有某位为1 bool none() const; //是否全部为0 bitset operator<<(size_t pos) const; bitset operator>>(size_t pos) const; bitset operator~(); static const size_t bitset_size = N; 注意：第0位在最右边。