'學好這13種數據結構，應對各種編程語言（C++版）'

學了這麼長時間數據結構和算法，有必要來個總結了，順便回顧一下我們這段時間的學習成果。以 C++ 語言本身提供的數據結構為例。如果能掌握這 13 種數據結構，相信在學習其它語言的時候就不費勁了。

數組 Array

數組在初始化的時候就需要知道其大小，後續是不可以改變其大小的，可以通過下標來獲取某個 index 中存放的元素。在 C++ 中通過源碼可以知道，它其實是在 C 數組的基礎上封裝的：

#include <array>
void testArray() {
 // 創建一個數組
 std::array<int, 5> a = {2, 4, 6, 8, 10};
 // 對數組進行遍歷
 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;
 // 修改數組中第一個值
 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);
 // 數組是否為空
 a.empty();
 // 求數組的長度
 std::cout << "a.size()=" << a.size() << std::endl;
 // 獲取第4個值
 int value = std::get<4>(a);
 std::cout << "a(4) = " << value << std::endl;
 // 創建一個空數組，數組中的值為0或者是與類型相等的其它值
 std::array<int, 5> a2;
 std::cout << "end a2" << a2[0] << std::endl;
 // 比較兩個數組中的元素是否都相等
 if (a == a2) {}
}

可變數組,向量vector

在C++中使用 Vector 存當可變數組，它的容量可以動態改變，初始化的時候不需要確定數組的大小。使用的方法和數組基本一致。

