【算法竞赛C++STL基础】栈，链表，队列，优先队列，map,set以及迭代器的用法

1，前知——模板函数的实现

函数模板的实现

template
T min (T a[] , int n ){

}

// 函数模板大致的书写方式，实际上就是多了个 template < class T > // 把 T 当成万能的数据结构

---

---

---

template <class T>
T min (T a[] , int n ){
    T minv = a[0] ;
    for(int i = 1 ; i < n ; i ++ ){
        minv = min(minv,a[i]) ; 
    }
    return minv;
}

2, hash 表

1，定义

哈希表实际上就是一种简单的映射关系，就和桶排序一样的效果，当前他一般只咉射到ASCII表的范围内，在范围外的咉射一般来说不是很好实现。

2,ASCII码表

记住几个重要的点 ：

48 - 0 / / 9

65 - A // 25

97 - a // 25

3，咉射关系

#include <iostream>
using namespace std ;
const int N = 256 ; // 2的八次方
int hash[N] ; 
int main () {
    // hash[i] ++ ; 
    return 0 ; 
}

---

---

---

3，迭代器

---

---

---

4，STL关系

1,stl 的基础关系

o容器：可容纳各种数据类型的数据结构。

o迭代器：可依次存取容器中元素的东西 // 相当于数组的下标

泛化 ：

一般来说容器中的迭代器为 vec.begin() , vec.end() | 数组中的迭代器为 q , q + n

迭代器中的差值一般是顺序存储的，插值个数 = 中间的个数

// 迭代器的存储 ： iterator 变量名

o算法：用来操作容器中的元素的函数模板。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。n函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

---

---

2,stl 的分类

1,相关分类

1. 顺序容器

vector：后部插入/删除，直接访问
deque：前/后部插入/删除，直接访问
list：双向链表，任意位置插入/删除

2. 关联容器

set：快速查找，无重复元素
multiset ：快速查找，可有重复元素
map：一对一映射，无重复元素，基于关键字查找
multimap ：一对一映射，可有重复元素，基于关键字查找

前2者合称为第一类容器

3. 容器适配器

stack：LIFO
queue：FIFO
priority_queue：优先级高的元素先出

---

2,相关简介

顺序容器

1. vector 头文件

实际上就是个动态数组。随机存取任何元素都能在常数时间完成O(1)。在尾端增删元素具有较佳的性能O(1)。

2. deque 头文件

也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector,常数较大)。在两端增删元素具有较佳的性能O(1)。

3. list 头文件

双向链表，在任何位置增删元素都能在常数时间完成O(N)。不支持随机存取。

上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关，只跟插入的时机有关。

关联容器

1. set/multiset: 头文件

set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。

2. map/multimap: 头文件

map与set的不同在于map中存放的是成对的key/value。

并根据key对元素进行排序，可快速地根据key来检索元素

map同multimap的不同在于是否允许多个元素有相同的key值。

上述4种容器通常以平衡二叉树方式实现，插入、查找和删除的时间都是 O(logN)

适配容器

1. stack :头文件

栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则 O（1）

2. queue :头文件

队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。O(1)

3. priority_queue :头文件

优先级队列。最高优先级元素总是第一个出列，O(logN)

---

---

3. STL 的相关函数的学习

3.1 STL函数中都含有的性质

1. .empty() // 判断是否为空 为空 == true
2. size() // 返回最多能放多少元素
3. swap() // 交换两个容器中的内容

---

---

3.2 vector,deque,list 三个容器中的特殊成员函数

1,迭代器

1. begin 返回指向容器中第一个元素的迭代器
2. end 返回指向容器中最后一个元素后面的位置的迭代器
3. rbegin 返回指向容器中最后一个元素的迭代器
4. rend 返回指向容器中第一个元素前面的位置的迭代器

---

---

2.顺序容器的基础函数

n.front() :返回容器中第一个元素的引用

n.back() : 返回容器中最后一个元素的引用

n.push_front() : 在容器的前面加入新元素 // list + dequeue

n.pop_front() ： 在容器的前面删除新元素 // list + dequeue

n.push_back(): 在容器末尾增加新元素

n.pop_back(): 删除容器末尾的元素

3. 顺序函数的高级函数

list函数

1. ls.unique() ; // 能够去重与前面一致的元素
2. ls.reverse() ; // 反转
3. ls.remove(x) // 删除与目标值x相同的所有元素

---

---

3.3 关联容器（QS： 我习惯称之为 hash类容器 ）

1，Map/Multimap 的容器 （现在来说的话我们一般不会使用到multimap 和unordered_map,先留下位置以后再说）

1, 创建容器

#include <map>
map < 键值 , 值 >  

2.基础函数

1. insert()：插入操作的平均时间复杂度是O(log n)。

2. operator[]：下标操作符的时间复杂度是O(log n)。如果键不存在，它会插入一个新元素，此时时间复杂度与insert()相同话说 他其实就是insert,但是一般情况下我们选用这种方式更加简单 。 //当没有的时候

3. clear()：清除所有元素的时间复杂度是O(n)，其中n是map中元素的数量。

4. count()：检查键是否存在的时间复杂度是O(log n)。

5. empty()：判断map是否为空的时间复杂度是O(1)。

6. erase()：删除一个元素的时间复杂度是O(log n)。

7. find()：查找一个键的时间复杂度是O(log n)。

2.cpp

#include <iostream>
#include <map>
using namespace std ;
map <string , int > mp ; 
int main () {
    // make_pair（键值 ， 内容值 ） ;
    // mp.insert(pair<,>) ; 
	mp.insert(make_pair("apple", 2)) ; 
	cout << mp["apple"] << endl ; 
	return 0 ; 
}

2，Set集合容器的常见函数

1. 插入 （set1.insert() ) : 把当前这个名称插入进当前集合 // O(log(N))
2. 查找有没有当前的值 ： .count()

需要注意的是，这些时间复杂度是在平均情况下给出的。在某些特定情况下（例如，当map需要进行大量重新平衡时），某些操作的时间复杂度可能会更高。此外，实际的性能还会受到其他因素的影响，如内存分配和缓存效率等。

---

---

3,适配器容器 stack , queue , priority_queue

stack ：

push / pop / top

queue :

push / pop / front / back

priority_queue :

push / pop / top

4. pair <>

// make_pair() 生成函数