学好这13种数据结构，应对各种编程语言（C++版）

布满荆棘的人生 2021-12-12 08:41 74阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | Lefex

来源公众号 | 超越技术

今天分享一篇朋友的文章，文章配图很精美~

![640][]

学了这么长时间数据结构和算法，有必要来个总结了，顺便回顾一下我们这段时间的学习成果。以 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++ 中本身提供了双向链表的实现。

![640?wx\_fmt=png][640_wx_fmt_png]

#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**

单链表只有指向下一个节点的指针，前面关于单链表我们做了好多算法题。

![640?wx\_fmt=png][640_wx_fmt_png 1]

#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++底层使用「双端队列」实现。关于队列的更多内容，可以看这篇内容 [图解设计一个循环队列。][Link 1]

![640?wx\_fmt=png][640_wx_fmt_png 2]

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

**双端队列deque**

双端队列可以对队头和队尾元素进行操作。在做算法的时候我们设计过一个双端队列 [图解设计一个双端队列][Link 2]。

![640?wx\_fmt=png][640_wx_fmt_png 3]

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 - 堆排序][6_10 -]（题目写出了）。在这篇文章中，我们实现了一个堆 [动手写个“堆”][Link 3]。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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）][LeetCode155. Min Stack]。

![640?wx\_fmt=png][640_wx_fmt_png 4]

#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][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 时更爽。

[640_wx_fmt_jpeg]: /images/20211211/e6dc17d192c440749d06613cf2a44c2c.png
[640]: /images/20211211/f77ed73d786d4cb8a5b4dd22ace12fd7.png
[640_wx_fmt_png]: /images/20211211/d3b1aca3dbbf4f81b1f8151820d87c09.png
[640_wx_fmt_png 1]: /images/20211211/29b0bed0324c4856a6f3e0226b844be2.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247484116&idx=1&sn=454885c3746bfa8b1e9b1a7cc36ae8c3&chksm=fabb0247cdcc8b51940991c9eb030645e98109a78f8d60e9fd479f7b32a855c054e9198a588f&scene=21#wechat_redirect
[640_wx_fmt_png 2]: /images/20211211/a4f5b579ac0d47f2a1bed5c741da0dbd.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247484117&idx=1&sn=70e30052ce22b5512124dec1ea2be5c0&chksm=fabb0246cdcc8b504da351237ca5315dfa8127029caa064698266ea7f2396d816cbbb36f52cf&scene=21#wechat_redirect
[640_wx_fmt_png 3]: /images/20211211/b00e61cbe6004e5db851a2c9117001e9.png
[6_10 -]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247483889&idx=1&sn=4c92c6d9fdb9b0fbc3cc99ee1a2fcadf&chksm=fabb0162cdcc8874bb601ed836f996dcd849f50993960d07e34539f6779b2dc295fcad0d4d63&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247484222&idx=1&sn=c1f958285a62bdf7bb2a94ee8448603c&chksm=fabb03adcdcc8abb77c0cfb003bb6434ac8a681f631eb9944e2a08fe4cfc72d9eb7e7dd59739&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20211211/ce8fc713316b419eb379c6136a925c03.png
[LeetCode155. Min Stack]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247484115&idx=1&sn=757ac8cf2e6f3f5d40755599ebe4956f&chksm=fabb0240cdcc8b56887c298bcc46ffae500fabc23d422a66cb72153635a214f5adea53b5524f&scene=21#wechat_redirect
[640_wx_fmt_png 4]: /images/20211211/e4683f10c7f243b89e1d664ffacd9c5a.png
[BST _ Set]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247484185&idx=1&sn=0d1d43b565c73e7f1db0311edbe0834b&chksm=fabb038acdcc8a9cfd41954d3ab880d4a93e9756527a5ff331cf340e49c1ee4466626531da78&scene=21#wechat_redirect