[数据结构与算法]22/1/31 STL

一、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<map>   //头文件
using namespace std;
map<tpyename1,typename2>name;  //定义一个map
/*typename1 映射前的类型（键key） 
tapename2 映射后的类型（值value） 
name  映射的名字
*/

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

（二）、map 的访问

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

 map<typename1,typename2>::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<utility>	//头文件
using namespace std;
/*因为map的内部实现中涉及pair，
因此添加map头文件时会自动添加utility头文件，
此时可以省去utility头文件。
*/
pair<typename1,typename2>name;//定义
//两个typename均可以是任意基本数据类型或者容器

相当于以下定义

struct pair{
	typename1 first;
	typename2 second;
}

三、set（集合）

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

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

（一）、set常用函数

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

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

set<int> s;
set<int>::const_iterator iter;
set<int>::iterator first;
set<int>::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<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(4);
	cout<<*s.lower_bound(2)<<endl;
	cout<<*s.lower_bound(3)<<endl;
	cout<<*s.upper_bound(3)<<endl;

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

#include<set>
using namespace std;
int main(){
	set<int>s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(1);
	cout<<"1出现的次数:"<<s.count(1)<<endl;
	cout<<"4出现的次数:"<<s.count(4)<<endl;
	return 0;
	}

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

(二）、set的访问

set只能通过迭代器访问

set<typename>::iterator it;
/*即先定义一个迭代器，
然后使用“*it”来访问set中的元素。
*/
for(it = s.begin() ; it != s.end() ; ++it) 
 cout<<*it<<" ";

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

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

#include<vector>
using namespace std;
vector<typename>name;
/*typename可以为任何基本类型，例如int、double、char、结构体等，
也可以是STL标准容器，如vector、queue等。
*/

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

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

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

vector<typename>::iterator it;

例如：

vector<int>::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类型，对字符串常用的需求功能进行了封装，使得操作起来更加方便，且不必担心内存是否足够、字符串的长度等问题。

#include<string>
using 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<<str<<endl;
   printf("%s\n",str.c_str());

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;
// 输出 abcxyz
cout << str3 << endl;
// 输出 abcxyz

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

string str1= “ aa “ ,str2= “ aaa “ ,str3= “ abc “ ;
if(str1 < str2) 
	printf( "OK1");
	// 输出 OK1
if(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 15

string 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 %d\n",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] 均赋值为 123
for(int i = 0;i < 5;i++) 
	printf( “ %d “ ,a[i]);

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

5、sort（排序）

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

#include<algorithm>
sort(start,end,compare());
/*start是要排序的数组的起始地址 end
	是要排序的数组的最后一位的地址 
	method是排序方法，分为从小到大和从大到小。不写时，为默认的从小到大。
*/

//从小到大的排序
bool compare(int a,int b){
	return a>b;
	}


sort(a,a+10,compare);

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

less<typename>()//从小到大排序
greater<typename>()//从大到小排序

6、unique（去重）

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

#include <iostream>
#include <algorithm>
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<len;i++)
		cout<<a[i]<<endl;//输出排序后的数组  
	return 0; 
 } 
/*Output:
3
5
6
8
9
12
*/

2、迭代器

   iterator unique(iterator it_1,iterator it_2);

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

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