22/1/31STL

一、map（映射）

其实，数组就是一种映射。

int a[100];//定义了一个int到int的映射a[5]=25;//5映射到25

数组总是将int类型映射到其他基本类型（称为数组的基类型），同时带来一个问题：string映射成int，数组就不方便。这时就可以用map。
map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

（一）、map的用途

至少有以下三种情形
**1、**需要建立字符（串）与整数之间的映射，用map可以减少代码量
**2、**判断大整数（比如几千位）或者其他类型数据是否存在，可以把map当做布尔型数组使用（哈希表）
**3、**字符串与字符串之间的映射

#include

普通int数组a就是map a。
而如果是字符串到整型的映射，就必须使用string，而不能使用char，即map a。
map的键和值也可以是STL容器，比如：map mp。
当然，map的键和值都是唯一的

（二）、map 的访问

访问 map 的元素有两种方式，一种是通过下标访问；另一种是通过迭代器访问。
通过下标访问就像普通的数组元素访问，例如先定义map mp，然后就可以通过mp[‘c’]的方式来访问它对应的元素，如mp[‘c’]=124。
通过迭代器访问，先作如下定义：

map::iterator it；

因为map的每一对映射都有两个typename，所以，我们使用“it->first”来访问键，而使用“it->second”来访问值。

（三）、map 的常用函数

1、find()和 size()
find(key)是返回键为 key 的映射的迭代器，时间复杂度为 0(log2 n)，n 为 map 中映射的对数。
size()用来获得map中映射的对数，时间复杂度为O(1)。
2、clear()
用来清空 map，时间复杂度为 0(n)。
3、erase()
erase()可以删除单个元素，也可以删除一个区间内的所有元素。
1）删除单个元素
①erase(it)，it为要删除的元素的迭代器，时间复杂度为O(1)。
②erase(key)，key为要删除的映射的键，时间复杂度为O(log2 n)。
2）删除一个区间内的所有元素
erase(first，last)，first为区间的起始迭代器，last为区间的末尾迭代器的下一个地址，也就是左闭右开的区间[first,last)，时间复杂度为O(last-first)。

二、pair

pair 是“二元结构体”的替代品，将两个元素捆绑在一起，节省编码时间。

#include//头文件using namespace std;pairname;//定义//两个typename均可以是任意基本数据类型或者容器

相当于以下定义

struct pair{typename1 first;typename2 second;}

三、set（集合）

set是一个内部自动有序且不含重复元素的容器。
set 最主要的作用就是自动去重并按升序排序，因此遇到需要去重但是又不方便直接开数组的情况时可以使用。
set 中的元素是唯一的，其内部采用“红黑树”实现。

#include ；using namespace std；set name;//typename 可以是任何基本类型或者容器，name 是集合的名字

（一）、set常用函数

1、insert（）
插入一个元素
注意如果集合中已经存在某元素，再次插入不会产生任何效果，即集合中不会出现重复元素。
2、erase（）
删除一个元素。若集合中不存在这个元素，不进行任何操作。

erase(iterator) ;//删除定位器iterator指向的值erase(first,second);//删除定位器first和second之间的值erase(key_value);//删除键值key_value的值

set s;set::const_iterator iter;set::iterator first;set::iterator second;for(int i = 1 ; i <= 200 ; ++i){s.insert(i);} s.erase(s.begin());//第一种删除first = s.begin();second = s.begin();second++; second++;s.erase(first,second);//第二种删除s.erase(18);//第三种删除

lower_bound(key_value) ，返回第一个大于等于key_value的定位器
upper_bound(key_value)，返回最后一个大于等于key_value的定位器

set s;s.insert(1);s.insert(3);s.insert(4);cout<<*s.lower_bound(2)<

3、count（）
判断元素是否在set中

#includeusing namespace std;int main(){sets;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"1出现的次数:"<

4、size（）
获取元素个数
5、clear（）
清空

