准备

数据结构的基础知识

数组：

是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

链表:

是一种物理存储单元上非连续、非顺序（不一定）的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

关于数组和链表的区别：

  1. 数组的优点：
  3. 1. 随机访问性强
  5. 2. 查找（读取）速度快
  7. 数组的缺点:
  9. 1. 插入和删除效率低
  11. 2. 可能浪费内存
  13. 3. 内存空间要求高，必须有足够的连续内存空间。
  15. 4. 数组大小固定，不能动态拓展
  18. 链表的优点:
  20. 1. 插入删除速度快
  22. 2. 内存利用率高，不会浪费内存
  24. 3. 大小没有固定，拓展很灵活。
  26. 链表的缺点:
  28. 不能随机查找，必须从第一个开始遍历，查找效率低

顺序容器（序列容器）

image.png

记忆方法：

array和vector底层原理是数组实现，再进行优化修改的新数组类型，而list、forward_list和deque则是链表。

1.Array（数组）

原理

  • 一种存储连续内存空间的，类型相同的线性储存结构，数据只读（数组）

固定大小的顺序容器，它们保存了一个以严格的线性顺序排列的特定数量的元素（定长数组）

特点

image.png

  1. #include <string>
  2. #include <iterator>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <array>
  7. int main()
  8. {
  9.     // 用聚合初始化构造
  10.     std::array<int, 3> a1{ {1, 2, 3} }; // CWG 1270 重申前的 C++11 中要求双花括号
  11.     // （ C++11 之后的版本和 C++14 起不要求）
  12.     std::array<int, 3> a2 = {1, 2, 3};  // = 后决不要求双花括号
  13.     std::array<std::string, 2> a3 = { std::string("a"), "b" };
  15.     // 支持容器操作
  16.     std::sort(a1.begin(), a1.end());
  17.     std::reverse_copy(a2.begin(), a2.end(), 
  18.                       std::ostream_iterator<int>(std::cout, " "));
  20.     std::cout << '\n';
  22.     // 支持带范围 for 循环
  23.     for(const auto& s: a3)
  24.         std::cout << s << ' ';
  25. }

2.Vector（动态数组/向量）

参考：https://zh.cppreference.com/w/cpp/container/vector

原理

一种存储连续内存空间的，类型相同的线性储存结构，数据可变（数组）

·特点

一个可以扩展的动态数组
随机访问、在尾部插入或删除元素快
在中间或头部插入或删除元素慢

·向量的容量

容量（capacity）：实际分配空间的大小
s.capacity0：返回当前容量
s.reserve（n）：若容量小于n，则对s进行扩展，使其容量至少为n
达到阈值内存就扩容两倍（扩容倍数和编译器版本有关）
注意扩容后数据搬离，指针指空，变为野指针

性能

image.png

  1. #include <iostream>
  2. #include <vector>
  4. int main()
  5. {
  6.     // 创建含有整数的 vector
  7.     std::vector<int> v = {7, 5, 16, 8};
  9.     // 添加二个整数到 vector
  10.     v.push_back(25);
  11.     v.push_back(13);
  13.     // 迭代并打印 vector 的值
  14.     for(int n : v) {
  15.         std::cout << n << '\n';
  16.     }
  17. }

3.List （双向链表）

原理

  • 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

image.png
image.png

性能

快速实现常量性能的增删，不支持随机访问，弥补数组的缺点
std::list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。
与 std::forward_list 相比，此容器提供双向迭代但在空间上效率稍低。
在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <list>
  5. int main()
  6. {
  7.     // 创建含整数的 list
  8.     std::list<int> l = { 7, 5, 16, 8 };
  10.     // 添加整数到 list 开头
  11.     l.push_front(25);
  12.     // 添加整数到 list 结尾
  13.     l.push_back(13);
  15.     // 以搜索插入 16 前的值
  16.     auto it = std::find(l.begin(), l.end(), 16);
  17.     if (it != l.end()) {
  18.         l.insert(it, 42);
  19.     }
  21.     // 迭代并打印 list 的值
  22.     for (int n : l) {
  23.         std::cout << n << '\n';
  24.     }
  25. }

4. forward_list （ 单向链表 ）

原理

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
image.png

特点

