type
status
date
slug
summary
tags
category
icon
password
Property
顺序容器类型
一个容器就是一些特定类型对象的集合。所有顺序容器（sequential container） 都为程序员提供了快速顺序访问元素的能力。但是这些容器在以下方面都有不同的性能折中：
- 向容器添加或从容器中删除元素的代价
- 非顺序访问容器中元素的代价
除了固定大小的
array外，其他容器都提供高效、灵活的内存管理：string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间中。
list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，只能遍历整个容器。且与vector、deque和array相比， 这两个容器的额外内存开销也很大
deque是一个更为复杂的数据结构。与string和vector类似，deque支持快速的随机访问。与strìng和vector一样，在deque的中间位置添加或删除元素的代价（可能）很高。但是，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当
forward_list和array是C++11新增类型：- 与内置数组相比，
array更安全易用。array对象大小固定，不支持添加和删除元素以及改变容器大小的操作
forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。
新标准库容器的性能几乎肯定与最精心优化过的同类数据结构一样好（通常会更好）。现代
C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。容器选择原则：
- 除非有合适的理由选择其他容器，否则应该使用
vector
- 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用
list或forward_list
- 如果程序要求随机访问容器元素，则应该使用
vector或deque
- 如果程序需要在容器头尾位置插入/删除元素，但不会在中间位置操作，则应该使用
deque
- 如果程序只有在读取输入时才需要在容器中间位置插入元素，之后需要随机访问元素，则：
- 先确定是否真的需要在容器中间位置插入元素。处理输入数据时，可以先向
vector追加数据，再调用标准库的sort函数重排元素，从而避免在中间位置添加元素 - 如果必须在中间位置插入元素，可以在输入阶段使用
list。输入完成后将list中的内容拷贝到vector中。
- 不确定应该使用哪种容器时，可以先只用
vector和list的公共操作：使用迭代器，不使用下标操作，避免随机访问。这样在必要时选择vector或list都很方便
如果同时需要随机访问和在中间部分插入或删除元素？此时需要看占主要的操作是什么（更多的是插入或删除，还是更多的是访问），来决定使用哪种类型的容器。在这种情况下，使用多种容器进行性能测试是必不可少的。
如果不知道该选择哪种容器，那就进使用
vector和list共同的接口：迭代器而不是下标，避免随机访问元素。这样就可以在需要时很容易的替换。