一個真——蒟蒻的算法日記（二）C++STL序列式容器小分析
? ? 在閱讀本篇之前，本——在洛谷和線下被所謂的蒟蒻吊打只能來B站給聯(lián)盟成員刷刷存在感的真——蒟蒻假設(shè)讀者已經(jīng)了解了C++的（控制臺）IO流，順序，分支，循環(huán)，數(shù)組，指針，結(jié)構(gòu)。只要能做到這點(diǎn)，哪怕最簡單的只要動一動動腦的編程題都不會寫（說不定我也不會呢），也可以看本文了。反正這些東西屬于是新手村的教學(xué)關(guān)卡，實(shí)在后期有問題，回頭再打一次就行。
? ? 如果認(rèn)為自己對指針了解不夠清楚，就這么解釋吧：想象內(nèi)存是一片海，你的程序要能始終站在陸地上，或者抓著鏈接陸地的繩子；總之不能直接在水里。陸地可以是連續(xù)的，比如數(shù)組；也可以是單個礁石，也就是單個的數(shù)據(jù)；也可以是多個礁石拼起來的小島，比如結(jié)構(gòu)體變量或類（小島也可以連起來成大陸）。這些數(shù)據(jù)可以有繩子鏈接，繩子的一頭也可以泡在水里。這里的繩子就是指針。如果你抓著“指針”這個繩子的一頭，然后發(fā)現(xiàn)另一頭沒有鏈接陸地，那么你就掉海里去了，程序就寄了，操作系統(tǒng)將為你吃一頓名為“運(yùn)行時錯誤SIGSEGV”的席。據(jù)說如果訪問空指針（野指針）是很危險(xiǎn)的，這倒不至于讓電腦死機(jī)什么的，但是，如果訪問空指針導(dǎo)致程序SIGSEGV，在學(xué)校就可能會掛科或淘汰，在職場就可能會被優(yōu)化，你說危險(xiǎn)不危險(xiǎn)。
? ? 在新手村的教學(xué)關(guān)卡我們獲得了第一個初始數(shù)據(jù)結(jié)構(gòu)：數(shù)組，或者說簡單順序表。它是一個十分呆板的，內(nèi)存上連續(xù)分布的線性數(shù)據(jù)結(jié)構(gòu)（線性表）。它的（特定位置）插入和刪除都是線性時間O(n)；查找元素是否存在是線性時間；但優(yōu)勢在于根據(jù)索引（下標(biāo)）查找元素是常數(shù)時間O(1)，屬于“查改易增刪難”。與之相反，新手村第一關(guān)是鏈表數(shù)據(jù)結(jié)構(gòu)，內(nèi)存上離散由指針首尾逐個相接，增刪都是常數(shù)時間（前提是操縱用指針已經(jīng)到位），查改是線性時間。鏈表的相關(guān)操作作為新手村第一關(guān)，建議在leetcode上進(jìn)行體驗(yàn)，洛谷大區(qū)人均反面向?qū)ο?，十分甚至九分不利于互?lián)網(wǎng)大廠面試。
? ?順序表和鏈表，就是C++STL序列式容器的基本物理結(jié)構(gòu)。打完鏈表關(guān)，就可以獲得STL的如下裝備（它們均支持任何數(shù)據(jù)類型，但以下以int為例）：
#include<vector>,#include<stack>,#include<queue>,#include<map>,#include<set>
vector<int>:動態(tài)順序表，有比較方便的，常數(shù)時間的增（push_back((int))）和刪（pop_back()）。（偶爾是線性時間；常數(shù)時間時內(nèi)存不變，線性時間時內(nèi)存翻倍。） 支持下標(biāo)訪問元素和迭代器/int 索引兩種遍歷方式，也允許中間插入和刪除元素（insert（）和erase()）但改不了線性時間的查改。適用于數(shù)據(jù)量不確定因而不好預(yù)設(shè)數(shù)組的情況，也可以在需要知道序列內(nèi)部信息時模擬棧（stac）和隊(duì)列（queue）。
stack<int>:動態(tài)順序表，其目的就是模仿棧（stack）“后進(jìn)先出”的行為。只能在序列尾部增加和刪除元素（push（（int））/pop()）（時間復(fù)雜度和vector<int>相同），取到尾部元素（top()）。不支持訪問中間的數(shù)據(jù)以及遍歷,也不支持中間插入和刪除。用于將遞歸函數(shù)優(yōu)化為普通函數(shù)，或者某些特殊場景。
queue<int>：動態(tài)順序表，模擬隊(duì)列（queue）“先進(jìn)先出”的行為。只能在尾部增加元素（push((int))）和在頭部刪除元素（pop()），同時首尾元素均可訪問（front（）和back（））。不可訪問中間元素以及遍歷，也不可中間插入和刪除。廣度優(yōu)先搜索（BFS）算法必備裝備，也適用于某些特定場景。
map<int,int>：底層是紅黑樹，當(dāng)做散列表（哈希表）使用，自身從小到大有序（對STL來說，字符串的序是字典序），初始值（未訪問值）恒為0。適用于索引值不屬于int類型的情形（比如字符串string），也適用于優(yōu)化多維數(shù)組或索引值超過int甚至超過long long的數(shù)組以應(yīng)對超出內(nèi)存限制的情況。
set<int>：底層是紅黑樹，且所有元素只出現(xiàn)一次。目前只發(fā)現(xiàn)有單身狗問題和珂朵莉樹兩種使用場景。
當(dāng)然STL容器不止這么一些，但新手村嘛，這些夠了。算法之路第一章的第一關(guān)：鏈表，棧，隊(duì)列，用這些東西已經(jīng)完全足夠。
下期預(yù)告：DFS與BFS
