第八周 标准模板库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.顺序容器和关联容器中都有的成员函数

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

第三节 标准模板库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 容器和容器上面的迭代器

例程1：vector的遍历，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个成员函数：

例程：双向链表的例程

图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;

}