image.png

  1. #include <forward_list>
  2. #include <string>
  3. #include <iostream>
  5. template<typename T>
  6. std::ostream& operator<<(std::ostream& s, const std::forward_list<T>& v)
  7. {
  8.     s.put('[');
  9.     char comma[3] = {'\0', ' ', '\0'};
  10.     for (const auto& e : v) {
  11.         s << comma << e;
  12.         comma[0] = ',';
  13.     }
  14.     return s << ']';
  15. }int main() 
  16. {
  17.     // C++11 初始化器列表语法：
  18.     std::forward_list<std::string> words1 {"the", "frogurt", "is", "also", "cursed"};
  19.     std::cout << "words1: " << words1 << '\n';
  20. }

5.deque（双端队列）

原理：魔改版的队列，双端队列则头尾均可push,pop
常见的STL容器/适配器 - 图8
image.png

  1.    #include <deque>
  2.     deque<int> mydeque= { 1, 2, 3 };
  3.     mydeque.push_back(12);
  4.     while (!mydeque.empty())
  5.     {
  6.         cout<< "取出元素" <<mydeque.front() << endl;
  7.         mydeque.pop_front();
  8.     }

关联式容器

1.Set

  • 原理：红黑树
  • 集合用来存储一组无重复的元素。由于集合的元素本身是有序的，可以高效地查找指定元素，也可以方便地得到指定大小范围的元素在容器中所处的区间。

std::set 是关联容器，含有 Key 类型对象的已排序集(由小到大)。用比较函数 比较(Compare)进行排序。搜索（读取）、移除和插入拥有对数复杂度。

  1. #include <iostream>
  2. #include <set>
  3. set<int> myset = { 1,5,4,8 };
  4.     for (int s : myset) {
  5.         cout << s;
  6.     }

2.Map

  • 原理：以Key建立的红黑树

_红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平_std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。
特点
image.png

  1. #include <set>
  2. using namespace std;
  3. int main{
  4.     map<int,string> mymap= {{ 1,"one" }, { 2,"two" },{ 3,"two" } }; 
  5. for (auto& s : mymap) {
  6.     std::cout << s.first << ':' << s.second << ' ';
  7.     }
  8. }

3.Multiset& Multimap

多重集合是允许有重复元素的集合，多重映射是允许一个键对应多个附加数据的映射。
多重集合与集合、多重映射与映射的用法差不多，只在几个成员函数上有细微差异，其差异主要表现在去除了键必须唯一的限制。

  1. // 定制比较
  2. multimap<Point, double, PointCmp> mag{
  3.     { {5, 12}, 13 },
  4.     { {3, 4}, 5 },
  5.     { {8, 15}, 17 },
  6.     { {3, -3}, -1 },
  7. };
  8. for (const auto& p : mag)
  9.     cout << "The magnitude of (" << p.first.x
  10.     << ", " << p.first.y << ") is "
  11.     << p.second << '\n';
  12. }

4.Unordered_Map/Unordered_Set

原理：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
参考：https://zh.cppreference.com/w/cpp/container/unordered_map
首先这里对比一下各种基础数据结构是算法时间复杂度，如图。
image.png
所有无序容器的底层实现都是Hash Map

  • 原理：序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，我们称其为桶，各键值对真正的存储位置是各个链表的节点。如图：

image.png
Pi表示存储的各个键值对

find（）方法的代码示例

  1. #include <cstddef>
  2. #include <iostream>
  3. #include <functional>
  4. #include <string>
  5. #include <string_view>
  6. #include <unordered_map>
  8. using namespace std::literals;
  9. using std::size_t;
  11. struct string_hash
  12. {
  13.     using hash_type = std::hash<std::string_view>;
  14.     using is_transparent = void;
  16.     size_t operator()(const char* str) const        { return hash_type{}(str); }
  17.     size_t operator()(std::string_view str) const   { return hash_type{}(str); }
  18.     size_t operator()(std::string const& str) const { return hash_type{}(str); }
  19. };
  21. int main()
  22. {
  23.     // 简单比较演示
  24.     std::unordered_map<int,char> example = {{1,'a'},{2,'b'}};
  26.     auto search = example.find(2);
  27.     if (search != example.end()) {
  28.         std::cout << "Found " << search->first << " " << search->second << '\n';
  29.     } else {
  30.         std::cout << "Not found\n";
  31.     }
  33.     // C++20 演示：无序容器的异质查找（通透哈希）
  34.     std::unordered_map<std::string, size_t, string_hash, std::equal_to<>> map{ {"one"s, 1} };
  35.     std::cout << std::boolalpha
  36.         << (map.find("one")   != map.end()) << '\n'
  37.         << (map.find("one"s)  != map.end()) << '\n'
  38.         << (map.find("one"sv) != map.end()) << '\n';
  39. }

