c++ 11标准模板（STL） std::vector (二）
定义于头文件 <vector>
| template< class T, | (1) | |
| namespace pmr { template <class T> | (2) | (C++17 起) |
1) std::vector 是封装动态数组的顺序容器。
2) std::pmr::vector 是使用多态分配器的模板别名。
| 元素相继存储，这意味着不仅可通过迭代器，还能用指向元素的常规指针访问元素。这意味着指向 vector 元素的指针能传递给任何期待指向数组元素的指针的函数。 | (C++03 起) |
vector 的存储是自动管理的，按需扩张收缩。 vector 通常占用多于静态数组的空间，因为要分配更多内存以管理将来的增长。 vector 所用的方式不在每次插入元素时，而只在额外内存耗尽时重分配。分配的内存总量可用 capacity() 函数查询。额外内存可通过对 shrink_to_fit() 的调用返回给系统。 (C++11 起)
重分配通常是性能上有开销的操作。若元素数量已知，则 reserve() 函数可用于消除重分配。
vector 上的常见操作复杂度（效率）如下：
- 随机访问——常数 O(1)
- 在末尾插入或移除元素——均摊常数 O(1)
- 插入或移除元素——与到 vector 结尾的距离成线性 O(n)
std::vector （对于 bool 以外的 T ）满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、序列容器 (SequenceContainer) 、连续容器 (ContiguousContainer) (C++17 起)及可逆容器 (ReversibleContainer) 的要求。
成员函数
构造 vector
std::vector<T,Allocator>::vector| vector(); | （1） | (C++17 前) |
| vector() noexcept(noexcept(Allocator())); | (C++17 起) | |
| explicit vector( const Allocator& alloc ); | (2) | (C++17 前) |
| explicit vector( const Allocator& alloc ) noexcept; | (C++17 起) | |
| explicit vector( size_type count, const T& value = T(), const Allocator& alloc = Allocator()); | （3） | (C++11 前) |
| vector( size_type count, const T& value, const Allocator& alloc = Allocator()); | (C++11 起) | |
| explicit vector( size_type count ); | （4） | (C++11 起) (C++14 前) |
| explicit vector( size_type count, const Allocator& alloc = Allocator() ); | (C++14 起) | |
| template< class InputIt > vector( InputIt first, InputIt last, const Allocator& alloc = Allocator() ); | (5) | |
| vector( const vector& other ); | (6) | |
| vector( const vector& other, const Allocator& alloc ); | (6) | (C++11 起) |
| vector( vector&& other ); | （7） | (C++11 起) (C++17 前) |
| vector( vector&& other ) noexcept; | (C++17 起) | |
| vector( vector&& other, const Allocator& alloc ); | (8) | (C++11 起) |
| vector( std::initializer_list<T> init, | (9) | (C++11 起) |
从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 。
1) 默认构造函数。构造拥有默认构造的分配器的空容器。
2) 构造拥有给定分配器 alloc 的空容器。
3) 构造拥有 count 个有值 value 的元素的容器。
4) 构造拥有个 count 默认插入的 T 实例的容器。不进行复制。
5) 构造拥有范围 [first, last) 内容的容器。
| 若 | (C++11 前) |
| 此重载仅若 | (C++11 起) |
6) 复制构造函数。构造拥有 other 内容的容器。若不提供 alloc ，则如同通过调用 std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator()) 获得分配器。
7) 移动构造函数。用移动语义构造拥有 other 内容的容器。分配器通过属于 other 的分配器移动构造获得。移动后，保证 other 为 empty() 。
8) 有分配器扩展的移动构造函数。以 alloc 为新容器的分配器，从 other 移动内容；若 alloc != other.get_allocator() ，则它导致逐元素移动。（该情况下，移动后不保证 other 为空）
9) 构造拥有 initializer_list init 内容的容器。
参数
| alloc | - | 用于此容器所有内存分配的分配器 |
| count | - | 容器的大小 |
| value | - | 以之初始化容器元素的值 |
| first, last | - | 复制元素的来源范围 |
| other | - | 用作初始化容器元素来源的另一容器 |
| init | - | 用作初始化元素来源的 initializer_list |
复杂度
1-2) 常数
3-4) 与 count 成线性
5) 与 first 和 last 的距离成线性
6) 与 other 的大小成线性
7) 常数。
8) 若 alloc != other.get_allocator() 则为线性，否则为常数。
9) 与 init 的大小成线性。
异常
到 Allocator::allocate 的调用可能抛出。
注意
在容器移动构造（重载 (7) ）后，指向 other 的引用及迭代器（除了尾迭代器）保持合法，但指代现于 *this 中的元素。当前标准由 [container.requirements.general]/12 中的总括陈述作出此保证，而 LWG 2321 正在考虑更严格的保证。
重载 (4) 对如 int 的非类类型元素清零，这与 new[] 将元素保持未初始化的行为不同。为匹配 new[] 的行为，可提供保留元素未初始化的自定义 Allocator::construct 。
析构 vector
std::vector<T,Allocator>::~vector| ~vector(); |
销毁容器。调用元素的析构函数，然后解分配所用的存储。注意，若元素是指针，则不销毁所指向的对象。
复杂度
与容器大小成线性。
调用示例
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <time.h>
#include <vector>using namespace std;struct Cell
{int x;int y;Cell() = default;Cell(int a, int b): x(a), y(b) {}Cell &operator +=(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator +(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator *(const Cell &cell){x *= cell.x;y *= cell.y;return *this;}Cell &operator ++(){x += 1;y += 1;return *this;}bool operator <(const Cell &cell) const{if (x == cell.x){return y < cell.y;}else{return x < cell.x;}}bool operator >(const Cell &cell) const{if (x == cell.x){return y > cell.y;}else{return x > cell.x;}}bool operator ==(const Cell &cell) const{return x == cell.x && y == cell.y;}
};std::ostream &operator<<(std::ostream &os, const Cell &cell)
{os << "{" << cell.x << "," << cell.y << "}";return os;
}int main()
{std::cout << std::boolalpha;std::mt19937 g{std::random_device{}()};srand((unsigned)time(NULL));auto generate = [](){int n = std::rand() % 10 + 110;Cell cell{n, n};return cell;};//从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 。//1) 默认构造函数。构造拥有默认构造的分配器的空容器。//2) 构造拥有给定分配器 alloc 的空容器。std::vector<Cell> vector1;std::cout << "vector1 empty: " << vector1.empty() << std::endl;//3) 构造拥有 count 个有值 value 的元素的容器。std::vector<Cell> vector2(6, generate());std::cout << "vector2: ";std::copy(vector2.begin(), vector2.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;//4) 构造拥有个 count 默认插入的 T 实例的容器。不进行复制。std::vector<Cell> vector3(6);std::cout << "vector3: ";std::copy(vector3.begin(), vector3.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;//5) 构造拥有范围 [first, last) 内容的容器。//6) 复制构造函数。构造拥有 other 内容的容器。若不提供 alloc ，则如同通过调用获得分配器std::vector<Cell> vector4(vector2.begin(), vector2.end());std::cout << "vector4: ";std::copy(vector4.begin(), vector4.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;//7) 移动构造函数。用移动语义构造拥有 other 内容的容器。//分配器通过属于 other 的分配器移动构造获得。移动后，保证 other 为 empty() 。//8) 有分配器扩展的移动构造函数。以 alloc 为新容器的分配器，//从 other 移动内容；若 alloc != other.get_allocator() ，则它导致逐元素移动。std::vector<Cell> vector5(std::move(vector2));std::cout << "vector5: ";std::copy(vector5.begin(), vector5.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;std::cout << "vector2 empty: " << vector2.empty() << std::endl;//9) 构造拥有 initializer_list init 内容的容器。std::vector<Cell> vector6({{101, 101}, {102, 102}, {103, 103},{104, 104}, {105, 105}, {106, 106}});std::cout << "vector6: ";std::copy(vector6.begin(), vector6.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;return 0;
}输出
