vector是用数组实现的、可变长度的顺序容器，本质是一种类模板。
template <
class T, // 元素类型
class Alloc = allocator<T> > // 空间配置器类型
class vector; // 类模板声明
| 接口声明 | 解释 |
|---|---|
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) | 赋值重载 |
| 容量操作 | 解释 |
|---|---|
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倍增容。
| 接口声明 | 解释 |
|---|---|
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 中容器的迭代器区间都是采用 [ f i r s t , l a s t ) [first,last) [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 << " ";
}
| 接口声明 | 解释 |
|---|---|
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);
template <class T, class Alloc = alloc>
class vector {
public:
typedef T* iterator;
// ...
private:
iterator start;
iterator finish;gggg
iterator end_of_storage;
}
这个结构和顺序表结构稍有不同，但本质是一样的。只是将容量和元素个数的变量用指向对应位置的迭代器代替。
class Seqlist {
T* _a; /* start */
size_t _size; /* finish - start */
size_t _capacity; /* end_of_storage - start */
}
//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就是一种指定的迭代器类型。因容器的结构各有不同，迭代器分为五种类型：
| 迭代器类型 | 名称 | 解释 | 适用容器 |
|---|---|---|---|
| input/output_iterator | 输入/输出迭代器 | 只读迭代器只能读取，只写迭代器可以写入该位置的值 | 无实际容器 |
| forward_iterator | 向前迭代器 | 只能向前移动（++），允许在迭代器位置进行读写 | forward_list |
| bidirectional_iterator | 双向迭代器 | 可以双向移动（++,––），允许在迭代器位置进行读写 | list, map, set |
| random_access_iterator | 随机迭代器 | 支持指针运算，可移动（++,––）任意跳转（+,–）读写(*) | deque,vector,string |
可以看出，下方的迭代器类型是上方的父类，也就是说下方迭代器满足上方的所有要求。
划分出不同的迭代器类型，是为了限制传入的迭代器，因为其必须满足要求才能完成接下来的函数。
函数如果指明迭代器类型为InputIterator，意思是满足输入迭代器的要求的迭代器都可以作此参数。故此处我们可以传入任意的迭代器。
一般底层是数组连续空间的容器，例如 vector, string 等都是随机迭代器。
像双向链表这样的非连续空间的容器是双向迭代器。
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将原空间的内容按字节拷贝至新空间。
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)); // err
for (int i = 0; i < size(); i++)
{
tmp[i] = _start[i];//_start指向的空间存任意类型都能完成深拷贝
}
delete[] _sta rt;
}
_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;
}
}
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; //返回删除数据的下一个位置
}
| 题目 | 题解 |
|---|---|
| 只出现一次的数字 | 【简洁明了】只出现一次的数字 I |
| 杨辉三角 | 【简洁明了】cpp 杨辉三角 |
| 删除有序数组中的重复项 | 【双指针 简单明了】数组去重 |
| 只出现一次的数字 II | 【简单明了 注释】只出现一次的数字 |
| 只出现一次的数字 III | 【详细解析】只出现一次的数字 系列 I II III |
| 多数元素 | 【哈希 排序 投票】三种解法 简洁明了 |
| 连续子数组的最大和 | 【动归】连续子数组的最大和 |
| 电话号码的字母组合 | 【注释解析 回溯】电话号码字母组合 |