(二）、set的访问

set只能通过迭代器访问

set::iterator it;for(it = s.begin() ; it != s.end() ; ++it) cout<<*it<<" ";

四、vector（向量/ 变长数组）

“长度根据需要而自动改变的数组”
需要定义很大数组时可能出现“超出内存限制”的错误，如图的顶点太多，使用邻接矩阵时会超出内存限制、使用指针实现邻接表有很容易出错，使用vector实现简洁方便且节省存储空间。

#includeusing namespace std;vectorname;

以上定义相当于定义了一个一维数组name[size]，但size不确定，长度可以根据需要而变化。

(一）、访问 vector 中的元素一般有两种方式

1、通过“下标”访问。
例如，对于容器 vector v，可以使用 v[index]来访问它的第 index 个元素。其中，0≤index≤v.size()-1，v.size()表示 vector 中元素的个数。
2、通过“迭代器”访问。
可以将迭代器（iterator）理解为一种类似指针的变量。其定义为：

vector::iterator it;

例如：

vector::iterator it= v.begin();for(int i = 0; i <= 5; i++) printf("%d ",*(it + i));

（二）、vector常用函数

1、push_back()
push_back(x)用来在 vector 后面添加一个元素 x，时间复杂度为 0(1)。
2、size()
如果是一维数组，size()用来获得 vector 中元素的个数；
如果是二维数组，size()用来获得vector 中第二维的元素个数，时间复杂度为 0 (1)。
3、pop_back()
pop_back()用来删除 vector 的尾元素，时间复杂度为 0(1)。
4、clear()
clear()用来清空 vector 中的所有元素，时间复杂度为 0(n)，其中 n 为 vector 中元素的个数。
5、insert ()
insert(it，x)用来向 vector 任意迭代器 it 处插入一个元素 x，时间复杂度为 0(n)。
6、erase()
erase()用来删除 vector 中的元素，有两种用法。
一种是 erase(it)，删除迭代器 it 处的元素；
另一种是 erase(first，last)，删除左闭右开区间[first，last)内的所有元素。

五、string

在C语言中，一般使用字符数组char str[]来存放字符串，但是操作麻烦，容易出错。C++在STL中加入了string类型，对字符串常用的需求功能进行了封装，使得操作起来更加方便，且不必担心内存是否足够、字符串的长度等问题。

#includeusing namespace std;string name;string str="hello";

（一）、string的访问

1、就像普通字符数组一样操作。

string str= “ abcd “ ;for(int i = 0; i < str.length(); i++) printf( “ %c “ ,str[i]);// 输出 abcd

如果要读入或者输出整个字符串，一般只用cin和cout。如果非要用printf，则需要用c_str()将string转换成字符数组。

string str; cin>>str; cout<

2、通过迭代器，主要与insert()、erase()等函数配合使用。
先定义string迭代器：

string::iterator it;

然后就可以通过“*it”来访问string里的每一个字符了，而且string和vector一样，支持直接对迭代器进行加减某个数字，如str.begin()+3等。例如：

string str="abcdefg";for(string::iterator it = str.begin()+2; it != str.end(); it++)printf("%c",*it);//输出cdefg

（二）、string的运算

1、“加法”运算。加法是把两个字符串直接拼接起来。例如：

string str1= “ abc “ ,str2= “ xyz “ ,str3;str3 = str1 + str2;str1 += str2;cout << str1 << endl;// 输出 abcxyzcout << str3 << endl;// 输出 abcxyz

2、“关系”运算，是按照字典序比较两个string 类型的大小。例如：

string str1= “ aa “ ,str2= “ aaa “ ,str3= “ abc “ ;if(str1 < str2) printf( "OK1");// 输出 OK1if(str1 < str3) printf( "OK2" );// 输出 OK2

(三）、string的常用函数

1、length()和size()
都是用来返回string的长度（字符个数），时间复杂度O(1)。
2、clear()
清空string中所有元素，时间复杂度O(1)。
3、substr(pos,len)
返回从pos号位置开始、长度为len的子串，时间复杂度O(n)
4、insert()
多种写法，时间复杂度都是O(n)。
insert(pos,string) 表示在pos号位置插入字符串string。
insert(it,it2,it3) it为原字符串的欲插入位置，it2和it3为待插入字符串的首尾迭代器（左闭右开区间）。
5、erase()
erase()可以删除单个元素，也可以删除一个区间内的所有元素，时间复杂度均为O (n)。
1）erase(it) 删除单个元素，it为要删除的元素的迭代器。
2）删除一个区间内的所有元素可以用两种方法。
①erase(first，last)，first为区间的起始迭代器，last为区间的末尾迭代器的下一个地址，也就是左闭右开的区间［first,last)。
②erase(pos，length)，pos为需要删除的字符串起始位置，length为要删除的字符个数。
6、find()
1）str.find(str2)，当str2是str的子串时，返回其在str中第一次出现的位置；否则返回string::npos。string::npos是一个常数，其本身的值等于-1，但由于是unsigned int类型，因此，也可以认为是unsigned int类型的最大值（4294967295）。
2）str.find(str2,pos)，是从str的pos号位开始匹配str2，返回值同str.find(str2)。
以上两种写法的时间复杂度都是O(n*m)，其中n和m分别为str和str2的长度。
7、replace()
str.replace(pos,len,str2)表示把str从pos号位开始、长度为len的子串替换为str2。也可以写成str.replace(it1,it2,str2)，表示把str的迭代器it1~it2范围内（左闭右开区间）的子串替换为str2。
时间复杂度都是O(str.length)。

补充函数 1、max()、min()、abs()和 swap()

max(x,y)和min(x,y)分别返回 x 和 y 中的较大值和较小值，且参数必须是两个，可以是浮点数。如果要返回 3 个数 x、y、z 的最大值，可以使用max(x,max(y,z))的方法。
abs(x)是返回 x 的绝对值，x 必须是整数。如果要求浮点数的绝对值，可以使用 math 头文件下的 fabs(x)。
swap(x,y)用来交换 x 和 y 的值。

2、reverse()

reverse（it，it2）可以将数组指针在 [it ~ it2)之间的元素，或容器的迭代器在[it ~ it2)范围内的所有元素进行反转。

int a[10] = {10,11,12,13,14,15};reverse(a,a+4);//将a[0]到a[3]这4个元素反转for(int i = 0; i < 6; i++) printf("%d ",a[i]);//输出13 12 11 10 14 15string str = "abcdefghi";reverse(str.begin()+2,str.begin()+6);for(int i = 0; i < str.length(); i++) printf("%c",str[i]);//输出abfedcghi

3、next_permutation()

求出一个序列在全排列中的下一个序列。
例如，n=3 的全排列为：123，132，213，231，312，321，所以 231 的下一个排列就是 312。

int a[10] = {1,2,3};do{printf("%d %d %dn",a[0],a[1],a[2]);}while(next_permutation(a,a+3));//a[0],a[1],a[2]三个元素的排列//next_permutation在达到全排列的最后一个时会返回false

4、fill () 和memset的区别

fill ()和 memset可以把数组或容器的某一段区间赋为某个相同的值。
fill()的赋值可以是数组类型对应范围中的任意值。

int a[5];fill(a,a+5,123);// 将 a[0] 到 a[4] 均赋值为 123for(int i = 0;i < 5;i++) printf( “ %d “ ,a[i]);

memset 只能赋值0和-1，赋值1的话，值为正整数。

5、sort（排序）

使用的排序方法类似于快排，时间复杂度为n*log2(n)，效率较高。

#includesort(start,end,compare());//从小到大的排序bool compare(int a,int b){return a>b;}sort(a,a+10,compare);

compare()也可以用c++标准库的函数

less()//从小到大排序greater()//从大到小排序

6、unique（去重）

去重，即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，指重复元素的位置被不重复的元素给占领了，重复的元素排到了后面（也就是仍然在数组中）。
由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。
两种访问方式
1、unique（start,end）
同sort

#include #include using namespace std;int a[10]={5,8,5,12,6,8,9,5,12,3};int len;//无重复元素的数组的长度 int main(){sort(a,a+10);//先排序len=unique(a,a+10)-a;//去重，返回的是a去重后的尾地址。for(int i=0;i 2、迭代器

iterator unique(iterator it_1,iterator it_2);

对容器中[it_1，it_2)范围的元素进行去重，返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
和erase函数一起使用可以删除重复元素，容器的长度也发生了改变。

vector a ={1,3,3,4,4,9}; vector::iterator it1 = a.begin(); vector::iterator it2 = a.end(); vector::iterator newend; newend = unique(it1,it2); //注意unique的返回值 a.erase(newend,it2);