第八周 标准模板库STL(一)

第一节 string类

1.关于string

string类是模板类:typedef basic_string<char>string;实例出来的类。使用string类要包含头文件<string>。

string对象的初始化有以下几种类型:

string s1(“Hello);

string month = “March”;

string s2(8,’x’);

以下的初始方法错误:

string error1 = ‘c’;//error

string error2(‘u’);//error

string error3 = 22//error

string error4(22);//error

但是可以将字符赋值给string对象,如下:

string s;

s = ‘n’;//OK

string对象的长度用成员函数length()读取,如下:

string s(“hello”);

cout<<s.length()<<endl;

string支持流读取运算符,如下:

string stringObject;

cin>> stringObject;

string支持getline函数:

string s;

getline(cin,s);

2.string的赋值和连接

(1)用=赋值:

string s1(“cat”),s2;

s2 = s1;

(2)用assign成员函数复制

string s1(“cat”),s3;

s3.assign(s1);

(3)用assign成员函数部分复制

string s1(“catpig”),s3;

s3.assign(s1,1,3);//从s1中下标为1的字符开始复制3个字符给s3

(4)单个字符复制

s2[5]=s1[3]=’a’;

(5)逐个访问string对象中的字符

string s1(“Hello”);

for(int i = 0;i<s1.length();i++)

cout<<s1.at(i)<<endl;

成员函数at会做范围检查,如果超出范围,会抛出out_of_range异常,而下标运算符[]不做范围检查。

(6)用+运算符连接字符串

string s1(“good”),s2(“morning”);

s1+=s2;

cout<<s1;//输出goodmorning

(7)用成员函数append

s2.append(s1,3,s1.size());//s1.size()为s1的字符数

下标为3开始,s1.size()个字符数,如果字符串内没有足够字符,则复制到字符串最后一个字符。

3.比较string

(1)用关系运算符比较string的大小:==/>/>=/</<=/!=

返回值都是bool类型,按照字典序。

(2)用成员函数compare比较string的大小

string s1(“hello”),s2(“hello”),s3(“hell”);

int f1 = s1.compare(s2);//0

int f2 = s1.compare(s3);//1

int f3 = s3.compare(s1);//-1

int f4 = s1.compare(1,2,s3,0,3);//-1,比较s1的1-2与s3的0到3

int f5 = s1.compare(0,s1.size(),s3);//1,比较s1和s3的0-end

4.成员函数

(1)成员函数substr

string s1(“hello world”),s2;

s2 = s1.substr(4,5);//下标4开始5个字符

cout << s2 <<endl;

输出:o wor

(2)成员函数swap

string s1(“hello”),s2(“really”);

s1.swap(s2);

(3)成员函数find()

string s1(“hello world”);

s1.find(“lo”);

在s1中从前向后查找lo第一次出现的地方,如果找到则返回lo开始的位置(即l的下标);如果找不到,返回string::npos(string定义的静态常量)。

(4)成员函数rfind()

string s1(“hello world”);

s1.rfind(“lo”);

在s1中从后向前查找lo第一次出现的地方,如果找到则返回lo开始的位置(即l的下标);如果找不到,返回string::npos(string定义的静态常量)。

(5)成员函数find_first_of()

string s1(“hello world”);

s1.find_first_of(“abcd”);

在s1中从前向后找abcd中任何一个字符第一次出现的地方,如果找到返回字母的位置;如果找不到返回string::npos。

(6)成员函数find_last_of()

string s1(“hello world”);

s1.find_last_of(“abcd”);

在s1中查找abcd中任何一个字符最后一次出现的地方,如果找到,返回找到字母的位置;如果找不到,返回string::npos。

(7)成员函数find_first_not_of()

string s1(“hello world”);

s1.find_first_not_of (“abcd”);

在s1中从前向后查找不在abcd中的字母第一次出现的地方,如果找到,返回找到字母的位置(在此例中为h,返回0);如果找不到,返回string::npos。

(8)成员函数find_last_not_of()

string s1(“hello world”);

s1.find_last _not_of (“abcd”);

在s1中凑后往前查找不在abcd中的字母第一次出现的地方,如果找到,返回找到字母的位置(此处为l,返回地址为9);如果找不到,返回string::npos。

(9)成员函数erase()。删除string中的字符。

(10)成员函数replace()。替换string中的字符。例如:

string s1(“hello world”);

s1.replace(2,3,”haha”);

cout << s1;

//将s1下标2开始的三个字符替换为haha

