企业官网建设流程全解析

本文对 STL 中的 C++标准库容器进行概述，对其有一个简单的理解，方便后续学习。

1 概述

标准库提供了各种类型安全的容器，用于存储一组相关的对象。这些容器都是类模板。当你声明一个容器变量时，必须指定容器要存放的元素类型。容器可以用初始化列表直接创建。它们自带成员函数，用来添加、删除元素以及执行其他操作。

• 可以通过迭代器遍历容器里的元素，并访问单个元素；
• 可以显式使用迭代器（调用它的成员函数、运算符、全局函数）；
• 可以隐式使用迭代器，比如用范围 for 循环；
• 所有 C++标准库容器的迭代器都有统一接口，但每个容器又有自己专属的迭代器；

2 分类

容器分为三大类：序列容器、关联容器、容器适配器

2.1 序列容器（Sequence Containers）

序列容器会保持你插入元素的顺序，不会乱序。

• vector (动态数组)
  • vector 用起来像数组，但能自动扩容；
  • 它支持随机访问、内存连续存放，长度非常灵活；
  • 是大多数场景的首选序列容器；
  • 如果不知道用哪个容器，先用 vector；
• array (固定大小数组)
  • 有 vector 的一些优点，安全版的 C语言数组；
  • 但是长度固定、不能变；
• deque (双端队列)
  • 允许在头部和尾部快速插入、删除；
  • 可以随机访问、灵活长度优点；
  • 但内存不连续，不是一整块；
• list (双向链表)
  • list 是双向链表，支持双向访问；
  • 在任意位置插入、删除都很快；
  • 但不支持随机访问，查找慢，不能直接用下标访问元素；
• forward_list (单向链表)
  • 单向链表，只能往前访问；
  • 省内存；
  • 功能比 list 少；

2.2 关联容器（Associative Containers）

在关联容器中，元素会按照预设规则排序（比如自动升序排列），不像序列容器保持插入顺序。同时也提供无序版本的关联容器。关联容器分为两大类：map (映射) 和 set (集合)。

• map (映射/字典)
  • map 有时被称为字典，由键值对（key–value）组成；
  • key 用来排序，value 是对应的数据；
  • map 自动按 key 排序，unordered_map 不排序；
  • 查 key 极快，无序版更快；
• set (集合)
  • set 是一个自动升序、元素唯一的容器，值本身就是键；
  • 只存值、不重复；
  • 自动排序；
  • 用来去重、快速查找有没有某个元素；
  • 无序版：unordered_set；
• 允许重复的版本
  • map 和 set 都不允许重复 key / 元素；
  • 可重复版本：multimap (可重复 key 的 map)、multiset (可重复元素的 set)；
  • 可重复版本无序版本：unordered_multimap、unordered_multiset；
• 迭代器
  • 有序版本（map/set）支持双向迭代器；
  • 无序版本支持前向迭代器；

异构查找（C++14 新特性）
有序关联容器（map / multimap / set / multiset）现在支持异构查找。在 find()、lower_bound() 这类查找函数里，不再强制必须传入和 key 完全一样的类型。你可以传入任何能和 key 进行比较的类型（只要定义了 < 比较符）。
异构查找是手动开启的（不是默认打开的）。声明容器时，指定比较器为std::less<>或std::greater<>(空心模板参数)，就能开启。
如果你使用默认比较器，那么容器的行为就会和 C++11 及更早版本完全一样。

//旧写法（C++11，有性能浪费）std::map<std::string,int>myMap;autoit=myMap.find("apple");//查找时，“apple” 会先创建临时 string 对象，浪费性能

//新写法（C++14，异构查找，高效）std::map<std::string,int,std::less<>>myMap;autoit=myMap.find("apple");//直接传 const char*，不创建临时 string ，超快

总结下来就是，C++14 异构查找就是在定义关联容器的时候加个 less<>，查找不用强转类型，直接查，性能更高。

在 map、multimap、set、multiset 中，以下成员函数已经被重载，以支持异构查找：

• find：找某个 key，找到了返回迭代器，没找到返回 end
• count：统计某个 key 出现多少次
• lower_bound：找大于等于目标值的第一个位置
• upper_bound：找大于目标值的第一个位置
• equal_range：一次性返回 lower_bound 和 upper_bound，用来找同 key 的一段范围

2.3 容器适配器（Container Adapters）

容器适配器是序列容器或关联容器的封装变体，为了简单、清晰，限制了接口（只暴露特定功能）。容器适配器不支持迭代器，不能和 STL 算法一起使用。

• queue (队列)
  • 遵循 FIFO（先进先出）规则；
  • 最早放进去的元素，最先被拿出来；
• priority_queue (优先队列)
  • 自动排序，值最大/优先级最高的元素永远在最前面；
  • 谁优先级高谁先出；
• stack (栈)
  • 遵循 LIFO（后进先出）规则；
  • 最后放进去的元素，最先被拿出来；

3 容器元素的要求

一般来说，只要元素是可拷贝的，几乎任何对象类型都能放进 C++ 容器。对于只能移动、不能拷贝的元素（比如 vector<unique_ptr<T>>），只要不调用会尝试拷贝它的容器函数，就可以正常使用。

• 元素的析构函数不允许抛出异常，否则容器内存管理会崩溃；
• 有序关联容器（map/set等）必须定义公开的比较运算符。默认用 operator<，就算你的类型不支持 <，也可以自定义比较规则；
• 容器的某些操作会要求元素有公开的默认构造函数和相等比较运算符，比如无序关联容器（unordered_map/set）需要支持 == 相等判断和哈希（hash）；

4 访问容器元素

容器的元素通过迭代器访问，也可以使用基于范围的 for 循环来遍历 C++标准库容器。

5 容器比较

所有容器都重载了 ==，但只能比较【同类型、同元素】的两个容器。

• 可以比较 vector<string>和vector<string>
• 不能比较 vector<string>和list<string>
• 不能比较 vector<string>和vector<char*>

在 C++98/03里，可以用 std::equal / std::mismatch 比较不同容器/不同元素。C++11 多了 std::is_permutation。但这些旧版函数都假设两个容器长度一样，如果第二个更短会出现未定义行为（崩溃），如果第二个更长会出现结果错误。

支持安全比较不同容器（C++14 开始）
可以用接收两个完整范围的新版 std::equal、std::mismatch、std::is_permutation：

• 支持长度不同的容器；
• 长度不同时，直接快速返回 false；
• 更安全、更少出错、速度更快；

注：除了std::list(不享受优化)