vector是一种封装动态数组的序列容器，在内存中连续排列。

vector的size

vector对象大小是固定的。

class vector {
...
protected:
    iterator start;           // 目前使用空间的头
    iterator finish;          // 目前使用空间的尾
    iterator end_of_storage;  // 目前可用空间的尾
...
};

std::vector<int> v;
// 输出24
std::cout << sizeof(v) << std::endl;

vector的构造函数

vector<int> v1;                                  // 无元素
vector<int> v2 {1, 2, 3, 4, 5};                  // 列表初始化
vector<int> v3(4);                               // 4个元素，初始值为0
vector<int> v4(5, 3);                            // 5个元素，初始值为3
vector<int> v5(v4);                              // 使用另外一个vector拷贝构造
vector<int> v6(std::move(v5));                   // 使用另外一个vector移动构造
vector<int> v7(arr1, arr1+5);                    // 使用指针初始化
vector<int> v8(v4.begin(), v4.end());            // 使用迭代器初始化[左闭,右开）

vector的成员函数

访问

成员函数 函数说明
at( size_type n ) 带有边界检查，返回对索引 n 处元素的引用。如果索引越界，则抛出 std::out_of_range 异常。
operator[]( size_type n ); 返回对索引 n 处元素的引用。不执行边界检查，速度更快。
front() 返回对第一个元素的引用。
back() 返回对最后一个元素的引用。
T* data() 返回指向底层数组的指针。

修改

成员函数 说明
void clear() 移除所有元素，使 vector 变为空。
insert( iterator position, const T& val ) 在 position 前插入一个值为 val 的新元素。
erase( const_iterator position ) 移除 position 处的元素。
push_back( const T& val ) 在 vector 的末尾添加一个新元素 val。
pop_back(); 移除 vector 的最后一个元素。
emplace(iterator position, Args&&... args ) 在 position 处通过就地构造插入新元素。
emplace_back( Args&&... args ) 在 vector 末尾通过就地构造插入新元素。
resize( size_type count ) 改变 vector 的大小为 count。
如果 count 小于当前大小，多余的元素会被移除；
如果 count 大于当前大小，新元素会默认初始化。
swap( vector& other ) 与另一个 vector 交换内容。

容量

成员函数 说明
empty() 如果 vector 中没有元素，则返回 true。
size() 返回 vector 中元素的数量。
max_size() 返回 vector 可以容纳的最大元素数量。和系统或库实现相关。
reserve( size_type new_cap ) 请求 vector 的容量至少为 new_cap。只在new_cp大于原有capacity时才扩容。
capacity() 返回 vector 当前分配的内存可以容纳的元素数量。
shrink_to_fit(); 减少容量以适应其大小。可能会释放未使用的内存。非强制，能否达成依赖于实现。

操作

| 成员函数 | 说明 | | ——————————————- | ——————————————————– | | assign( size_type count, const T& value ) | 将 vector 的内容替换为 count 个值为 value 的元素。 |

迭代器

成员函数 说明
begin() 返回指向 vector 第一个元素的迭代器。
end() 返回指向 vector 最后一个元素之后位置的迭代器。
rbegin() 返回指向 vector 最后一个元素的反向迭代器。
rend() 返回指向 vector 第一个元素之前位置的反向迭代器。
cbegin() 返回指向 vector 第一个元素的 const 迭代器。
cend() 返回指向 vector 最后一个元素之后位置的 const 迭代器。
crbegin() 返回指向 vector 最后一个元素的 const 反向迭代器。
crend() 返回指向 vector 第一个元素之前位置的 const 逆向迭代器。

vector的扩容机制

在插入元素时，如果size==capcaity时进行扩容操作：

  1. 开辟一块更大的内存空间
  2. 将原来的元素复制到新的内存空间（优先尝试移动构造）
  3. 释放原有空间
  4. 将新的元素插入到新的内存空间中

扩容特点：

  • 对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都将失效。
  • 初始时刻vector的capacity为0，插入第一个元素后capacity增加为1。
  • 不同的编译器实现的扩容方式不一样，MSVC中以1.5倍扩容，GCC以2倍扩容。

为什么使用成倍扩容策略： 使用成倍扩容策略，平均下来插入一个元素的平均时间复杂度为O(1)。

为什么使用1.5倍或2倍扩容： 理想的扩容方案是在第N次扩容时可以复用之前N-1次释放的空间。如果按照2倍方式扩容，第i次扩容空间大小如下：

1 2 4 8 16 32 64 ...

可以看到，每次扩容时，前面释放掉的空间都不能使用。

比如：第4次扩容时，假设前3次空间已经释放，即释放的空间有1+2+4=7，而第四次需要8，导致无法使用之前的空间。

但使用使用1.5倍扩容时，在几次扩容后，就可能重用之前的内存空间。

参考