vector
随机访问 在序列末尾插入和删除元素为常量时间，而在中间插入和删除元素需要线性时间
介绍
- vector为可变长的数组（动态数组），定义的vector数组可以随时添加和删除元素
- 当vector容量不足以容纳新增元素时会扩容为两倍（不同编译器有不同的实现，GCC以两倍扩容），需要将元素复制到新开辟的空间
在局部作用域中vector数组是开辟在堆区的，而普通数组是开辟在栈区的
因为栈的大小通常较小，所以如果要开辟很大的数组要用vector
头文件
#include <vector>
初始化
// 默认初始化
vector();
// 初始化指定大小的vector
explict vector(size_type count);
// 初始化指定大小的vector并赋值为指定value
vector(size_type count, const Type& value);
// 用vector初始化vector
vector(const vector& source);
vector(vector&& source);
// 用迭代器指定范围的元素初始化vector
template <class InputIterator>
vector(InputIterator first, InputIterator last);
创建指定大小的二维数组
// 方法一
int m = 2, n = 3;
vector<vector<int> vec(m, vector<int>(n));
// 方法二
vector<vector<int> vec;
vec.resize(m);
for(int i = 0; i < m; ++i) {
vec[i].resize(n);
}
函数
assign
清空vector并将指定元素复制到vector
// assign
void assign(size_type count, const Type& value);
// 初始化列表
void assign(initializer_list<Type> ini_list);
template <class InputIterator>
void assign(InputerIterator first, InputIterator last);
at
- 返回指定位置的元素
- 尝试返回不存在的位置时抛出异常
reference at(size_type position);
const_reference at(size_type position);
back
- 返回对向量中最后一个元素的引用
- 如果vector为空，则返回值不确定
reference back();
const_reference back() const; // 第二个const保证了该函数不会改变对象的状态
begin
- 返回vector指向第一个元素的迭代器
- 如果vector为空则返回容器开始的位置，这时和end返回的位置相同
const_iterator begin() const;
iterator begin();
capacity
返回在不分配更多的存储的情况下vector可以包含的元素个数
size_type capacity() const;
cbegin
- 返回第一个元素地址的const迭代器
- 对于空vector，cbegin == cend
const_iterator cbegin() const;
cend
返回指向最后一个元素后面一个位置
const_interator cend() const;
clear
- 清除vector中的元素
- 调用之后size变为0，capacity不变
void clear();
crbegin
返回指向最后一个元素的const迭代器
const_reverse_iterator crbegin() const;
crend
返回指向第一个元素前面一个位置的迭代器
const_reverse_iterator crend() const;
data
返回指向第一个元素的指针，不提供范围检查（使用时要小心）
const_pointer data() const;
pointer data();
empty
vector为空返回true，否则返回false
bool empty() const;
end
返回vector最后一个元素的后一个位置的迭代器
iterator end();
const_iterator end() const;
erase
- 从指定位置删除元素
- 返回操作之后的vector的第一个元素的位置
- 时间复杂度为o(n)
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
front
- 返回vector中第一个元素的引用
- 若vector为空，返回值不确定
reference front();
const_reference front() const;
insert
返回的迭代器指向新插入的元素
iterator insert(const_iterator position, const Type& value);
iterator insert(const_iterator position, const Type&& value);
void insert(const_iterator position, size_type count, const Type& value);
template <class InputIterator>
void insert(const_iterator position, InputIterator first, InputIterator last);
max_size
- 返回vector最大可取长度
- 取决于系统内存容量
size_type max_size() const;
pop_back
删除末尾元素
void pop_back();
push_back
在尾部添加元素
void push_back(const T& value);
void push_back(T&& value);
rbegin
返回反向第一个元素
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
rend
返回反向最后一个元素的后一个位置
const_reverse_iterator rend() const;
reverse_iterator rend();
reserve
- 预留长度
- 不会影响size，如果reserve小于size则什么都不做
- 如果capacity已经足够大，则什么都不做
void reserve(size_type count);
resize
为vector指定新的大小
void resize(size_type new_size);
// value表示新插入的元素值
void resize(size_type new_size, Type value);
shrink_to_fit
放弃额外容量
void shrink_to_fit();
size
返回vector中的元素数量
size_type size() const;
swap
交换两个vector中的元素
// 不需要显示指定分配器
void swap(vector<Type, Allocator>& right);
friend void swap(vector<Type, Allocator>& left, Allocator>& right);
运算符
operator[]
- 返回指定位置元素的引用,
- 如果访问越界发生错误，没有at安全
reference operator[](size_type position);
const_reference operator[](size_type position) const;
operator=
vector& operator=(const vector& right);
vector& operator=(vector&& right);
operator==
时间复杂度为o(n)
bool operator==(const vector<Type, Allocator>& left, const vector<Type, Allocator>& right);