學(xué)了這么長(zhǎng)時(shí)間數(shù)據(jù)結(jié)構(gòu)和算法，有必要來個(gè)總結(jié)了，順便回顧一下我們這段時(shí)間的學(xué)習(xí)成果。以 C++ 語言本身提供的數(shù)據(jù)結(jié)構(gòu)為例。如果能掌握這 13 種數(shù)據(jù)結(jié)構(gòu)，相信在學(xué)習(xí)其它語言的時(shí)候就不費(fèi)勁了。?
數(shù)組 Array?
看我主頁簡(jiǎn)介免費(fèi)C++學(xué)習(xí)資源，視頻教程、職業(yè)規(guī)劃、面試詳解、學(xué)習(xí)路線、開發(fā)工具
每晚8點(diǎn)直播講解C++編程技術(shù)。
數(shù)組在初始化的時(shí)候就需要知道其大小，后續(xù)是不可以改變其大小的，可以通過下標(biāo)來獲取某個(gè) index 中存放的元素。在 C++ 中通過源碼可以知道，它其實(shí)是在 C 數(shù)組的基礎(chǔ)上封裝的：?
#include?<array>
void?testArray()?{
// 創(chuàng)建一個(gè)數(shù)組
std::array a = {2,?4,?6,?8,?10};
// 對(duì)數(shù)組進(jìn)行遍歷
for?(const?auto?i : a) {
std::cout?<< i <<?std::endl;
}
for(int?i =?0; i < a.size(); i++) {
std::cout?<< a[i] <<?std::endl;
}
// 取第一個(gè)值，通過 [index] 獲取
std::cout?<<?"a[0] = "?<< a[0] <<?std::endl;
// 修改數(shù)組中第一個(gè)值
a[0] =?5;
/**
at 會(huì)檢查 index 是否越界，越界將 crash，而 a[index] 不會(huì);
libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: array::at
*/
a.at(0);
// 數(shù)組是否為空
a.empty();
// 求數(shù)組的長(zhǎng)度
std::cout?<<?"a.size()="?<< a.size() <<?std::endl;
// 獲取第4個(gè)值
int?value =?std::get<4>(a);
std::cout?<<?"a(4) = "?<< value <<?std::endl;
// 創(chuàng)建一個(gè)空數(shù)組，數(shù)組中的值為0或者是與類型相等的其它值
std::array a2;
std::cout?<<?"end a2"?<< a2[0] <<?std::endl;
// 比較兩個(gè)數(shù)組中的元素是否都相等
if?(a == a2) {}
}
可變數(shù)組,向量vector
在C++中使用 Vector 存當(dāng)可變數(shù)組，它的容量可以動(dòng)態(tài)改變，初始化的時(shí)候不需要確定數(shù)組的大小。使用的方法和數(shù)組基本一致。
#include?<vector>
// 向量
void?testVector()?{
/**
vector<T> 它與Array不同，它的大小是可變的
*/
std::vector v;
// 增加容器的容量，至少容納 20 個(gè)元素
v.reserve(20);
// 初始化一個(gè)向量
std::vector v2 = {2,?4,?5,?7};
// 以數(shù)組初始化一個(gè)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;
// 獲取第一個(gè)元素
std::cout?<<?"v.front() = "?<< v2.front() <<?std::endl;
// 在末尾插入值為 9
v2.push_back(9);
// 在末尾插入值為 2
v2.emplace_back(2);
// 刪除第一個(gè)元素，傳入的值是一個(gè)迭代器
v2.erase(v2.begin());
// 長(zhǎng)度
v2.size();
// 刪除所有元素
v2.clear();
// 刪除末尾元素
v2.pop_back();
// 在末尾插入元素
v2.insert(v2.end(),?3);
}
雙向鏈表 list?
雙向鏈表具有指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的指針。C++ 中本身提供了雙向鏈表的實(shí)現(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?
單鏈表只有指向下一個(gè)節(jié)點(diǎn)的指針，前面關(guān)于單鏈表我們做了好多算法題。
#include?<forward_list>
void?testForwardList()?{
forward_list flist {"name",?"lefe",?"hello"};
// 計(jì)算它的大小
auto?count = distance(begin(flist), end(flist));
cout?<<?"size:"?<< count <<?endl;
// 頭部插入
flist.push_front("before3");
// 在頭部插入
flist.insert_after(flist.begin(),?"before2");
// 在頭結(jié)點(diǎn)前面插入
flist.insert_after(flist.before_begin(),?"before1");
// 遍歷單鏈表
for?(auto?word : flist) {
cout?<< word <<?endl;
}
}
隊(duì)列 queue
隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，C++底層使用「雙端隊(duì)列」實(shí)現(xiàn)。關(guān)于隊(duì)列的更多內(nèi)容，可以看這篇內(nèi)容?圖解設(shè)計(jì)一個(gè)循環(huán)隊(duì)列。
#include?<queue>
void?testQueue()?{
queue s;
// 入隊(duì)
s.push(1);
// 出隊(duì)
s.pop();
// 隊(duì)首
s.front();
// 隊(duì)尾
s.back();
// 隊(duì)大小
s.size();
}
雙端隊(duì)列deque
雙端隊(duì)列可以對(duì)隊(duì)頭和隊(duì)尾元素進(jìn)行操作。在做算法的時(shí)候我們?cè)O(shè)計(jì)過一個(gè)雙端隊(duì)列圖解設(shè)計(jì)一個(gè)雙端隊(duì)列。?
void?testDeque()?{
// 初始化一個(gè)空雙端隊(duì)列
deque my_deque;
// 初始化一個(gè)含有兩個(gè)元素雙端隊(duì)列
deque name_queue {"lefe",?"wsy"};
cout?<<?"[0] = "?<< name_queue[0] <<?endl;
// 獲取隊(duì)頭元素
cout?<<?"front = "?<< name_queue.front() <<?endl;
// 獲取隊(duì)尾元素
cout?<<?"back = "?<< name_queue.back() <<?endl;
// 從尾部入隊(duì)
name_queue.push_back("bx");
name_queue.pop_front();
}
優(yōu)先隊(duì)列 priority_queue
優(yōu)先隊(duì)列和普通隊(duì)列一樣只能在隊(duì)尾插入元素，隊(duì)頭刪除元素，但是它有一個(gè)特點(diǎn)，隊(duì)頭永遠(yuǎn)是優(yōu)先級(jí)最大的元素，出隊(duì)順序與入隊(duì)順序無關(guān)。C++ 中的底層使用「堆」實(shí)現(xiàn)的，這樣時(shí)間復(fù)雜度可以控制在 O（logn）。
void?testPriorityQueue()?{
// 創(chuàng)建優(yōu)先隊(duì)列
priority_queue q;
// 向隊(duì)列中添加元素
q.push(4);
q.push(1);
for(int?i =?0?; i < q.size() ; i++) {
cout?<< q.top() <<?endl;
// 刪除第一個(gè)元素
q.pop();
}
// 隊(duì)列是否為空
q.empty();
}
堆heap
堆是一顆完全二叉樹，某個(gè)節(jié)點(diǎn)的值總是不大于父節(jié)點(diǎn)的值（大根堆），可以使用數(shù)組來表示一個(gè)堆，C++ 默認(rèn)提供的是大根堆。在堆排序中我們有詳細(xì)介紹了堆。?圖解排序 6/10 - 堆排序（題目寫出了）。在這篇文章中，我們實(shí)現(xiàn)了一個(gè)堆動(dòng)手寫個(gè)“堆”。?
C++ 中的堆是通過算法實(shí)現(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 是個(gè)堆
push_heap(numbers.begin(), numbers.end());
// 移除堆頂元素，需要把 numbers 中的尾部元素移除，不會(huì)自動(dòng)移除
pop_heap(numbers.begin(), numbers.end());
numbers.pop_back();
}
棧 stack?
棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，C++ 底層使用雙端隊(duì)列實(shí)現(xiàn)。在以前最小棧算法中我們?cè)敿?xì)介紹了這種數(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中保存了兩個(gè)值，這兩個(gè)值的類型可以是任意類型，也可以不同。通過 first 和 second 來獲取對(duì)應(yīng)的值。
void?testPair()?{
pair p = {"name",?"lefex"};
// 通過first 和 second 來獲取第一個(gè)和第二個(gè)值
cout?<< p.first;
cout?<< p.second;
}
元組 tuple
它是 pair 的擴(kuò)充版，可以存儲(chǔ)多個(gè)不同類型的元素。
void?testTuple()?{
pair p = {"name",?"lefe"};
// 創(chuàng)建一個(gè) tuple，類型為 <strinng, int, double, pair>
auto?my_tuple = make_tuple("name",?20,?10.3, p);
// 獲取第一個(gè)元素
cout?<<?"0 = "?<< get<0>(my_tuple) <<?endl;
// 獲取第二個(gè)元素
cout?<<?"1 = "?<< get<1>(my_tuple) <<?endl;
}
集合 set?
集合中不能存儲(chǔ)相同的元素，它底層基于平衡二叉樹實(shí)現(xiàn)，在前面的文章中我們通過二分搜索樹實(shí)現(xiàn)了 set。使用 BST 實(shí)現(xiàn) Set。在 C++ 中 set 是有序的，同時(shí)也提供了無序的 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)在其它語言中幾乎也會(huì)提供，而且底層實(shí)現(xiàn)基本一致，所有只有掌握了這些數(shù)據(jù)結(jié)構(gòu)原理，在學(xué)習(xí)一門其它語言變的非常輕松，調(diào)用 API 時(shí)更爽。
