当前位置:   article > 正文

C++(标准库):12---STL容器总体概述_容器用来管理一大群元素。为了适应不同需要,stl提供了不同的容器,如下图所示

容器用来管理一大群元素。为了适应不同需要,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内部预先定义好的无序容器有:
  • 在无序容器中,元素没有明确的排序次序。也就是如果容器中有三个元素,当你迭代器容器内的所有元素时,它们的次序可能不同,当你再插入一个新元素时,先前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循环

八、容器都提供的类型

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/843783
推荐阅读
相关标签
  

闽ICP备14008679号