---

vector

vector是动态空间，随着元素的加入它内部机制会自行空充空间以容纳新元素。vector维护了一个连续的线性空间，普通指针就可以满足要求作为vector的迭代器，随机访问迭代器。vector里面其实有三个迭代器，分别是指向空间头部的iterator，指向空间尾部的iterator和指向可用空间的iterator。当有新的元素插入时，如果当前容量够就直接插入，如果容量不够则扩容至两倍或1.5倍，如果两倍不足，则扩容至足够大的空间。由于扩充过程不是在原有的空间后面追加，而是重新申请一块新的连续内存，所以所有迭代器都会失效。

template < class T, // 元素类型class Alloc = allocator<T> > // 空间配置器类型class vector; // 类模板声明

1. vector的接口

1.1 默认成员函数

接口声明	解释
vector()	默认构造
vecotr(size_type n, const_value_type& val=value_type())	填充构造，填充n个元素
vector(InputIter first, InputIter last)	范围构造，迭代器区间初始化
vector(const vector& v)	拷贝构造
vector& operator=(const vector& x)	赋值重载

1.2 容量操作

容量操作	解释
size_type size()	元素个数
size_type capacity()	容量大小
size_type max_size()	最大能存储的元素个数（无意义）
void resize(size_type n, value_type val = value_type());	增减有效元素个数

v.reserve(100);   // 扩容到100
v.resize(100, 1); // 有效元素个数变为100,新增元素初始化为1
v.resize(10);     // 有效元素个数变为10

由图可知，vs下vector按1.5倍增容。

1.3 访问操作

接口声明	解释
reference operator[](size_type n)	返回下标位置的引用
const_reference operator[] (size_type n) const
reference at(size_type n)
const_reference at (size_type n) const

[]重载和at的区别是，[]越界会断言报错，at是抛异常。

迭代器接口	解释
begin	起始位置的迭代器
end	末尾元素的下一个位置的迭代器
rbegin	反向起始位置的迭代器
rend	反向末尾元素的下一个位置的迭代器
cbegin,cend	begin 和 end 的 const 版本

[]重载就已经能方便的访问 vector，但并不意味着放弃迭代器。大部分容器都支持迭代器访问，且迭代器使用简单规范统一。

STL 中容器的迭代器区间都是采用 $[first,last)$ 左闭右开的方式。

//[]
for (size_t i = 0; i < v.size(); i++) {v1[i] += 1;
}//iterator
vector<int>::iterator it = v.begin();
while (it != v.end()) {cout << *it << " ";it++;
}for (auto e : v) {cout << e << " ";
}

1.4 修改操作

接口声明	解释
void push_back (const value_type& val)	尾插
void pop_back()	尾删
iterator insert (iterator pos, const value_type& val)	迭代器位置插入
void insert (iterator pos, size_type n, const value_type& val);	迭代器位置插入
void insert (iterator pos, InputIter first, InputIter last)	迭代器位置插入一段区间
iterator erase (iterator pos)	迭代器位置删除
iterator erase (iterator first, iterator last)	删除一段迭代器区间
void assign (size_type n, const value_type& val)	覆盖数据

v.insert(ret, 30);
v.insert(ret, 2, 30);
v.insert(ret, v2.begin(), v2.end());
v1.erase(pos);
v1.erase(v1.begin(), v1.end());

#include <algorithm>
// 查找接口
template <class InputIter, class T>InputIter find (InputIter first, InputIter last, const T& val);

1.5 vector与常见的数据结构的对比

大伙们看看它们的主要特性和区别如下：

以下是 vector和array对比表格:

特性	vector	array
动态大小	可以动态增长或缩小	大小固定，定义时确定
内存管理	自动管理内存，大小动态调整	静态分配，大小不变
容量管理	有 size()、capacity() 和 reserve() 方法	可以使用 size() 方法获取大小
初始化	可以使用初始化列表或复制其他 vector	可以使用初始化列表或逐个赋值
存储元素类型	可以存储任意类型的数据	只能存储相同类型的数据
访问元素	通过 at()、[] 或迭代器访问	通过 [] 或指针访问
插入与删除	插入和删除元素会自动调整内存	不支持直接插入或删除元素
复制与传递	复制时会复制所有元素	传递时通常是指针或引用
原始数组特性	无法访问指针指向的连续内存块	可以直接操作指向的连续内存块
标准库支持	提供丰富的算法和方法操作	支持的操作有限，主要依赖于指针操作

以下是 vector 和 list 的对比表格：