如果被替换区间大小小于替换长度,那么直接在后面加,如本例输出为hehaha world

(11)成员函数insert()。在string中插入字符。

例程:

string s1(“hello world”);

string s2(“show insert”);

s1.insert(5,s2); // 将s2插入s1下标5的位置

cout << s1 << endl;

s1.insert(2,s2,5,3);

//将s2中下标5开始的3个字符插入s1下标2的位置

cout << s1 << endl;

输出结果为:

helloshow insert world

heinslloshow insert world

(12)成员函数c_str。转换成C语言式char*字符串

string s1(“hello world”);

printf(“%s\n,s1.c_str());//为了兼容C语言

// s1.c_str() 返回传统的const char * 类型字符串,且该字符串以‘\0’结尾。

(13)成员函数data()

string s1(“hello world”);

const char * p1=s1.data();

for(int i=0;i<s1.length();i++)

printf(“%c”,*(p1+i));

//s1.data() 返回一个char * 类型的字符串,对s1 的修改可能会使p1出错。

(14)成员函数copy()。字符串拷贝函数。

string s1(“hello world”);

int len = s1.length();

char * p2 = new char[len+1];

s1.copy(p2,5,0);

p2[5]=0;

cout << p2 << endl;

// s1.copy(p2,5,0) 从s1的下标0的字符开始制作一个最长5个字符长度的字符串副本并将其赋值给p2。返回值表明实际复制字符串的长度。

输出结果为:hello

5.字符串流处理

除了标准流和文件流输入输出外,还可以从string进行输入输出;

类似 istream和osteram进行标准流输入输出,我们用istringstream 和 ostringstream进行字符串上的输入输出,也称为内存输入输出。

用到的头文件:

#include <string>

#include <iostream>

#include <sstream>

例程1:字符串输入流 istringstream

string input(“Input test 123 4.7 A”);

istringstream inputString(input);

string string1, string2;

int i;

double d;

char c;

inputString >> string1 >> string2 >> i >> d >> c;

cout << string1 << endl << string2 << endl;

cout << i <<endl << d << endl << c << endl;

long L;

if(inputString >> L)

cout << “long\n”;

else cout << “empty\n”;

输出结果为:

Input test 123 4.7 A empty

例程2:字符串输出流 istringstream

ostringstream outputString;

int a = 10;

outputString << “This ” << a << ” ok” << endl;

cout << outputString.str();

输出:This 10 ok

 

第二节 标准模板库STL概述(一)

1.泛型程序设计

C++语言的核心优势之一就是便于软件的重用。C++中有两个方面体现重用:

(1)面向对象的思想:继承和多态,标准类库。

(2)泛型程序设计的思想:模板机制,以及标准模板库STL。

将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。

标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。有了STL,不必再写大多的标准数据结构和算法,并且可获得非常高的性能。

2.STL中的基本概念

容器:可容纳各种数据类型的通用数据结构,是类模板。

迭代器:可用于依次存取容器中元素,类似于指针。

算法:用来操作容器中的元素的函数模板。

算法本身与他们操作的数据的类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

举个例子,比如说int array[100];该数组就是容器,而int*类型的指针变量就可以作为迭代器,sort算法可以作用于该容器上,对其进行排序:

sort(array,array+70);

3.容器概述

可以用于存放各种类型的数据(基本类型的变量、对象等)的数据结构,都是类模板,分为三种:

①顺序容器:vector,deque,list。

②关联容器:set,multiset,map,multimap。

③容器适配器:stack,queue,priority_queue。

对象被插入容器中时,被插入的是对象的一个复制品。许多算法,比如排序,查找,要求对容器中的元素进行比较,有的容器本身就是排序的,所以,放入容器的对象所属的类,往往还应该重载 == 和 < 运算符。

(1)顺序容器

容器并非排序的,元素的插入位置同元素的值无关。有vector,deque,list三种。

①vector   头文件<vector>

动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间)。

②deque 头文件<deque>

双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。

③list 头文件<list>

双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取

(2)关联容器

元素是排序的,插入任何元素,都按相应的排序规则来确定其位置。在查找时有非常好的性能,通常以平衡二叉树方式实现,插入和检索时间都是O(log(N))

①set/multiset 头文件<set>

set即集合。set中不允许相同元素,multiset中允许相同的元素。

②map/multimap 头文件<map>

map与set的不同在于map中存放的元素有且仅有两个成员变量,一个名为first,另一个名为second,map根据first值对元素进行从小到大排序,并可快速根据first来检索元素。

map同multimap的不同在于是否允许相同first值的元素。

