C++面向对象程序设计课程笔记（第九周）（下）

第四节 容器适配器

容器适配器没有迭代器！

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 不变序列算法中的算法

我们具体来看：

（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 变值算法的算法

我们来具体看一下：

（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 删除算法的算法

算法复杂度均为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 变序算法的算法

我们来具体看一下：

（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 排序算法的算法

我们来具体看一下：

（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 有序区间算法的算法

我们来具体看一下：

（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位在最右边。