特性	vector	list
内部结构	底层基于动态数组	底层基于双向链表
访问元素	随机访问（[] 或 at()），时间复杂度 O(1)	顺序访问（只能通过迭代器），时间复杂度 O(n)
内存管理	自动管理内存，大小动态调整	自动管理内存，节点动态分配和释放
插入与删除	插入和删除元素可能需要调整内存	插入和删除元素对内存影响较小
容器大小	可以动态增长或缩小	可以动态增长或缩小
迭代器稳定性	操作过程中不会使迭代器失效	插入或删除元素后，迭代器可能失效
内存占用	在大多数情况下比较节省内存	每个元素都有额外的指针开销
性能分析	随机访问性能好，适合需要频繁访问的场景	插入和删除性能好，适合需要频繁插入和删除的场景
使用场景	适合需要频繁访问元素的场景	适合需要频繁插入和删除元素的场景

以下是 vector 和 list 在常见操作的时间复杂度对比：

操作	vector	list
访问元素	O(1)	O(n)
在末尾插入/删除	平均 O(1)，最坏情况 O(n)	平均 O(1)
在开头插入/删除	平均 O(n)，最坏情况 O(n)	平均 O(1)
在中间插入/删除	平均 O(n)，最坏情况 O(n)	平均 O(1)
容量调整	O(n)	不适用，链表不需要调整容量
迭代器操作	随机访问迭代器 O(1)	迭代器无法直接访问元素，需要遍历链表 O(n)

2. vector的模拟实现

vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。如图：

2.1 类的定义

template <class T, class Alloc = alloc>
class vector {
public:typedef T* iterator;// ...
private:iterator start;iterator finish;iterator end_of_storage;
}

这个结构和顺序表结构稍有不同，但本质是一样的。只是将容量和元素个数的变量用指向对应位置的迭代器代替。

class Seqlist {T* _a;            /* start */size_t _size;     /* finish - start */size_t _capacity; /* end_of_storage - start */
}

2.2 默认成员函数

//default constructor
vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}
//fill constructor
vector(size_t n, const T& val = T()) // 引用临时对象可延长其声明周期: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{resize(n, val);  
}
//copy constructor
vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];for (size_t i = 0; i < v.capacity(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

//range constructor
template <class InputIterator>
vector(InputIterator first, InputIterator last) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last) {push_back(*first++);}
}
//destructor
~vector() 
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}// 现代写法
//copy constructor
vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{vector<T> tmp(v.begin(), v.end());swap(tmp);
}
//operator=
vector<T>& operator=(vector<T> v)  /* pass by value */
{swap(v);return *this;
}

从范围构造可以看出类模板中的函数也可以是函数模板。

迭代器的分类

函数模板的模板参数要传迭代器区间时，命名是有规定的，范围构造中的InputIterator就是一种指定的迭代器类型。因容器的结构各有不同，迭代器分为五种类型：

名称	特性	适用容器
输入/输出迭代器	只读迭代器只能读取，只写迭代器可以写入	无实际容器
单向迭代器	++，读写	forward_list
双向迭代器	++，––，读写	list, map, set
随机迭代器	++，––，+，–，读写	deque, vector, string

可以看出，下方的迭代器类型是上方的父类，也就是说下方迭代器满足上方的所有要求。

划分出不同的迭代器类型，是为了限制传入的迭代器，因为其必须满足要求才能完成接下来的函数。

函数指明迭代器为InputIterator，意味着满足要求的迭代器都可以传入，起提示的作用。

当然，模版不区分类型，语法上所有迭代器都可以传入，但可能无法完成编译。

2.3 容量接口

memcpy 浅拷贝问题

vector<string> v;
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111"); // 增容浅拷贝

出现问题是因为正好数组需要增容。模拟实现的reserve函数使用memcpy将原空间的内容按字节拷贝至新空间。

1. 若 vector 存储的是内置类型，则浅拷贝没问题。
2. 若 vector 存储的是自定义类型，浅拷贝使得新旧变量指向同一块空间。深拷贝调用拷贝构造或者赋值重载。

内存增长机制

当空间不足以容纳数据时（例如使用 vec.push_back(val)），std::vector 会自动申请更大的内存空间，通常是当前大小的1.5倍或2倍（具体取决于编译器，例如GCC通常是2倍，而在VS下的MinGW是1.5倍）。然后，它会将原有数据拷贝到新的内存空间中，并释放原来的内存空间。

当你释放或清空数据（使用 vec.clear()）时，std::vector 的存储空间不会被释放，只是清空了数据元素。因此，对 std::vector 的任何操作，一旦触发了内存重新配置，会导致指向原 vector 的所有迭代器失效。