(3)容器适配器

①stack:头文件 <stack>

栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。后进先出

②queue 头文件<queue>

队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。先进先出

③priority_queue 头文件<queue>

优先级队列。最高优先级元素总是第一个出列。

4.顺序容器和关联容器中都有的成员函数

成员函数功能
begin返回指向容器中第一个元素的迭代器。
end返回指向容器中最后一个元素后面的位置的迭代器。
rbegin返回指向容器中最后一个元素的迭代器。
rend返回只想容器中第一个元素前面的位置迭代器。
erase从容器中删除一个或几个元素。
clear从容器中删除所有元素。

5.顺序容器的常用成员函数

成员函数功能
front返回容器中第一个元素的引用。
back返回容器中最后一个元素的引用。
push_back在容器末位增加新元素。
pop_back删除容器模块的元素。
erase删除迭代器指向的元素(可能会使该迭代器失效),或删除一个区间,返回被删除元素后面的那个元素的迭代器。

 

第三节 标准模板库STL概述(二)

1.迭代器

(1)基本概念

  • 用于指向顺序容器和关联容器中的元素
  • 迭代器用法和指针类似
  • 有const 和非 const两种
  • 通过迭代器可以读取它指向的元素
  • 通过非const迭代器还能修改其指向的元素

(2)迭代器的定义

定义一个容器类的迭代器的方法可以是:

容器名称::iterator 变量名;

容器名称::const_iterator 变量名;

访问一个迭代器指向的元素:

*迭代器变量名

迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,此时再使用它,就会出错,类似于使用NULL或未初始化的指针一样。

例程:

#include <vector>

#include <iostream>

using namespace std;

int main() {

vector<int> v; //一个存放int元素的数组,一开始里面没有元素

v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);

vector<int>::const iterator i;//常量迭代器

for(int i = v.begin();i!=v.end;++i)

cout<<*i<<“,”;

cout<<endl;

//输出结果1,2,3,4,

vector<int>::reserve.iterator r;//反向迭代器

for(r = v.rbegin();r!=v.rend();r++)

cout<<*r<<“,”;

cout<<endl;

//输出结果:4,3,2,1,

vector<int>::iterator j;//非常量迭代器

for(j = v.begin();j!=v.end();j++)

*j = 100;

for(i = v.begin();i!=v.end();i++)

cout<<*i<<“,”;

//输出结果:100,100,100,100,

return 0;

}

(3)双向迭代器

若p和p1都是双向迭代器,则可对p、p1可进行以下操作:

++p,p++:使p指向容器中下一个元素;

–p,p–:使p指向容器的上一个元素;

*p:取p指向的元素;

p = p1:赋值;

p==p1,p!=p1:判断是否相等

(4)随机访问迭代器

若p和p1都是随机访问迭代器,则可对p、p1可进行以下操作:

双向迭代器的所有操作

p += i 将p向后移动i个元素

p -= i 将p向向前移动i个元素

p + i 值为: 指向 p 后面的第i个元素的迭代器

p – i 值为: 指向 p 前面的第i个元素的迭代器

p[i] 值为: p后面的第i个元素的引用

p < p1, p <= p1, p > p1, p>= p1

p – p1  : p1和p之间的元素个数

表3.1 容器和容器上面的迭代器

容器容器上的迭代器类别
vector随机访问
deque随机访问
list双向
set/multiset双向
map/multimap双向
stack不支持
queue不支持
priority_queue不支持

 

例程1vector的遍历,deque也是这样

vector<int> v(100);

int i;

for(i = 0;i < v.size() ; i ++)

cout<<v[i];//根据下标随机访问

vector<int>::const_iterator ii;

for( ii = v.begin(); ii != v.end ();++ii)

cout << * ii;

for( ii = v.begin(); ii < v.end ();++ii )

cout << * ii;

例程2:list的遍历(双向迭代器)

list<int> v;

list<int>::const_iterator ii;

for(ii=v.begin();ii!=v.end();++ii)

cout<<*ii;

2.算法

算法就是一个个函数模板, 大多数在<algorithm> 中定义。STL中提供能在各种容器中通用的算法,比如查找,排序等。算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作,因此需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找。有的算法返回一个迭代器。比如 find() 算法,在容器中查找一个元素,并返回一个指向该元素的迭代器。算法可以处理容器,也可以处理普通数组

算法示例:find()

template<class InIt, class T>

InIt find(InIt first, InIt last, const T& val);