#include <vector>
// 向量
void testVector() {
 /**
 vector<T> 它與Array不同，它的大小是可變的
 */
 std::vector<std::string> v;
 // 增加容器的容量，至少容納 20 個元素
 v.reserve(20);
 // 初始化一個向量
 std::vector<int> v2 = {2, 4, 5, 7};
 // 以數組初始化一個vector
 std::array<std :: string, 5> words {"one", "two","three", "four", "five"};
 std::vector<std::string> 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

雙向鏈表具有指向前一個節點和後一個節點的指針。C++ 中本身提供了雙向鏈表的實現。

#include <list>
void testList() {
 list<string> 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<string>::iterator beg_iter = words.begin();
 list<string>::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

單鏈表只有指向下一個節點的指針，前面關於單鏈表我們做了好多算法題。

#include <forward_list>
void testForwardList() {
 forward_list<string> 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");
 // 在頭結點前面插入
 flist.insert_after(flist.before_begin(), "before1");
 // 遍歷單鏈表
 for (auto word : flist) {
 cout << word << endl;
 }
}

隊列 queue

隊列是一種先進先出的數據結構，C++底層使用「雙端隊列」實現。關於隊列的更多內容，可以看這篇內容 圖解設計一個循環隊列。

#include <queue>
void testQueue() {
 queue<int> s;
 // 入隊
 s.push(1);
 // 出隊
 s.pop();
 // 隊首
 s.front();
 // 隊尾
 s.back();
 // 隊大小
 s.size();
}

雙端隊列deque

雙端隊列可以對隊頭和隊尾元素進行操作。在做算法的時候我們設計過一個雙端隊列 圖解設計一個雙端隊列。

void testDeque() {
 // 初始化一個空雙端隊列
 deque<int> my_deque;
 // 初始化一個含有兩個元素雙端隊列
 deque<string> 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();
}

優先隊列 priority_queue

優先隊列和普通隊列一樣只能在隊尾插入元素，隊頭刪除元素，但是它有一個特點，隊頭永遠是優先級最大的元素，出隊順序與入隊順序無關。C++ 中的底層使用「堆」實現的，這樣時間複雜度可以控制在 O（logn）。

void testPriorityQueue() {
 // 創建優先隊列
 priority_queue<int> q;
 // 向隊列中添加元素
 q.push(4);
 q.push(1);
 for(int i = 0 ; i < q.size() ; i++) {
 cout << q.top() << endl;
 // 刪除第一個元素
 q.pop();
 }
 // 隊列是否為空
 q.empty();
}

堆heap

堆是一顆完全二叉樹，某個節點的值總是不大於父節點的值（大根堆），可以使用數組來表示一個堆，C++ 默認提供的是大根堆。在堆排序中我們有詳細介紹了堆。圖解排序 6/10 - 堆排序（題目寫出了）。在這篇文章中，我們實現了一個堆 動手寫個“堆”。

C++ 中的堆是通過算法實現的，需要導入 #include <algorithm>

#include <algorithm>
void testHeap() {
 vector<int> numbers {6, 20, 7, 3, 5};
 /**提供判斷方法*/
 // make_heap(numbers.begin(), numbers.end(), [](int a,int b){return a < b;});
 // 創建堆後，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 大根堆，調用 push_heap 先確保先前的 vertor 是個堆
 push_heap(numbers.begin(), numbers.end());
 // 移除堆頂元素，需要把 numbers 中的尾部元素移除，不會自動移除
 pop_heap(numbers.begin(), numbers.end());
 numbers.pop_back();
}

棧 stack

棧是一種先進後出的數據結構，C++ 底層使用雙端隊列實現。在以前最小棧算法中我們詳細介紹了這種數據結構。圖解最小棧（LeetCode155. Min Stack）。

#include <stack>
void testStack() {
 stack<int> s;
 s.push(1);
 s.pop();
 cout << "top=" << s.top() << endl;
 s.size();
}

映射 map、unordered_map

map 是一種保存 key 和 vaule 的數據結構，key 是唯一的。C++ 中提供了有序的 map 和無序的 map 「unordered_map」。

#include <unordered_map>
#include <map>
void testMap() {
 // 初始化
 map<string, string> m;
 pair<map<string, string>::iterator, bool> ret_iter = 
 m.insert(pair<string, string>("name", "lefe"));
 if (ret_iter.second == false) {
 cout << "name have existed" << endl;
 }
 // 初始化
 map<int, string> m2 = {
 {2014, "iOS"},
 {2015, "Android"},
 };
 // 單值插入
 m["name"] = "wsy";
 // 多值插入
 m.insert({{"age", "20"}, {"from", "nmg"}});
 cout << "size = " << m.size() << endl;
 // 使用迭代器刪除
 m.erase(m.begin());
 // 查找
 map<string, string>::iterator find_iter = m.find("from");
 if (find_iter != m.end()) {
 cout << "find" << endl;
 }
 // 遍歷, key 是有序的
 for (pair<string, string> v : m) {
 cout << v.first << " = " << v.second << endl;
 }
 // 刪除全部元素
 m.clear();
}

pair

pair中保存了兩個值，這兩個值的類型可以是任意類型，也可以不同。通過 first 和 second 來獲取對應的值。

void testPair() {
 pair<string, string> p = {"name", "lefex"};
 // 通過first 和 second 來獲取第一個和第二個值
 cout << p.first;
 cout << p.second;
}

元組 tuple

它是 pair 的擴充版，可以存儲多個不同類型的元素。

void testTuple() {
 pair<string, string> p = {"name", "lefe"};
 // 創建一個 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

集合中不能存儲相同的元素，它底層基於平衡二叉樹實現，在前面的文章中我們通過二分搜索樹實現了 set。使用 BST 實現 Set。在 C++ 中 set 是有序的，同時也提供了無序的 set 「UnorderSet」。

#include <set>
#include <unordered_set>
void testSet() {
 set<int> s {7, 3, 4};
 s.insert(5);
 // 3,4,5,7
 for (auto v : s) {
 cout << v << endl;
 }
 
 unordered_set<int> us {7, 3, 4};
 us.insert(5);
 // 7,3,4,5
 for (auto v : us) {
 cout << v << endl;
 }
}

總結

我們介紹了 C++ 語言本身提供的數據結構，有線性結構和非線性結構。這些數據結構在其它語言中幾乎也會提供，而且底層實現基本一致，所有隻有掌握了這些數據結構原理，在學習一門其它語言變的非常輕鬆，調用 API 時更爽。

大家加油！！！