void reserve(size_t n) 
{if (n > capacity()) {T* tmp = new T[n];size_t oldSize = size();if (_start) {//memcpy(tmp, _start, size() * sizeof(T)); // errfor (int i = 0; i < size(); i++) {tmp[i] = _start[i];//_start指向的空间存任意类型都能完成深拷贝}delete[] _start;}_start = tmp;_finish = _start + oldSize;_end_of_storage = _start + n;}
}

void resize(size_t n, T val = T())
{if (n > size()){reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}
}

reserve和resize的区别

reserve 是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化 push_back），可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve 只是保证 vector 中的空间大小（capacity）最少达到参数所指定的大小 n，预留空间。

resize 可以改变有效空间的大小，也有改变默认值的功能。capacity 的大小也会随着改变。resize() 可以有多个参数。 resize() 改变了 vector 的 capacity 同时也增加了它的 size！

原因如下：

1. reserve 是容器预留空间，但在空间内不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用 push_back()/insert() 函数。

2. resize 是改变容器的大小，且在创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用 operator[] 操作符，或者用迭代器来引用元素对象。此时再调用 push_back() 函数，是加在这个新的空间后面的。

可能大家平时用 reserve() 比较多，顾名思义，reserve 就是预留内存。为的是避免内存重新申请以及容器内对象的拷贝。说白了，reserve() 是给 push_back() 准备的！而 resize 除了预留内存以外，还会调用容器元素的构造函数，不仅分配了 N 个对象的内存，还会构造 N 个对象。

从这个层面上来说， resize() 在时间效率上是比 reserve() 低的。但是在多线程的场景下，用 resize 再合适不过。

2.4 修改接口

iterator insert(iterator pos, const T& val)
{assert(_start <= pos && pos <= _finish); // 检查pos位置是否合法// 增容if (_finish == _end_of_storage) {size_t sz = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2); //增容会导致迭代器失效，迭代器位置陈旧pos = _start + sz; //增容后更新pos}// 后移 [pos,_finish)for (iterator end = _finish; end > pos; --end){*end = *(end - 1);}// 插入*pos = val;++_finish;return pos; //返回迭代器最新位置
}

• 增容改变_start，但迭代器pos并没有跟着改变，仍然指向原空间，也就是迭代器失效。
• 迭代器pos实参并没有改变仍然指向错误位置，故函数返回更新的pos。

iterator erase(iterator pos)
{assert(_start <= pos && pos < _finish);for (iterator begin = pos + 1; begin < _finish; begin++){*(begin - 1) = *begin;}_finish--;return pos; //返回删除数据的下一个位置
}

• erase 挪动数据后 pos 指向元素会发生变化，同样会导致迭代器失效。
• 返回删除数据的下一个位置，通过返回值更新迭代器。

迭代器失效问题

1. 插入操作导致迭代器失效

当向 vector 中插入元素时，如果当前容量不足，vector 会重新分配内存，并将现有元素复制到新的内存空间中。这种内存重分配会导致所有之前获取的迭代器失效，因为它们仍然指向旧的内存地址，而不是新分配的地址。例如：

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();  // 获取迭代器指向 vec 的第一个元素vec.push_back(4);  // 插入元素导致内存重分配，it 指向的地址已经无效
// it 现在是一个悬空指针，不能再安全地使用

解决方法是，在插入操作之后重新获取迭代器，或者使用返回的插入位置迭代器。

2. 删除操作导致迭代器失效

删除 vector 中的元素会导致迭代器失效，特别是被删除元素之后的所有元素的位置都会向前移动。如果使用的是被删除元素的迭代器，那么在调用删除操作后，该迭代器就变得无效。例如：

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2;  // it 指向 vec 的第三个元素，值为 3vec.erase(it);  // 删除元素 3// 现在 it 指向的位置已经是无效的，应该重新赋值或者使用 erase 返回的迭代器

为了安全地进行删除操作，可以使用 erase 方法返回的迭代器，它指向被删除元素之后的下一个有效位置：

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2;  // it 指向 vec 的第三个元素，值为 3it = vec.erase(it);  // 删除元素 3，并更新 it 为下一个有效迭代器

 

3. vector的oj题

题目	题解
只出现一次的数字	【简洁明了】只出现一次的数字 I
杨辉三角	【简洁明了】cpp 杨辉三角
删除有序数组中的重复项	【双指针 简单明了】数组去重
只出现一次的数字 II	【简单明了 注释】只出现一次的数字
只出现一次的数字 III	【详细解析】只出现一次的数字 系列 I II III
多数元素	【哈希 排序 投票】三种解法 简洁明了
连续子数组的最大和	【动归】连续子数组的最大和
电话号码的字母组合	【注释解析 回溯】电话号码字母组合