STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。STL 是 C++ 标准库的一部分,不用单独安装。C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环队列,set 的底层为红黑树,hash_set 的底层为哈希表。 下面介绍的几个常用容器,如果能动手实现其中的例子,将对掌握他们的用法大有裨益。

vector (需#include<vector>

vector翻译为向量——长度根据需要自动改变的的数组。早题目中,有时碰到普通数组会超内存的情况,这时用vector会让问题简单很多,此外vector还用邻接表的方式存储图,这对无法使用邻接矩阵的题目、又害怕使用指针实现邻接表的读者非常友好,写法也很简洁。

vector的定义

1
vector<typename> name;

这里的typename可以使任何类型,既可以是int、double、char等,也可以是STL容器,如vector、set、queue等。值得指出的是,如果typename也是一个STL容器,定义时记得在>>符号之间加上空格,因为一些C++11之前的标准编译器会将之视为移位操作,导致编译错误。下面是几个应用案例。

1
2
vector<int> name1;
vector<vector<int> > name2; //>>之间要加空格

对于初学者,可以将二维vector数组当作两个维都可以变长的二维数组来理解

定义vector数组的格式是:

1
vector<typename> Arrayname[arraySize];

注意掌握vector的几种常见构造函数:

1
2
3
4
5
6
> vector()//创建一个空vector
> vector(int nSize)//创建一个vector,元素个数为nSize
> vector(int nSize,const t& t)//创建一个vector,元素个数为nSize,且值均为t
> vector(const vector&)//复制构造函数
> vector(begin,end)//复制[begin,end)区间内另一个数组的元素到vector中
>

vector容器内元素的访问

有两种方式:下标访问和迭代器访问

通过下标访问

和访问普通数组一样,对一个定义为vector<typename>vivector容器,直接访问vi[index]即可。当然这里的下标是0到vi.size()-1,访问此范围之外的元素可能会出错。

通过迭代器访问

迭代器可以理解为一种类似指针的东西,定义为:

1
vector<typename>::iterator it;

这样it就是一个vector<typename>::iterator类型的变量,这样就得到了迭代器it,并可以通过*it来访问vector的元素。

例如对于下面的vector容器可以通过类似下标和指针访问数组的方式来访问容器内的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<vector>
using namespace std;
int main(){
vector<int> vi; //vector定义
for(int i=1;i<=5;i++){
vi.push_back(i);
} //vi.begin()为取vi的首元素地址,而it指向这个地址
vector<int>::iterator it=vi.begin();
for(int i=0;i<5;i++){
printf("%d ",*(it+1)); //输出vi[i]
}
return 0;
}

从这里可以看出,vi[i]*(vi.begin()+i)是等价的。

上面介绍了begin()函数时取vi的首元素地址,还应该指出end()函数,和begin()函数不同的是,end()vi尾元素地址的下一个地址。其作为迭代器末尾的标志,不存储任何元素。

除此之外,迭代器还支持自加操作++itit++(自减操作同理),于是有了另一种遍历vector的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<vector>
using namespace std;
int main(){
vector<int> vi; //vector定义
for(int i=`;i<=5;i++){
vi.push_back(i);
} //vector迭代器不支持it<vi.end()写法,因此循环条件只能用it!=vi.end()
for(vector<int>::iterator it=vi.begin();it!=vi.end();it++){
printf("%d ",*it); //输出vi[i]
}
return 0;
}

最后指出,在常用STL容器中,只有vectorstring中才允许使用vi.begin()+3这种迭代器加上整数的写法

vector常用函数实例解析

push_back()

本函数在vector后面添加一个元素x,时间复杂度为O(1)

pop_back()

本函数删除vector尾部元素,时间复杂度为O(1)

size()

获得vector中元素的个数,时间复杂度为O(1),size()返回的是unsigned类型,不过一般来说用%d不会有很大的问题,这一点对所有STL容器都是一样的。

clear()

清空vector中所有元素,时间复杂度O(N)

insert()

insert(it,x)vector的任意迭代器it处插入元素x,时间复杂度O(N)

erase()

有两种用法:删除单个元素、删除一个区间内所有元素,时间复杂度均为O(N)
删除单个元素:erase(it)删除迭代器为it处的元素
删除一个区间内所有元素:erase(first,last)删除[first,last)内所有元素

vector常见用途

存储数据

在元素数目不确定时作为数组使用可以节省空间

用邻接表存储图

set (需#include<set>

set的定义

1
2
set<typename> name;	//set的定义
set<typename> Arrayname[arraySize]; //set数组定义

set内元素的访问

只能通过迭代器访问

1
set<typename>::iterator it;

由于除了vectorstring以外的STL容器都不支持*(it+i)的访问方式,因此只能按如下方式枚举:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<set>
using namespace std;
int main(){
set<int> st; //set定义
set.insert(3);
set.insert(5);
set.insert(2);
set.insert(3); //注意:不支持it<st.end()的写法
for(set<int>::iterator it=st.begin();it!=st.end();it++){
printf("%d ",*it); //输出st[i]
}
return 0;
}
//输出结果:2 3 5

可以发现,set内元素自动递增排序且去除重复元素

set常用函数实例解析

insert()

将元素x插入set容器中,并自动递增排序和去重,时间复杂度O(logN)

find()

find(value)返回set中对应值为value的迭代器,时间复杂度为O(logN)

erase()
删除单个元素

删除单个元素有两种方法:

  • st.erase(it)it为所需要删除元素的迭代器,时间复杂度为O(1),可以结合find()函数来使用
  • st.erase(value)value为所需要删除元素的值,时间复杂度为O(logN)
删除一个区间内所有元素

st.erase(first,last)删除一个区间内所有元素,时间复杂度为O(last-first)。

size()

获得set内元素的个数,时间复杂度O(1)

clear()

清空set,复杂度为O(N)

set的常见用途

最主要的作用是去重并按照升序排序,因此如果碰到需要去重但是不方便直接开数组的情况,可以尝试用set解决。
延伸:set中元素是唯一的,如果需要处理不唯一的情况,则需要使用multiset,另外C++11引入了unordered_set,可以用来处理只去重不排序的需求。

string (需#include<string>

string的定义

1
2
string str;
string str2="abcd";

string中内容的访问

通过下标访问
1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
#include<string>
using namespace std;
int main(){
string str="abcd";
for(int i=0;i<str.length();i++){
printf("%c",str[i]);
}
return 0;
}

如果要读入和输出整个字符串,则只能用cincout

1
2
3
4
5
6
7
8
9
#include<stdio.h>
#include<string>
using namespace std;
int main(){
string str;
cin>>str;
cout<<str;
return 0;
}

如果希望用printf输出string,则需要用c_str()进行类型转换。

1
2
3
4
5
6
7
8
#include<stdio.h>
#include<string>
using namespace std;
int main(){
string str="abcd";
printf("%s\n",str.c_str());
return 0;
}
通过迭代器访问

迭代器的定义方式

1
string::iterator it;

那么就可以利用迭代器进行访问

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
#include<string>
using namespace std;
int main(){
string str="abcd";
for(string::iterator it=str.begin();it!=str.end();it++){
printf("%c",*it);
}
return 0;
}

string常用函数实例解析

operator+=

可以将两个string拼接起来

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#include<string>
using namespace std;
int main(){
string str1="abcd",str2="xyz",str3;
str3=str1+str2;
str1+=str2;
cout<<str1<<endl;
cout<<str3<<endl;
return 0;
}
compare operator(==、!=、<、>、<=、>=)

两个string类型可以直接利用上述比较符号比较大小,比较规则是字典序

length()/size()

返回string的长度

insert()
insert(pos,string)

pos号位置加入字符串string

insert(it,it2,it3)

it为原字符串欲插入位置,it2it3为待插入字符串首尾迭代器,用来表示串[it2,it3)将被插在it的位置上

erase()
str.erase(it)

删除单个元素,it为需要删除的元素的迭代器

str.erase(first,last)

删除迭代器所指向的区间[first,last)

str.erase(pos,length)

pos为需要开始删除的起始位置,length为删除的字符个数

clear()

清空string的数据

substr()

substr(pos,len)返回从pos号位开始,长度为len的子串,时间复杂度为O(len)

string::npos

其值为-1,但因为为unsigned_int型,因而实际为4294967295。用来作为find()函数失配时的返回值

find()
  • str.find(str2),当str2str的子串时,返回其在str中第一次出现的位置,如果str2不是str的子串,那么返回string::npos
  • str.find(str2,pos),从strpos号位开始匹配str2,返回值与上相同
replace()
  • str.replace(pos,len,str2)strpos号位开始,长度为len的子串替换为str2
  • str.replace(it1,it2,str2)str的迭代器[it1,it2)范围子串替换为str2