STL之集合

1.集合定义：

1. 确定性 表示一个元素要么在这个集合内，要么不在。（这个很水很容易理解）
2. 互异性 表示一个集合当中所有元素都是不一样的，不存在在一个集合中，出现两个一模一样的元素
3. 无序性 表示一个集合当中的元素没有顺序，就像班级调座位一样，谁都可以坐前排，谁都可以坐后排，是平等地位的。
4. 应用：在信息学当中，要用到集合，就可以使用set这个容器。

2.STL-Set

3.Set的用法

1. 定义方法：使用 $set$ 前，必须先添加 $set$ 头文件，即 #include <set>，同时，必须要有using namespacestd。定义一个 set 的方法如下： set<typename> name;其中，$typename$ 可以是任何基本类型或者容器，$name$ 是集合的名字。也可以定义 $set$ 数组，例如：set<int> st[100];这样 st[0]～st[99] 中的每一个元素都是一个 $set$ 容器。
2. 访问方法：$set$只能通过迭代器访问。

set<int > s;  //普通的定义（不允许元素重复）
multiset<double > s;  //（允许集合中元素重复）
struct rec{...};
set<rec > s;  //结构体

3. Set 常用的函数

a.insert(5); //在a集合里插入一个元素5
a.size(); //获取集合的长度（即有几个数）
a.clear(); //清空集合a中的所有元素
a.empty(); //判断集合a是否为空
a.begin(); //集合a的第一个位置
a.end(); //集合a的最后一个元素的下一个位置，就没有的意思
a.rbegin() 返回一个逆向迭代器，指向倒数第一个元素，即最后一个元素的位置。
a.insert(x) 把一个元素 x 插入到集合 a中，时间复杂度为O(logn)。
a.erase(x) 从 a 中删除所有等于 x 的元素。
a.find(x)//在集合s中查找等于 x 的元素，并返回指向该指针的迭代器。

若不存在，则返回 s.end() 。时间复杂度O(logn)。

a.count(x)//返回集合 s 中等于 x 的元素个数，时间复杂度O(k+logn)，

其中 k 为元素 x 的个数。
set<int > ::iterator it ;  //定义集合类型的迭代器。
s.begin() 是指向集合中最小元素的迭代器。
s.end() 是指向集合中最大元素的下一个位置的迭代器。

set<int > :: iterator it;  it是一个迭代器
a.erase(it); //删除迭代器当前存着的集合a的元素

2. STL之映射

1.定义

1. $map$ 翻译为映射，是 $STL$ 中的常用容器。 其实，数组就是一种映射，比如：int a[100]；就是定义了一个 $int$ 到 $int$ 的映射。而 a[5]=25; 就是把 $5$ 映射到 $25$。数组总是将 $int$类型映射到其它基本类型（称为数组的基类型），这同时也带来了一个问题，有时候我们希望把 $string$ 映射成一个 $int$ ，数组就不方便了。 这时就可以使用 $map$，$map$ 可以将任何基本类型（包括 $STL$ 容器）映射到任何基本类型（包括 $STL$ 容器）。
2. $map$ 的用途至少有以下三种情形：
   1）需要建立字符（串）与整数之间的映射。
   2）可以用大整数做下标，来实现数组计数。
   3）字符串与字符串之间的映射。

2.定义 $map$ 的方法

1、必须先添加map头文件，即#include <map>，同时必须要有“using namespace std”。
2、定义一个map的方法为：map<typename1,typename2> name;
其中，typename1是映射前的类型（键key），typename2是映射后的类型（值value），name为映射的名字。
例如：普通int数组a就是map<int,int> a。而如果是字符串到整型的映射，就使用string和int建立映射，即map<string,int> a。

三、使用map的方法
1、map 的访问
访问 map 的元素有两种方式，一种是通过下标访问；另一种是通过迭代器访问。
（1）、用下标访问
通过下标访问就像普通的数组元素访问。
例如：定义了map<char,int> mp， 那么：就可以直接访问mp[‘c’]， 如mp[‘c’]=124。
（2）、通过迭代器访问，通常遍历整个映射时，会用到它。
例如：定义了map<char,int> mp，且做了多次操作后，输出所有的值。
如mp[‘c’]=124，mp[‘t’]=100,  mp[‘c’]=200   
map<char,int>::iterator it；
因为map的每一对映射都有两个typename，所以，我们使用“it->first”来访问“键”(下标)，而使用“it->second”来访问“值”（内容）。 
for(it=mp.begin(), it !=mp.end(), it++)
cout<<it->first<<':'<<it->second<<endl;
2. Map 使用方法总结：
map<key_type,value_type>name;//普通的定义
map<string,int>::iterator it; //定义映射类型的迭代器。
it->first 引用键值， it->second 引用映射值。
m.size();  元素个数；
m.empty();  判m是否空；
m.clear(); 清空m；
m.begin(); 是指向map中最小元素的迭代器。
m.end(); 是指向map中最大元素下一个位置的迭代器。

3.STL之动态数组

一、标准模板库（Standard Template Library，STL）

具有以下的组件：

1. 容器：容纳包含一组元素的对象。
2. 迭代器：提供访问容器的方法
3. 函数对象
4. 算法

二、STL之向量——vector

1. $vector$ 是 $c++$ 标准库提供的一个变长数组类型，它可以像数组一样进行数据的存储和访问。
2. $vector$ 会根据需要自动扩展其自身的容量来容纳更多的数据。
3. $vector$ 的内部存储结构和数组一样，使用的是一段连续的存储空间。

三、vector的优缺点

四、vector的声明和初始化

五、vector的常用函数

六、 vector 的访问

1. 第一种是通过“下标”访问。例如，对于容器 vector v，可以使用 v[index]来访问它的第 index 个元素。其中，0≤index≤v.size()-1，v.size()表示 vector 中元素的个数。
2. 第二种方式是通过“迭代器”访问。迭代器类似于指针，指向vector中元素的位置，可以使用迭代器来访问vector中的元素。迭代器的声明和初始化

t2=a.end()-1; t2指向数组a结束位置

vector<int>::iterator it= a.begin();

for(int i = 0; i <= 5; i++) printf("%d ",*(it + i));

七、配合迭代器使用的函数

4.STL之栈

一、什么是栈

二、stack容器

三、Stack 使用方法总结：

四、练习

• 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，……，则车辆出站的顺序为
  A. 1, 2, 3, 4, 5
  B. 1, 2, 4, 5, 7
  C. 1, 4, 3, 7, 6
  D. 1, 4, 3, 7, 2

• 设栈S和队列Q的初始状态为空，元素e1，e 2，e 3，e 4，e 5，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2 ，e 4 ，e 3，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为。
  A．2
  B．3
  C．4
  D．5