C++(标准库):12---STL容器总体概述

一、容器概述

• 容器用来管理一大群元素。为了适应不同需要，STL提供了不同的容器，如下图所示

二、容器的分类

• 总的来说，容器可以分为三大类：
  • ①序列式容器（Sequence container）：这是一种有序（ordered）集合，其内每个元素均有确凿的位置——取决于插入时机和位置，与元素值无关。STL提供了5个定义好的序列式容器：
    • array、vector、deque、list、forward_list
  • ②关联式容器（Associative container）：这是一种已排序（sorted）集合，元素位置取决于其value（或key）和给定的某个排序准则。STL提供了4个关联式容器
    • set、multiset、map、multimap
  • ③无序容器（Unordered (associative) container）：这是一种无序集合（unordered collection），其内每个元素的位置无关紧要，唯一重要的是某特定元素是否位于此集合内。STL内含4个预定义的无序容器：
    • unordered_set、unordered_multiset、unordered_map、unordered_multimap

三、序列式容器

• STL内部预先定义好的序列式容器有：
  • array：在固定大小的array内管理元素
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483103
  • vector：可变大小数组
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483009
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/103565158
  • deque：双端队列
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483037
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/103614247
  • list：双向链表
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483054
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/103571246
  • forward_list：单向链表
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483078
• array是TR1引入的，进入C++标准库的时间比较短，而且它有一些特殊属性，与其他STL容器不共通
• 详情点击各个链接查看即可

四、关联式容器

• STL内部预先定义好的关联式容器有：
  • set：元素依据其value自动排序，每个元素只能出现一次，不允许重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483473
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104249771
  • multiset：和set的唯一差别是，其元素可以重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483473
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104250832
  • map：每个元素都是key/value pair，其中key是排序准则的基准。每个key只能出现一次，不允许重复。Map也被视为一种关联式数组，也就是“索引可为任意类型”的数组
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483491
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104249771
  • multimap：和map的唯一差别是，其元素都可以重复。multimap可被当做字典使用
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483491
    • 源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104250832
• 关联式容器依据特定的排序准则，自动为其元素排序。元素可以是任何类型的value，也可以是key/value pair，其中key可以是任何类型，映射至一个相关value，而value也可以是任意类型
• 排序准则：
  • 对于只有value的关联式容器，例如set、multiset，其对value进行排序。对于key/value pair的关联式容器，例如map、multimap，其根据key进行排序
  • 默认情况所有容器都以操作符<进行排序，不过你可以提供自己的比较函数，定义出不同的排序准则
• 关联式的底层实现数据结构：
  • 关联式容器底层以平衡二叉树（红黑树）实现，源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/103645839
  • 因为使用平衡二叉树实现，所以对于特定的key或value，其能很快的找到特定的元素，因为其操作具备的是对数复杂度，而普通的循序式容器的复杂度是线型的。因此，使用关联式容器，面对1000个元素，平均而言你只要10次比较操作而不是500比较就可以查找特定的元素
• 关联式容器拥有自动排序能力，并不意味着它们在排序方面的执行效能更高。实际上，由于股演练时容器每安插一个新元素都要进行一次排序，速度反而不及序列式容器经常采用的收发：先安插所有元素，然后调用STL提供的排序算法进行一次完全排序

五、无序容器

• STL内部预先定义好的无序容器有：
  • unordered_set：是无序元素的集合，其中每个元素不能重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483561
  • unordered_multiset：和unordered set的唯一差别是，其元素可以重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483561
  • unordered_map：元素都是key/value pair，每个key不能重复，value可以重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483561
  • unordered_multimap：和unordered_map的唯一差别是，其key可以重复
    • 基础语法参阅：https://blog.csdn.net/qq_41453285/article/details/105483561
• 在无序容器中，元素没有明确的排序次序。也就是如果容器中有三个元素，当你迭代器容器内的所有元素时，它们的次序可能不同，当你再插入一个新元素时，先前3个元素的相对次序可能会被改变
• 这些无序容器都有一个可选的template实参，用来指明hash函数和等效准则，该准则被用来寻找某给定值，以便判断是否发生重复。默认的等效准则是操作符==
• 无序容器的主要优点是：当你打算查找一个带某特定值的元素，其速度甚至可能快过关联式容器。事实上无序容器提供的是摊提的常量复杂度，前提是你又一个良好的hash函数。然而提供一个良好的hash函数并非容易的事，可能需要提供更多内存作为bucket
• 底层实现：
  • 无序容器通常以hash table实现出来，内部结构是一个“由linked list组成”的array，源码剖析参阅：https://blog.csdn.net/qq_41453285/article/details/104260053
  • 通过某个hash函数的运算，确定元素落于这个array的位置。Hash函数运算的目标是：让每个元素的落点（位置）有助于用户快速访问任何一个元素

