第四节 容器适配器

容器适配器没有迭代器!

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