first 和 last 这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点[first,last)。区间的起点是位于查找范围之中的,而终点不是。find在[first,last)查找等于val的元素。用 == 运算符判断相等。函数返回值是一个迭代器。如果找到,则该迭代器指向被找到的元素。如果找不到,则该迭代器等于last。

例程:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

int main()  {

int array[10] = {10,20,30,40};

vector<int> v;

v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);

vector<int>::iterator p;

p = find(v.begin(),v.end(),3);

if(p!=v.end())

cout<<*p<<endl;//输出3

p = find(v.begin(),v.end(),9)

if(p == v.end())

cout<<“not found”<<endl;//输出not found

p = find(v.begin+1,v.end()-2,1);

//查找区间为[2,3)

if(p!=v.end())

cout<<*p<endl;//输出结果为3,因为找不到就返回v.end(),在这里相当于v.end()的是3这个位置

int *pp = find(array,array+4,20);//数组名是迭代器

cout<<*pp<<endl;//输出20

}

3.STL中的“大”、“小”和“相等”

关联容器内部的元素是从小到大排序的。有些算法要求其操作的区间是从小到大排序的,称为“有序区间算法”,例如binary_search(二分法查找);有些算法会对区间进行从小到大(可以自己定义)排序,称为“排序算法”,例如sort;还有一些其它算法会用到“大”“小”的概念,使用STL时,在缺省情况下,以下三个说法等价:

(1)x比y小;

(2)表达式“x<y”为真;

(3)y比x大。

有时,“x和y相等”等价于“x==y为真”,例如在未排序的区间上进行的算法,如顺序查找find;有时候“x和y相等”等价于“x小于y和y小于x同时为假”(这里小于也是可以自定义的),例如有序区间算法,如binary_search,关联容器自身的成员函数find。

第四节 vector,deque和list

1.vector

vector示例程序1

#include <iostream>

#include <vector>

using namespace std;

template<class T>

void PrintVector( T s, T e){

for(; s != e; ++s)

cout << * s << ” “;

cout << endl;

}

int main(){

int a[5] = {1,2,3,4,5};

vector<int> v(a,a+5);//将数组a的内容放入v

cout<<“1)”<<v.end()-v.begin()<<endl;

//两个随机迭代器可以相减,输出1)5

cout<<“2)”;

PrintVector(v.begin(),v.end());

//2)1 2 3 4 5

v.insert(v.begin()+2,13);

cout<<“3)”;

PrintVector(v.begin(),v.end());

//3)1 2 13 3 4 5

v.erase(v.begin()+2);

cout<<“4)”;

PrintVector(v.begin(),v.end());

//4)1 2 3 4 5

vector<int> v2(4,100);//v2有4个元素,都是100

v2.insert(v2.begin(),v.begin()+1,v.begin()+3);

cout<<“5)”;

PrintVector(v2.begin(),v2.end());

//5)2 3 100 100 100 100

v.erase(v.begin() + 1, v.begin() + 3);

//删除 v 上的一个区间,即 2,3

cout << “6) “;

PrintVector(v.begin(),v.end());

//6) 1 4 5

return 0;

}

例程2:用vector实现二维数组

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector<vector<int> > v(3);

//v有3个元素,每个元素都是vector<int>容器

for(int i = 0;i<v.size();++i)

for(int j = 0;j<4;++j)

v[i].push_back(j);

for(int i = 0;i<v.size();++i){

for(int j = 0;j<v[i].size();++j)

cout<<v[i][j]<<” “;

cout<<endl;

}

return 0;

}

2.deque

所有适用于 vector的操作都适用于 deque。

deque还有 push_front(将元素插入到前面) 和pop_front(删除最前面的元素)操作,复杂度是O(1)。

3.双向链表

在任何位置插入删除都是常数时间,不支持随机存取。除了具有所有顺序容器都有的成员函数以外,还支持8个成员函数:

函数名作用函数名作用
push_front在前面插入unique删除所有和前一个元素相同的元素(要做到元素不重复,则在unique之前还需要sort)
pop_front删除最前面的元素merge合并两个链表,并清空被合并的那个
sort排序(但不支持STL的算法sortreverse颠倒链表
remove删除和指定值相等的所有元素splice在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素

例程:双向链表的例程

图4.1 程序1

图4.2 程序1续1

template <class T>

void PrintList(const list<T> & lst) {

//不推荐的写法,还是用两个迭代器作为参数更好

int tmp = lst.size();

if( tmp > 0 ) {

typename list<T>::const_iterator i;

i = lst.begin();

for( i = lst.begin();i != lst.end(); i ++)

cout<<*i<<“,”;

}

}//typename用来说明 list<T>::const_iterator是个类型 //在vs中不写也可以

int main(){

list<A> lst1,lst2;

lst1.push_back(1);lst1.push_back(3); lst1.push_back(2);lst1.push_back(4);

lst1.push_back(2);

lst2.push_back(10);lst2.push_front(20);

lst2.push_back(30);lst2.push_back(30);

lst2.push_back(30);lst2.push_front(40); lst2.push_back(40);

cout<<“1)”;PrintList(lst1);cout<<endl;

//1)1,3,2,4,2

cout<<“2)”;PrintList(lst2);cout<<endl;

