學了這么長時間數(shù)據(jù)結(jié)構(gòu)和算法池充，有必要來個總結(jié)了桩引，順便回顧一下我們這段時間的學習成果。以 C++ 語言本身提供的數(shù)據(jù)結(jié)構(gòu)為例收夸。如果能掌握這 13 種數(shù)據(jù)結(jié)構(gòu)坑匠，相信在學習其它語言的時候就不費勁了。?
數(shù)組 Array?
看我主頁簡介免費C++學習資源咱圆，視頻教程笛辟、職業(yè)規(guī)劃、面試詳解序苏、學習路線手幢、開發(fā)工具
每晚8點直播講解C++編程技術(shù)。
數(shù)組在初始化的時候就需要知道其大小忱详，后續(xù)是不可以改變其大小的围来，可以通過下標來獲取某個 index 中存放的元素。在 C++ 中通過源碼可以知道匈睁，它其實是在 C 數(shù)組的基礎(chǔ)上封裝的：?
#include?<array>
void?testArray()?{
// 創(chuàng)建一個數(shù)組
std::array a = {2,?4,?6,?8,?10};
// 對數(shù)組進行遍歷
for?(const?auto?i : a) {
std::cout?<< i <<?std::endl;
}
for(int?i =?0; i < a.size(); i++) {
std::cout?<< a[i] <<?std::endl;
}
// 取第一個值监透，通過 [index] 獲取
std::cout?<<?"a[0] = "?<< a[0] <<?std::endl;
// 修改數(shù)組中第一個值
a[0] =?5;
/**
at 會檢查 index 是否越界，越界將 crash航唆，而 a[index] 不會;
libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: array::at
*/
a.at(0);
// 數(shù)組是否為空
a.empty();
// 求數(shù)組的長度
std::cout?<<?"a.size()="?<< a.size() <<?std::endl;
// 獲取第4個值
int?value =?std::get<4>(a);
std::cout?<<?"a(4) = "?<< value <<?std::endl;
// 創(chuàng)建一個空數(shù)組胀蛮，數(shù)組中的值為0或者是與類型相等的其它值
std::array a2;
std::cout?<<?"end a2"?<< a2[0] <<?std::endl;
// 比較兩個數(shù)組中的元素是否都相等
if?(a == a2) {}
}
可變數(shù)組,向量vector
在C++中使用 Vector 存當可變數(shù)組，它的容量可以動態(tài)改變糯钙，初始化的時候不需要確定數(shù)組的大小粪狼。使用的方法和數(shù)組基本一致。
#include?<vector>
// 向量
void?testVector()?{
/**
vector<T> 它與Array不同任岸，它的大小是可變的
*/
std::vector v;
// 增加容器的容量再榄，至少容納 20 個元素
v.reserve(20);
// 初始化一個向量
std::vector v2 = {2,?4,?5,?7};
// 以數(shù)組初始化一個vector
std::array words {"one",?"two","three",?"four",?"five"};
std::vector words_copy {std::begin(words) ,?std::end(words)};
// 通過 v[index] 獲取或者修改元素
std::cout?<<?"v[0] = "?<< v2[1] <<?std::endl;
// 獲取第一個元素
std::cout?<<?"v.front() = "?<< v2.front() <<?std::endl;
// 在末尾插入值為 9
v2.push_back(9);
// 在末尾插入值為 2
v2.emplace_back(2);
// 刪除第一個元素，傳入的值是一個迭代器
v2.erase(v2.begin());
// 長度
v2.size();
// 刪除所有元素
v2.clear();
// 刪除末尾元素
v2.pop_back();
// 在末尾插入元素
v2.insert(v2.end(),?3);
}
雙向鏈表 list?
雙向鏈表具有指向前一個節(jié)點和后一個節(jié)點的指針享潜。C++ 中本身提供了雙向鏈表的實現(xiàn)困鸥。
#include?<list>
void?testList()?{
list words {"hello",?"list"};
// 頭部插入元素
words.push_front("push_fron");
words.emplace_front("emplace_front");
// 尾部插入
words.push_back("push_back");
words.emplace_back("emplace_back");
// 指定位置插入
words.insert(words.begin()++,?"insert");
// 刪除元素
words.remove("push_fron");
// 通過迭代器來訪問鏈表中的元素
list::iterator beg_iter = words.begin();
list::iterator end_iter = words.end();
cout?<<?"beg_iter:"?<< *beg_iter <<?endl;
cout?<<?"end_iter:"?<< *end_iter <<?endl;
for?(auto?a : words) {
cout?<< a <<?endl;
}
}
單鏈表 forward_list?
單鏈表只有指向下一個節(jié)點的指針，前面關(guān)于單鏈表我們做了好多算法題剑按。
#include?<forward_list>
void?testForwardList()?{
forward_list flist {"name",?"lefe",?"hello"};
// 計算它的大小
auto?count = distance(begin(flist), end(flist));
cout?<<?"size:"?<< count <<?endl;
// 頭部插入
flist.push_front("before3");
// 在頭部插入
flist.insert_after(flist.begin(),?"before2");
// 在頭結(jié)點前面插入
flist.insert_after(flist.before_begin(),?"before1");
// 遍歷單鏈表
for?(auto?word : flist) {
cout?<< word <<?endl;
}
}
隊列 queue
隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)疾就，C++底層使用「雙端隊列」實現(xiàn)。關(guān)于隊列的更多內(nèi)容吕座，可以看這篇內(nèi)容?圖解設(shè)計一個循環(huán)隊列虐译。
#include?<queue>
void?testQueue()?{
queue s;
// 入隊
s.push(1);
// 出隊
s.pop();
// 隊首
s.front();
// 隊尾
s.back();
// 隊大小
s.size();
}
雙端隊列deque
雙端隊列可以對隊頭和隊尾元素進行操作。在做算法的時候我們設(shè)計過一個雙端隊列圖解設(shè)計一個雙端隊列吴趴。?
void?testDeque()?{
// 初始化一個空雙端隊列
deque my_deque;
// 初始化一個含有兩個元素雙端隊列
deque name_queue {"lefe",?"wsy"};
cout?<<?"[0] = "?<< name_queue[0] <<?endl;
// 獲取隊頭元素
cout?<<?"front = "?<< name_queue.front() <<?endl;
// 獲取隊尾元素
cout?<<?"back = "?<< name_queue.back() <<?endl;
// 從尾部入隊
name_queue.push_back("bx");
name_queue.pop_front();
}
優(yōu)先隊列 priority_queue
優(yōu)先隊列和普通隊列一樣只能在隊尾插入元素漆诽，隊頭刪除元素，但是它有一個特點锣枝，隊頭永遠是優(yōu)先級最大的元素厢拭，出隊順序與入隊順序無關(guān)。C++ 中的底層使用「堆」實現(xiàn)的撇叁，這樣時間復(fù)雜度可以控制在 O（logn）供鸠。
void?testPriorityQueue()?{
// 創(chuàng)建優(yōu)先隊列
priority_queue q;
// 向隊列中添加元素
q.push(4);
q.push(1);
for(int?i =?0?; i < q.size() ; i++) {
cout?<< q.top() <<?endl;
// 刪除第一個元素
q.pop();
}
// 隊列是否為空
q.empty();
}
堆heap
堆是一顆完全二叉樹，某個節(jié)點的值總是不大于父節(jié)點的值（大根堆）陨闹，可以使用數(shù)組來表示一個堆楞捂，C++ 默認提供的是大根堆薄坏。在堆排序中我們有詳細介紹了堆。?圖解排序 6/10 - 堆排序（題目寫出了）寨闹。在這篇文章中胶坠，我們實現(xiàn)了一個堆動手寫個“堆”。?
C++ 中的堆是通過算法實現(xiàn)的繁堡，需要導(dǎo)入?#include <algorithm>
#include?<algorithm>
void?testHeap()?{
vector numbers {6,?20,?7,?3,?5};
/**提供判斷方法*/
// make_heap(numbers.begin(), numbers.end(), [](int a,int b){return a < b;});
// 創(chuàng)建堆后沈善，numbers 中元素的值為: 20，6椭蹄，7闻牡，3，5绳矩，大根堆
make_heap(numbers.begin(), numbers.end(), [](int?a,int?b){return?a < b;});
// 向堆中添加元素
numbers.push_back(40);
// 重組堆：40罩润，6，20埋酬，3哨啃，5，7 大根堆写妥，調(diào)用 push_heap 先確保先前的 vertor 是個堆
push_heap(numbers.begin(), numbers.end());
// 移除堆頂元素拳球，需要把 numbers 中的尾部元素移除，不會自動移除
pop_heap(numbers.begin(), numbers.end());
numbers.pop_back();
}
棧 stack?
棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)珍特，C++ 底層使用雙端隊列實現(xiàn)祝峻。在以前最小棧算法中我們詳細介紹了這種數(shù)據(jù)結(jié)構(gòu)。?圖解最小棧（LeetCode155. Min Stack）?扎筒。
#include?<stack>
void?testStack()?{
stack s;
s.push(1);
s.pop();
cout?<<?"top="?<< s.top() <<?endl;
s.size();
}
映射 map莱找、unordered_map
map 是一種保存 key 和 vaule 的數(shù)據(jù)結(jié)構(gòu)，key 是唯一的嗜桌。C++ 中提供了有序的 map 和無序的 map 「unordered_map」奥溺。
#include?<unordered_map>
#include?<map>
void?testMap()?{
// 初始化
map m;
pair::iterator,?bool> ret_iter =
m.insert(pair("name",?"lefe"));
if?(ret_iter.second ==?false) {
cout?<<?"name have existed"?<<?endl;
}
// 初始化
map m2 = {
{2014,?"iOS"},
{2015,?"Android"},
};
// 單值插入
m["name"] =?"wsy";
// 多值插入
m.insert({{"age",?"20"}, {"from",?"nmg"}});
cout?<<?"size = "?<< m.size() <<?endl;
// 使用迭代器刪除
m.erase(m.begin());
// 查找
map::iterator find_iter = m.find("from");
if?(find_iter != m.end()) {
cout?<<?"find"?<<?endl;
}
// 遍歷, key 是有序的
for?(pair v : m) {
cout?<< v.first <<?" = "?<< v.second <<?endl;
}
// 刪除全部元素
m.clear();
}
pair
pair中保存了兩個值，這兩個值的類型可以是任意類型骨宠，也可以不同浮定。通過 first 和 second 來獲取對應(yīng)的值。
void?testPair()?{
pair p = {"name",?"lefex"};
// 通過first 和 second 來獲取第一個和第二個值
cout?<< p.first;
cout?<< p.second;
}
元組 tuple
它是 pair 的擴充版层亿，可以存儲多個不同類型的元素桦卒。
void?testTuple()?{
pair p = {"name",?"lefe"};
// 創(chuàng)建一個 tuple，類型為 <strinng, int, double, pair>
auto?my_tuple = make_tuple("name",?20,?10.3, p);
// 獲取第一個元素
cout?<<?"0 = "?<< get<0>(my_tuple) <<?endl;
// 獲取第二個元素
cout?<<?"1 = "?<< get<1>(my_tuple) <<?endl;
}
集合 set?
集合中不能存儲相同的元素匿又，它底層基于平衡二叉樹實現(xiàn)方灾，在前面的文章中我們通過二分搜索樹實現(xiàn)了 set。使用 BST 實現(xiàn) Set碌更。在 C++ 中 set 是有序的裕偿，同時也提供了無序的 set 「UnorderSet」洞慎。?
#include?<set>
#include?<unordered_set>
void?testSet()?{
set s {7,?3,?4};
s.insert(5);
// 3,4,5,7
for?(auto?v : s) {
cout?<< v <<?endl;
}
unordered_set us {7,?3,?4};
us.insert(5);
// 7,3,4,5
for?(auto?v : us) {
cout?<< v <<?endl;
}
}
總結(jié)
我們介紹了 C++ 語言本身提供的數(shù)據(jù)結(jié)構(gòu)，有線性結(jié)構(gòu)和非線性結(jié)構(gòu)嘿棘。這些數(shù)據(jù)結(jié)構(gòu)在其它語言中幾乎也會提供拢蛋，而且底層實現(xiàn)基本一致，所有只有掌握了這些數(shù)據(jù)結(jié)構(gòu)原理蔫巩，在學習一門其它語言變的非常輕松，調(diào)用 API 時更爽快压。