适配器

1.stack（栈）

最先压入的元素最后被弹出

2.queue（队列）

最先压入的元素最先被弹出 

  1. #include <stack>
  2. #include <deque>
  3. #include <iostream>
  5. int main()
  6. {
  7.     std::stack<int> c1;
  8.     c1.push(5);
  9.     std::cout << c1.size() << '\n';
  11.     std::stack<int> c2(c1);
  12.     std::cout << c2.size() << '\n';
  14.     std::deque<int> deq {3, 1, 4, 1, 5};
  15.     std::stack<int> c3(deq);
  16.     std::cout << c3.size() << '\n';
  17. }

3. 优先级队列(priority_queue)

最“大”的元素最先被弹出 

  1. #include <functional>
  2. #include <queue>
  3. #include <vector>
  4. #include <iostream>
  6. template<typename T> void print_queue(T& q) {
  7.     while(!q.empty()) {
  8.         std::cout << q.top() << " ";
  9.         q.pop();
  10.     }
  11.     std::cout << '\n';
  12. }
  14. int main() {
  15.     std::priority_queue<int> q;
  17.     for(int n : {1,8,5,6,3,4,0,9,7,2})
  18.         q.push(n);
  20.     print_queue(q);
  22.     std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
  24.     for(int n : {1,8,5,6,3,4,0,9,7,2})
  25.         q2.push(n);
  27.     print_queue(q2);
  29.     // 用 lambda 比较元素。
  30.     auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
  31.     std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
  33.     for(int n : {1,8,5,6,3,4,0,9,7,2})
  34.         q3.push(n);
  36.     print_queue(q3);
  38. }

总结

常见的STL容器/适配器 - 图13
1、Vector是顺序容器。是一个动态数组。支持随机存取、插入、删除、查找等操作，在内存中是一块连续的空间。在原有空间不够情况下自己主动分配空间。添加为原来的两倍。vector随机存取效率高，可是在vector插入元素。须要移动的数目多。效率低下。
注意：vector动态添加大小时。并非在原空间之后持续新空间（由于无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来。然后才開始在原内容之后构造新元素，并释放原空间。
因此。对vector的不论什么操作，一旦引起空间又一次配置，指向原vector的全部迭代器就都失效了。

2、Map是关联容器，以键值对的形式进行存储，方便进行查找。关键词起到索引的作用，值则表示与索引相关联的数据。以红黑树的结构实现，插入删除等操作都在O(logn)时间内完毕。
注意：map的下标操作。其行为与vector非常不同样：使用一个不在容器中keyword作为下标，会加入一个具有此keyword的元素到map中。
一般使用find函数取代下标操作。
3、Set是关联容器，set中每一个元素仅仅包括一个keyword。set支持高效的keyword查询操作——检查一个给定的keyword是否在set中。
set也是以红黑树的结构实现。支持高效插入、删除等操作。

关于Map、Set，STL提供8个关联容器，这8个关联容器的不同之处体如今三个维度上面：

  1. 或者是一个set，或者是一个map
  2. 或者要求不反复的keyword，或者同意反复的keyword
  3. 按顺序保存，或无序保存

8个关联容器各自是：

| 按keyword有序保存元素

|

| | —- | —- | | map | 关联数组，保存keyword-对 | | set | keyword即值，即仅仅保存keyword的容器 | | multimap | keyword可反复出现的map | | multiset | keyword可反复出现的set | | 无序集合 |

| | unordered_map | 用哈希函数组织的map | | unordered_set | 用哈希函数组织的set | | unordered_multimap

| 哈希组织map，keyword可反复出现 | | unordered_multiset

| 哈希组织set，keyword可反复出现

|