//2)40,20,10,30,30,30,40

lst2.sort();

图4.3 程序1续2

图4.4 程序1 续3

图4.5 程序1 续4

第五节 函数对象

1.函数对象定义

函数对象是个对象,但是用起来看上去像函数调用,实际上也执行了函数调用。若一个类重载了运算符“()”,则该类的对象就成为了函数对象。

例如:

class CMyAverage{

public:

double operator()(int a1, int a2, int a3){

return (double)(a1+a2+a3)/3;

}

};

CMyAverage agerage;

cout<<agerage(3,4,5);//输出为4

2.STL里有模板举例

(1)template<class InIt, class T, class Pred>

T accumulate(InIt first, InIt last, T val, Pred pr);

pr就是一个函数对象,对[first,last)中的每个迭代器I,执行val = pr(val,*I),返回最终的val。

pr也可以是个函数。

Dev C++中的Accumulate源代码1:

template<typename _InputIterator, typename _Tp>

_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init){

for(;__first!=__last;++__first)

__init = __init + *__first;

return __init;

}

//typename等价于class

Dev C++中的Accumulate源代码2:

template<typename _InputIterator, typename _Tp, typename _BinaryOperation>

_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,_BinaryOperation __binary_op){

for(;__first!=__last;++__first)

__init = __binary_op(__init + *__first);

return __init;

}

调用accumulate时,和__binary_op对应的实参可以是个函数或函数对象

(2)greater函数对象类模板

template<class T>

struct greater : public binary_function<T, T, bool> {

bool operator()(const T& x, const T& y) const {

return x>y;

}

};

可以看出,在这里只有x>y的时候才会返回true。

list有两个sort函数,第一个是前面所说的不带参数的sort函数,它将list中的元素按“规定的比较方法”升序排列。

list还有另一个sort函数:

template <class T2>

void sort(T2 op);

可以用op来比较大小,即op(x,y)为true则认为x应该排在前面。

例程:

#include <list>

#include <iostream>

#include <iterator>

using namespace std;

class MyLess {

public:

bool operator()(const int & c1, const int & c2)

{

return (c1%10)<(c2%10);

}

};

int main()

{

const int SIZE = 5;

int a[SIZE] = {5,21,14,2,3};

list<int> lst(a,a+SIZE);

lst.sort(MyLess()); //调用的第二种sort排序,由MyLess()来确定,准确的说是()确定

Print(lst.begin(),lst.end());

cout<<endl;

lst.sort(greater<int>());//greater<int>()是个对象

Print(lst.begin(),lst.end());

cout<<endl;

return 0;

}

输出结果:21,2,3,14,5,(按照个位数排序)

21,14,5,3,2,(倒序排列)

3.STL中使用自定义的“大”“小”关系

关联容器和STL中许多算法,都是可以用函数或函数对象自定义比较器的。在自定义了比较器op的情况下,以下三种说法是等价的:

①x小于y;

②op(x,y)返回值为true;

③y大于x。

例题:写出MyMax模板

#include <iostream>

#include <iterator>

using namespace std;

class MyLess {

public:

bool operator()(const int & c1, const int & c2)

{

if((c1%10)<(c2%10))

return true;

elsereturn false;

}

bool MyCompare(int a1, int a2)

{

if((a1%10)<(a2%10))

return false;

else

return true;

}

};

template <class T, class Pred>

T MyMax(T first, T last, Pred myless)

{

       T tmpMax= first;//tmpMax是一个迭代器

       for(;first!=last;++first)

              if(myless(*tmpMax,*first))

                     tmpMax = first;

       return tmpMax;

};

 

 

int main()

{

int a[] = {35,7,13,19,12};

cout<<*MyMax(a,a+5,MyLess())<<endl;//个位数最大

cout<<*MyMax(a,a+5,MyCompare)<<endl;//个位数最小

return 0;

}