C++ Vectors [C++ Reference]

C++ Vectors

#include <vector>
 
template<
    class T,
    class Allocator = std::allocator<T>
> class vector;

std::vector（C++向量）是一个支持快速随机访问和快速尾部元素插入删除的容器。不支持容器内部快速插入删除操作。它是用数组实现的。

访问 vector 中的元素可以在常数时间（O(1)）内完成，向 vector 追加元素也可以在 amortized constant time 内完成，而定位一个特殊值元素或向 vector 中插入元素将要花费线性时间(O(N))。

成员类型

成员类型	定义
`value_type`	`T`
`allocator_type`	`Allocator`
`size_type`	Unsigned integral type (usually `size_t`) （无符号整型）
`difference_type`	Signed integral type (usually `ptrdiff_t`)（符号整型）
`reference`	`Allocator::reference`
`const_reference`	`Allocator::const_reference`
`pointer`	`Allocator::pointer`
`const_pointer`	`Allocator::const_pointer`
`iterator`	Random access iterator（随机存取迭代器）
`const_iterator`	Constant random access iterator
`reverse_iterator`	`std::reverse_iterator<iterator>`
`const_reverse_iterator`	`std::reverse_iterator<const_iterator>`

成员函数

std::vector（C++向量）包括下列成员函数：

常用

(constructor)	creates a vector（创建一个向量）
operator=	assigns values to the container（赋值给容器）
assign	assigns values to the container（赋值给容器）
operator==,!=,>,<,>=,<=	compares vectors with other vectors（和其他容器比较）
get_allocator	returns the allocator associated with the container

元素访问

at	带越界检查地访问指定元素
operator[]	访问指定元素
front	返回 vector 第一个元素的引用
back	返回 vector 最后一个元素的引用
data	returns a pointer to the underlying collection of data （返回指向当下数据集的指针）

迭代器

begin, cbegin	返回指向头部的迭代器
end, cend	返回指向尾部的迭代器
rbegin, crbegin	returns a `reverse_iterator` to the beginning of reversed container（返回指向反向容器头部的“反向迭代器”）
rend, crend	returns a `reverse_iterator` to the end of reversed container （返回指向反向容器尾部的“反向迭代器”）

容量

empty	检查容器是否为空
size	返回元素个数
max_size	返回元素个数最大值
reserve	反向存储
capacity	returns the number of elements that can be held in currently allocated storage（返回 vector 可以容纳的最大元素数量）
shrink_to_fit	通过释放未使用内存减少内存使用(C++0x feature)

Modifiers（修改器）

clear	清除所有元素
insert	插入元素
emplace	todo (C++0x feature)
erase	清除元素
push_back	在尾部插入一个元素
emplace_back	todo (C++0x feature)
pop_back	清除尾部的元素
resize	改变存储元素的个数
swap	与另一个 vector 交换所有内容

Note that a boolean vector (vector<bool>) is a specialization of the vector template that is designed to use less memory. A normal boolean variable usually uses 1-4 bytes of memory, but a boolean vector uses only one bit per boolean value. todo

需要注意的是，boolean 类型的 vector 是一个特殊的 vector 模板，是一种更少内存使用的设计。正常情况下，一个 boolean 变量要用到 1-4 bytes 内存，但是在 boolean 类型的 vector 中，每一个 boolean 值只使用 1 bit 内存。