sequential container

元素加入容器的先后顺序决定了其在容器中的位置

除了顺序容器还有关联容器

容器拥有一些共通的接口

头文件

Copy 1#include <vector>
 2
 3#include <deque>
 4
 5#include <array>
 6
 7#include <forward_list>
 8
 9#include <list>
10
11#include <string>

固定大小数组

array

到了C++, 需要使用内置数组时, 建议使用array

相比内置数组，array更安全，也更容易使用

array不支持增删元素，以及修改容器大小的操作

顺序容器的特点

1. array，vector，string，deque
   
   将元素整片存储 -> 支持随机访问
   

2. list和forward_list
   
   将元素分开存储 -> 保存元素的先后位置会占用内存
   

3. 除了array外，其他容器都提供高效灵活的内存管理
   
   可以增删元素，扩张和收缩容器的大小
   

4. forward_list没有size操作，更快
   

forward_list和array是新C++标准增加的类型

顺序容器的选择

标准

1. 访问指定位置元素的需求
   

   -
   vector，deque，array，string	将元素保存在连续的内存空间 -> 可以使用下标访问 -> 支持随机访问
   list和forward_list	将元素分开存储 -> 不支持随机访问, 只支持顺序访问

2. 增删元素的开销
   

   -
   vector，deque，array，string	将元素保存在连续的内存空间 -> 增加元素可能需要扩容; 增删元素可能需要移动元素
   deque	有指向队首元素和队尾元素的迭代器 -> 两端增删元素很快，同list和forward_list
   list和forward_list	将元素分开存储 -> 增删元素很快速, 无额外开销

场景

优先使用vector

• 在意空间的额外开销: 不建议使用list和forward_list
  

• 要求随机访问: 建议使用vector和deque
  
  list和forward_list不支持
  

  string只能存储字符
  

  array限定了元素个数
  

• 经常需要在容器指定位置插入/删除元素: 建议使用使用list或forward_list
  

• 需要在首尾位置插入/删除元素，不会在中间位置插入和删除: deque
  

• 输入时需要在中间位置插入元素，之后需要随机访问(有排序需求)
  

  最终肯定是vector
  

  一开始可以使用list
  

  如果有某种顺序，可以使用vector之后调用sort排序
  

• 不确定使用哪种容器
  
  在程序中使用vector和list的公共操作：不使用下标，使用迭代器
  

顺序容器的比较

1. 对常用功能的支持
   

   顺序容器	大小可变	支持任意位置添加/删除元素(开销小)	支持随机访问(连续存储)	只支持顺序访问
   array	X	-	O	-
   vector(string)	O	X	O	-
   deque	O	X	O	-
   list	O	O	X	O
   forward_list	O	O	X	O

2. 顺序容器各自的特性
   

   顺序容器	大小	增加/删除元素	存储和访问
   array	固定	不可以	连续存储, 随机访问
   vector(string)	可变	尾部: 增/删; 可能需要扩容	同上
   deque	可变	首/尾部: 增/删; 可能需要扩容	同上
   list	可变	指定位置: 增/删	顺序访问
   forward_list	可变	指定位置之后: 增/删	同上