第八周 标准模板库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 | 不支持 |
例程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个成员函数:
函数名 | 作用 | 函数名 | 作用 |
push_front | 在前面插入 | unique | 删除所有和前一个元素相同的元素(要做到元素不重复,则在unique之前还需要sort) |
pop_front | 删除最前面的元素 | merge | 合并两个链表,并清空被合并的那个 |
sort | 排序(但不支持STL的算法sort) | reverse | 颠倒链表 |
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;
}