六、容器的选择

• 一些规则如下：
  • ①默认情况下应该使用vector。vector的内部结构最简单，并允许随机访问，所以数据的访问十分方便灵活，数据的处理也够快
  • ②如果经常要在序列头部和尾部插入和移除元素，应该采用deque。如果你希望元素被移除时，容器能够自动缩减内部内存用量，那么也该采用deque。此外，由于vector通常采用一个内存区块来存放元素，而deque采用多个区块，所以后者可内含更多元素
  • ③如果需要经常在容器中段执行元素的安插、移动、删除，可考虑使用list。list提供特殊的成员函数，可以在常量时间内将元素从A容器移动到B容器。但由于list不支持随机访问，所以如果只知道list的头部却要访问list中的元素，效能会降低
  • ④如果你要的容器对异常的处理使得“每次操作若不成功便无任何作用”，那么应该选list（但是不调用其assignment操作符和sort()；而且如果元素比较过程中会抛出异常，就不要调用merge()、remove()、remove_if()、unique()），或选用associative/unordered容器（但是不调用多元素安插动作，而且如果比较准则的复制/赋值动作可能抛出异常，就不要调用swap()或erase()）
  • ⑤如果你经常需要根据某个准则查找元素，应当使用“依据该准则进行hash”的unordered set或multiset。然而，hash容器内是无序的，所以如果你必须依赖元素的次序，应该使用set或multiset，它们根据查找准则对元素排序
  • ⑥如果想处理key/value pair，请采用unordered (multi)map。如果元素次序很重要，可采用(multi)map
  • ⑦如果需要关联式数组，应采用unordered map。如果元素次序很重要，可采用map
  • ⑧如果需要字典结构，应采用unordered multimap。如果元素次序很重要，可采用multimap

七、容器的共通能力

• 所有STL容器都满足下面的能力，三个最核心的能力是：
  • ①所有容器提供的都是“value语义”而非“reference语义”。容器进行元素的插入时，内部实施的是copy或/move动作，而不是管理元素的reference
  • ②元素在容器内有其特定顺序。每一种容器都会提供若干“返回迭代器”的操作函数，这些迭代器可用来遍历各个元素。这是STL算法的关键接口
  • ③一般而言，各项操作并非绝对安全，也就是说它们并不会检查每一个可能发生的错误。调用者必须确保传给操作函数的实参符合条件
• 通过STL自己不会排除异常。如果STL容器调用的用户自定义操作抛出异常，行为各异

八、容器的共通操作

• C++标准只定义一系列容器共通操作，适用于所有STL容器，然后由于C++11带来了容器的多样化，因此会有一些例外
• 下面两张图列出了（几乎）所有容器共通的操作（其中“必要”列表示某个操作是否为总体性容器条件的一部分）

初始化

• 每个容器类都提供了一个default构造函数、一个copy构造函数、一个析构函数

赋值和swap()

• 当你对着容器赋予元素时，来源容器的所有元素被复制到目标容器内，后者原本的元素全被移除。所以，容器的赋值动作代价相对高昂
• 自C++11起，可以使用move assignment语义取代上述行为。所有容器都提供move assignment操作符。基于效率考虑，如果赋值后右侧容器的内容不再被使用，应该使用这种赋值手法。例如：

• 自C++98开始，所有容器都提供成员函数swap()，所有容器都提供成员函数swap()，用来置换两容器的内容。实际上，它只是置换若干内部pointer，所以其保证常量复杂度
• 注意，array容器的swap()行为略有不同。由于它无法只是在内置换pointer，所以其swap()拥有线型复杂度，而且原本存在的迭代器和reference在swap发生之后，指向的是同一容器的不同元素

与大小相关的函数

• 所有容器都提供三个与大小相关的操作函数
  • empty()
  • size()
  • max_size()

比较

• 除了无序容器之外，常用的比较操作符==、!=、<、<=、>、>=
• 若要比较两个不同类型的容器，必须使用STL比较算法

元素访问

• 所有容器都提供迭代器接口
• 因此它们都支持range-based for循环

八、容器都提供的类型

• 所有容器都提供下图列出的共通类型

转载：https://blog.csdn.net/qq_41453285/article/details/105482769