学好这 13 种数据结构，应对各种编程语言（C++ 版）
学了这么长时间数据结构和算法，有必要来个总结了，顺便回顾一下我们这段时间的学习成果。以 C++ 语言本身提供的数据结构为例。如果能掌握这 13 种数据结构，相信在学习其它语言的时候就不费劲了。
数组 Array
看我主页简介免费C++学习资源，视频教程、职业规划、面试详解、学习路线、开发工具
每晚8点直播讲解C++编程技术。
数组在初始化的时候就需要知道其大小，后续是不可以改变其大小的，可以通过下标来获取某个 index 中存放的元素。在 C++ 中通过源码可以知道，它其实是在 C 数组的基础上封装的：
#include <array>
void testArray() {
// 创建一个数组
std::array 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 a2;
std::cout << "end a2" << a2[0] << std::endl;
// 比较两个数组中的元素是否都相等
if (a == a2) {}
}
可变数组,向量vector
在C++中使用 Vector 存当可变数组，它的容量可以动态改变，初始化的时候不需要确定数组的大小。使用的方法和数组基本一致。
#include <vector>
// 向量
void testVector() {
/**
vector<T> 它与Array不同，它的大小是可变的
*/
std::vector v;
// 增加容器的容量，至少容纳 20 个元素
v.reserve(20);
// 初始化一个向量
std::vector v2 = {2, 4, 5, 7};
// 以数组初始化一个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
双向链表具有指向前一个节点和后一个节点的指针。C++ 中本身提供了双向链表的实现。
#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
单链表只有指向下一个节点的指针，前面关于单链表我们做了好多算法题。
#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");
// 在头结点前面插入
flist.insert_after(flist.before_begin(), "before1");
// 遍历单链表
for (auto word : flist) {
cout << word << endl;
}
}
队列 queue
队列是一种先进先出的数据结构，C++底层使用「双端队列」实现。关于队列的更多内容，可以看这篇内容 图解设计一个循环队列。
#include <queue>
void testQueue() {
queue s;
// 入队
s.push(1);
// 出队
s.pop();
// 队首
s.front();
// 队尾
s.back();
// 队大小
s.size();
}
双端队列deque
双端队列可以对队头和队尾元素进行操作。在做算法的时候我们设计过一个双端队列图解设计一个双端队列。
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();
}
优先队列 priority_queue
优先队列和普通队列一样只能在队尾插入元素，队头删除元素，但是它有一个特点，队头永远是优先级最大的元素，出队顺序与入队顺序无关。C++ 中的底层使用「堆」实现的，这样时间复杂度可以控制在 O（logn）。
void testPriorityQueue() {
// 创建优先队列
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
堆是一颗完全二叉树，某个节点的值总是不大于父节点的值（大根堆），可以使用数组来表示一个堆，C++ 默认提供的是大根堆。在堆排序中我们有详细介绍了堆。 图解排序 6/10 - 堆排序（题目写出了）。在这篇文章中，我们实现了一个堆动手写个“堆”。
C++ 中的堆是通过算法实现的，需要导入 #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;});
// 创建堆后，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 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 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 来获取对应的值。
void testPair() {
pair p = {"name", "lefex"};
// 通过first 和 second 来获取第一个和第二个值
cout << p.first;
cout << p.second;
}
元组 tuple
它是 pair 的扩充版，可以存储多个不同类型的元素。
void testTuple() {
pair 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 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;
}
}
总结
我们介绍了 C++ 语言本身提供的数据结构，有线性结构和非线性结构。这些数据结构在其它语言中几乎也会提供，而且底层实现基本一致，所有只有掌握了这些数据结构原理，在学习一门其它语言变的非常轻松，调用 API 时更爽。
