STL 数据结构一本通

liyao2025 · 2025-11-26 13:07:38 · 个人记录

A.STL之集合

1.集合定义：

把一些元素按照某些规律放在一起，就形成了一个集合。比如说每个班级就是一个集合，竞赛班也是一个集合，每间学校也是一个集合，等等。

特点：确定性、互异性、无序性。

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

4. 应用：在信息学当中，要用到集合，就可以使用set这个容器。

   但是正如刚刚所说的，如果一个集合没有顺序，那么我们在遍历这个集合的时候存在着困难，因此，我们还是会按照顺序来整理元素（ 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<typename>::iterator it;然后使用“*it”来访问 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的元素

# B. STL之映射
## 1.定义
1. $map$ 翻译为映射，是 $STL$ 中的常用容器。
其实，数组就是一种映射，比如：```int a[100]；```就是定义了一个 $int$ 到 $int$ 的映射。而 ```a[5]=25;``` 就是把 $5$ 映射到 $25$。数组总是将 $int$类型映射到其它基本类型（称为数组的基类型），这同时也带来了一个问题，有时候我们希望把 $string$ 映射成一个 $int$ ，数组就不方便了。 ![1](https://huatu.98youxi.com/markdown/work/uploads/upload_8abfd392f627c622057ee8f3507b4dc3.PNG)这时就可以使用 $map$，$map$ 可以将任何基本类型（包括 $STL$ 容器）映射到任何基本类型（包括 $STL$ 容器）。 ![2](https://huatu.98youxi.com/markdown/work/uploads/upload_4e18fbd7c8a7ca55e75cefc2650b0d23.PNG)

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中最大元素下一个位置的迭代器。

   
   # C.STL之动态数组
   ## 1、标准模板库
   是HP公司开发的一个C++模板库，包含一些常用的数据结构和算法。

具有以下的组件：

1. 容器：容纳包含一组元素的对象。

2. 迭代器：提供访问容器的方法

3. 函数对象

4. 算法

2、STL—vector

4.头文件#include<vector>

3、vector的优缺点

优点：

（1）进行插入删除操作后会动态连接

（2）有很多函数可以调用

（3）动态分配内存，节省空间

缺点：

（1）需要记忆函数较多

（2）Vector变量动态改变时，各参数值可能需要重新获取

（3）Vector数组的数组名不是数组的地址，部分函数需要使用迭代器访问容器。

4、vector的声明和初始化

(1) vector<数据类型>a,b,c,d;//空的

(2) vector<数据类型>a(10);//定义一个长度为10，下标从0~9的动态数组，数组会默认初始化为0

(3) vector<数据类型>a(10,1);//定义一个长度为10，下表从0~9的动态数组，数组初始化为1

(4) vector<数据类型>a(b);////用动态数组b来创建动态数组a，整体复制性赋值

(5) vector<数据类型>().swap(a); 清空a,并释放空间; //惯用法。

5、vector的常用函数

(1)a.size()返回数组长度

(2)a.resize(n)重设数组的大小。

(3)a.clear()清空数组所有元素

(4)a.empty()判断数组是否为空，是返回1，否返回0

(5)a.swap(b)交换a和b两容器的值

(6)a.push_back(x)在动态数组a尾部添加元素x

(7)a.pop_back()删除数组尾部元素

6、 vector 的访问

访问 vector 中的元素一般有两种方式。

1. 第一种是通过“下标”访问。例如，对于容器 vector<int> v，可以使用 v[index]来访问它的第 index 个元素。其中，0≤index≤v.size()-1，v.size()表示 vector 中元素的个数。

2. 第二种方式是通过“迭代器”访问。迭代器类似于指针，指向vector中元素的位置，可以使用迭代器来访问vector中的元素。迭代器的声明和初始化

(1)vector<数据类型>::iterator t1,t2;// 创建t1,t2两个迭代器

t1=a.begin(); t1指向数组a的开始位置

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

a.begin()指向数组a的开始位置

a.end()指向数组a的结束位置的下一个位置

例如：

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

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

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

(1)a.insert(t1,2)//在数组下标为t1的位置插入一个元素2，其他元素向后移一位

(2)a.erase(t1)//删除第t1个位置的元素，其他元素向前移动一位

(3)a.erase(t1,t2+1)//删除t1~t2区间内的元素，其余元素向前移动

(4)reverse(t1,t2+1)//反转t1~t2区间内的元素

(5)sort(t1,t2+1)//对数组元素从小到大排序

D.STL之栈

1、什么是栈

栈也是一种操作（或者说运算）受到限制的特殊线性表。

其插入和删除操作都限制在表的一端进行，这一端被称为“栈顶（top）”，相对的另一端称为“栈底（bottom）”。

两种操作：

1“进栈（PUSH）”或者“压栈”

2.“出栈（POP）”。

栈的特点是：“先进后出（FILO，First In Last Out）”

2、stack容器

stack翻译为栈，是STL中实现的一个“后进先出”的容器，它提供了栈操作中的很多命令，非常方便。

如：

访问栈顶元素：top()

删除栈顶元素：pop()

元素放入栈顶：push()

使用stack前，要先添加stack头文件，即#include <stack>，同时，必须要有“using namespace std”。

定义一个 stack 的方法如下：

stack<typename> name;

其中，typename 可以是任何基本类型或者容器，name 是栈的名字。

3、Stack 使用方法总结：

s.push(x);入栈, 将x 接到栈s的顶端。

s.pop(); 出栈,弹出栈顶端s的第一个元素，注意，并不会返回被弹出元素的值。

s.top(); 访问栈顶端元素， 即最早被压入栈s的元素。

s.empty(); 判断栈是否为空 , 当栈空时，返回true。

s.size(); 访问栈中的元素个数。

4、练习

• 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 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 :::info[答案] C :::

• 设栈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 :::info[答案] B :::

E.队列