一个真——蒟蒻的算法日记（二）C++STL序列式容器小分析
在阅读本篇之前，本——在洛谷和线下被所谓的蒟蒻吊打只能来B站给联盟成员刷刷存在感的真——蒟蒻假设读者已经了解了C++的（控制台）IO流，顺序，分支，循环，数组，指针，结构。只要能做到这点，哪怕最简单的只要动一动动脑的编程题都不会写（说不定我也不会呢），也可以看本文了。反正这些东西属于是新手村的教学关卡，实在后期有问题，回头再打一次就行。
如果认为自己对指针了解不够清楚，就这么解释吧：想象内存是一片海，你的程序要能始终站在陆地上，或者抓着链接陆地的绳子；总之不能直接在水里。陆地可以是连续的，比如数组；也可以是单个礁石，也就是单个的数据；也可以是多个礁石拼起来的小岛，比如结构体变量或类（小岛也可以连起来成大陆）。这些数据可以有绳子链接，绳子的一头也可以泡在水里。这里的绳子就是指针。如果你抓着“指针”这个绳子的一头，然后发现另一头没有链接陆地，那么你就掉海里去了，程序就寄了，操作系统将为你吃一顿名为“运行时错误SIGSEGV”的席。据说如果访问空指针（野指针）是很危险的，这倒不至于让电脑死机什么的，但是，如果访问空指针导致程序SIGSEGV，在学校就可能会挂科或淘汰，在职场就可能会被优化，你说危险不危险。
在新手村的教学关卡我们获得了第一个初始数据结构：数组，或者说简单顺序表。它是一个十分呆板的，内存上连续分布的线性数据结构（线性表）。它的（特定位置）插入和删除都是线性时间O(n)；查找元素是否存在是线性时间；但优势在于根据索引（下标）查找元素是常数时间O(1)，属于“查改易增删难”。与之相反，新手村第一关是链表数据结构，内存上离散由指针首尾逐个相接，增删都是常数时间（前提是操纵用指针已经到位），查改是线性时间。链表的相关操作作为新手村第一关，建议在leetcode上进行体验，洛谷大区人均反面向对象，十分甚至九分不利于互联网大厂面试。
顺序表和链表，就是C++STL序列式容器的基本物理结构。打完链表关，就可以获得STL的如下装备（它们均支持任何数据类型，但以下以int为例）：
#include<vector>,#include<stack>,#include<queue>,#include<map>,#include<set>
vector<int>:动态顺序表，有比较方便的，常数时间的增（push_back((int))）和删（pop_back()）。（偶尔是线性时间；常数时间时内存不变，线性时间时内存翻倍。） 支持下标访问元素和迭代器/int 索引两种遍历方式，也允许中间插入和删除元素（insert（）和erase()）但改不了线性时间的查改。适用于数据量不确定因而不好预设数组的情况，也可以在需要知道序列内部信息时模拟栈（stac）和队列（queue）。
stack<int>:动态顺序表，其目的就是模仿栈（stack）“后进先出”的行为。只能在序列尾部增加和删除元素（push（（int））/pop()）（时间复杂度和vector<int>相同），取到尾部元素（top()）。不支持访问中间的数据以及遍历,也不支持中间插入和删除。用于将递归函数优化为普通函数，或者某些特殊场景。
queue<int>：动态顺序表，模拟队列（queue）“先进先出”的行为。只能在尾部增加元素（push((int))）和在头部删除元素（pop()），同时首尾元素均可访问（front（）和back（））。不可访问中间元素以及遍历，也不可中间插入和删除。广度优先搜索（BFS）算法必备装备，也适用于某些特定场景。
map<int,int>：底层是红黑树，当做散列表（哈希表）使用，自身从小到大有序（对STL来说，字符串的序是字典序），初始值（未访问值）恒为0。适用于索引值不属于int类型的情形（比如字符串string），也适用于优化多维数组或索引值超过int甚至超过long long的数组以应对超出内存限制的情况。
set<int>：底层是红黑树，且所有元素只出现一次。目前只发现有单身狗问题和珂朵莉树两种使用场景。
当然STL容器不止这么一些，但新手村嘛，这些够了。算法之路第一章的第一关：链表，栈，队列，用这些东西已经完全足够。
下期预告：DFS与BFS
