c++ 11标准模板（STL） std::vector (二）

定义于头文件 <vector>

template<     class T,     class Allocator = std::allocator<T> > class vector;	(1)
namespace pmr {     template <class T>     using vector = std::vector<T, std::pmr::polymorphic_allocator<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,         const Allocator& alloc = Allocator() );		(9)	(C++11 起)

从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 。

1) 默认构造函数。构造拥有默认构造的分配器的空容器。

2) 构造拥有给定分配器 alloc 的空容器。

3) 构造拥有 count 个有值 value 的元素的容器。

4) 构造拥有个 count 默认插入的 T 实例的容器。不进行复制。

5) 构造拥有范围 [first, last) 内容的容器。

若 InputIt 是整数类型，则此构造函数拥有的效果同 vector(static_cast<size_type>(first), static_cast<value_type>(last), a) 。	(C++11 前)
此重载仅若InputIt 满足遗留输入迭代器 (LegacyInputIterator) 才参与重载决议，以避免和重载 (2) 的歧义。	(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;
}

输出