- 数据结构 by STL
你用的最多的STL中的数据结构是什么？（最多选择四项）
- 栈丨stack
- 队列丨queue （包括衍生的priority_queue）
- 双向队列丨deque
- vector
- 集合丨set
- 地图丨map
- 链表丨list
- array
- 其他，请补充（应该没其他的了吧
0 投票人
-
一维数组：应该没人不知道吧
-
栈 (stack) ：
栈 (stack) 是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈底（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表（简称LIFO：Last in, First out 结构）。
//// 表达式计算，神坛上の栈 ////
//8829 计算表达式
//1031 表达式的计算
//有兴趣的可以去洛谷加以钻研
/*
#include<stack>
stack<int> s;
stack<string> s;
stack<node> s;
s.empty(); //如果栈为空则返回true, 否则返回false;
s.size(); //返回栈中元素的个数
s.top(); //返回栈顶元素, 但不删除该元素
s.pop(); //弹出栈顶元素, 但不返回其值
s.push(); //将元素压入栈顶
*/
可惜的是，后进先出，多少有些没素质（bushi
-
队列（queue）：
队列是一个先进先出的数据结构
联想一下链表，在单链表中，只能对表尾进行插入，对表头进行结点的删除，这样强限制性的链表，就是所说的队列。也就是说，队列是限定在表的一端进行插入，表的另一端进行删除的数据结构。 -
去买票排队，每一列队伍都有一个队尾和队首，先来的先买票，后来的后买，买好的就从队首出去，新来买票的就需要从队尾继续排队。是不是比栈有素质多了（bushi
//// 队列 queue丨模拟の神 ////
/*
#include<queue>
queue<int> q;
queue<string> q;
queue<node> q;
q.empty() //如果队列为空返回true，否则返回false
q.size() //返回队列中元素的个数
q.pop() //删除队列首元素但不返回其值
q.front() //返回队首元素的值，但不删除该元素
q.push() //在队尾压入新元素
q.back() //返回队列尾元素的值，但不删除该元素
*/
可他不能以下标遍历（此处鞭尸 栈_stack
-
神秘のdeque
deque（双端队列）是double-ended queue 的一个不规则缩写。deque是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩。 -
特定的库可以以不同的方式实现deques，通常作为某种形式的动态数组。但是在任何情况下，它们都允许通过随机访问迭代器直接访问各个元素，通过根据需要扩展和收缩容器来自动处理存储。
-
deque上常见操作的复杂性（效率）如下：
- 随机访问 - 常数 O(1)
- 在结尾或开头插入或移除元素 - 摊销不变 O(1)
- 插入或移除元素 - 线性 O(n)
//// 从单向变双向丨deque ////
#include <deque>
deque<int> a; //定义一个int类型的双端队列a
deque<int> a(10); //定义一个int类型的双端队列a，并设置初始大小为10
deque<int> a(10, 1); //定义一个int类型的双端队列a，并设置初始大小为10且初始值都为1
deque<int> b(a); //定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); //将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值
//-------------------------------------------------------------------
deq.size() //容器大小
deq.max_size() //容器最大容量
deq.resize() //更改容器大小
deq.empty() //容器判空
deq.shrink_to_fit() //减少容器大小到满足元素所占存储空间的大小
deq.front() //访问第一个元素
deq.back() //访问最后一个元素
deq.push_back() //尾部增加元素
deq.push_front() //前端增加元素
deq.pop_back() //删除尾部元素
deq.pop_front() //删除前端元素
deq.emplace_front() //头部插入
deq.emplace_back() //尾部插入
deq.insert() //任意位置插入一个元素
deq.erase() //任意位置删除元素
dep.at() //检测越界并访问
双端操作的奇妙无法想象！
-
vector：
-
vector是一个连续的线性空间，就像数组一样，区别于数组之处在于vector是可以对数组的大小进行动态修改的。但是在访问和操作上也可以像数组一样提供一种指针的访问方式，那么这就是vector迭代器，但是迭代器千万不可以被理解为它就是指针。
-
vector这个容器理解起来就像一个大小可变的数组，与数组不同的地方就是数组是一块静态的空间，而vector是一块动态的空间，随着元素的加入，vector的内部机制会自行扩充空间大小以收纳更多的元素。
//// 万金油 vector ////
/*
#include<vector>
vector<int> v1;
vector<node> v2;
vector<string> v3;
vector<vector<int> >; //注意空格 //这里相当于二维数组int a[n][n];
vector<int> v5 = { 1,2,3,4,5 };
vector<string> v6 = { "my","name","is","Badcen" };
//初始化
vector<int> v7(5, -1); //初始化为-1,-1,-1,-1,-1。
vector<string> v8(3, "hi");
//第一个参数是数目，第二个参数是要初始化的值
vector<int> v9(10); //默认初始化为0
vector<int> v10(4); //默认初始化为空字符串
*/
确实是个万能数据结构（确信
- 集合 set：
- set就是集合的意思，集合的特点就是不会出现重复的内容。一般用来作查重或去重操作。
////set：欢乐的世界////
#include<set>
set<int> se;
set<string> se;
set<node> se;
se.insert() //插入元素
se.count() //判断容器中是否存在某个元素
se.size() //返回容器的尺寸，也可以元素的个数
se.erase() //删除集合中某个元素
se.clear() //清空集合
se.empty() //判断是否为空
se.begin() //返回第一个节点的迭代器
se.end() //返回最后一个节点加1的迭代器
se.rbegin() //反向迭代器
se.rend() //反向迭代器
se.find() //查找某个指定元素的迭代器
se.lower_bound() //二分查找第一个不小于某个值的元素的迭代器
se.get_allocator() //返回集合的分配器
se.swap() //交换两个集合的变量
se.max_size() //返回集合能容纳元素的最大限值
他不能直接访问元素，但有很多不知名数据结构也不行，不寒颤（ stack & queue ：6
- 地图 map：
现实中的数据很多是关联的，例如书本名称和价格，每条数据都含有两部分：
- 信息学竞赛一本通 ：¥80
- 高等数学 ：¥27.5
- 生物信息分析 ：¥35.5
-
我们可以使用map存储这类一对一的数据：
第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
第二个可以称为该关键字的值(value)； -
另外需要注意的是，使用 map 容器存储的各个键-值对，键的值既不能重复也不能被修改。换句话说，map 容器中存储的各个键值对不仅键的值独一无二，键的类型也会用 const 修饰，这意味着只要键值对被存储到 map 容器中，其键的值将不能再做任何修改。
//// map：新华字典检索表 ////
#include<map>
map<int,int> m;
m.insert({a,b}); //添加元素 //等价于 m.insert(pair<int,int> (a,b));
//map中key的值是唯一的，如果插入一个已经存在的key值会导致原先值的覆盖
m.erase(i); //删除 m[i] //括号内为key值，也就是左值
m[i] = n; //修改元素
ans = m[i] //直接通过key值查找元素
ans = find(12)->first; //通过value值找key值
ans = find(1)->second; //通过key值找value值
m.clear(); //清除所有元素
m.empty(); //如果为空返回1，负责返回0
m.size(); //返回容器的元素个数
m.max_size(); //返回容器可以容纳的最大元素
m.begin()->first; //结果为容器的第一个元素的key值
m.begin()->second; //结果为容器的第一个元素的value值
MLE说不定可以这么解决？
- 链表 list：
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：主要不同在于forward_list是单链表，只能单方向迭代。
- 与其他的序列式容器相比(array，vector，deque)，list在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置。
- list还需要一些额外的空间，以保存每个节点的相关联信息。
//// 难以捉摸的下一元素：list ////
不想打出来qwq（不会真有人用链表吧
-
array：
array是序列式容器，类似于C语言的数组，是固定大小的，一旦定义完成后就无法进行扩容或收缩。
////array：无名的数据结构////
begin 返回容器中第一个元素的迭代器
end 返回容器中最后一个元素之后的迭代器
rbegin 返回指向最后一个元素的迭代器
rend 返回指向第一个元素之前的迭代器
size 返回 容器中当前元素的数量
max_size 返回容器可容纳的最大数量
empty 判断容器是否为空
at 返回容器在n处的引用，有错误检测
front 返回容器的第一个元素的引用
back 返回容器的最后一个元素的引用
data 返回指向首个元素的指针
fill 填充元素
swap 交换容器内的元素
array可以用来创造多维数组，但我不放（懒qwq
-
其实这里的大多数数据结构我们上课都手打过（可恶被骗了），各种数据结构我们除了需要会使用，还需要理解其原理。
-
最后，感谢STL的贡献！（翻译：我很懒不想手打
