【C++】Vector -- 详解（上）https://developer.aliyun.com/article/1514669?spm=a2c6h.13148508.setting.27.4b904f0ejdbHoA
二、vector深度剖析及模拟实现
1、vector 的底层结构
源码中，SGI 版本 STL - vector 的实现：
template <class T, class Alloc = alloc> class vector { public: typedef T value_type; typedef value_type* iterator; // 指向数组空间的指针T*是天然的d // ... protected: // ... iterator start; iterator finish; iterator end_of_storage; // 成员变量是三个T*类型的指针 // ... };
源码中，push_back 尾插接口的实现：
定位 new 表达式在实际中一般是配合内存池使用。因为 vector 的空间是从内存池来的，内存池分配出的空间是没有初始化的，该空间存放的是哪个自定义类型对象，就使用定位 new 表达式显示调用其构造函数进行初始化。
2、std::vector 的核心框架接口的模拟实现 xyl::vector
（1）vector 的结构
#pragma once #include <iostream> #include <vector> #include <string> #include <cassert> // assert #include <cstring> // memcpy using namespace std; namespace xyl { template<class T> // T: 模板参数，指vector中存放数据的类型 class vector { public: // iterator是内嵌类型，在vector类域里面定义的类型 // vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } private: iterator _start; // 指向数组的开始 iterator _finish; // 指向最后一个有效元素的下一个位置 iterator _end_of_storage; // 指向空间结束的下一个位置 public: // 默认成员函数 vector(); // 无参构造函数 template<class InputIterator> vector(InputIterator first, InputIterator last); // 使用迭代器初始化构造 vector(const vector<T>& v); // 拷贝构造（深拷贝） void swap(vector<T>& v) // 交换两个容器的内容 vector<T>& operator=(vector<T> v) // 赋值运算符重载（深拷贝） ~vector(); // 容量操作 size_t size() const { return _finish - _start; } // 有效元素个数 size_t capacity() const { return _end_of_storage - _start; } // 容量大小 bool empty() const { return size(); } // 判空 void reserve(size_t n); // 调整容器的容量大小（capacity） void resize(size_t n, const T& val = T()); // 调整容器的有效元素大小（size） // 访问操作，[]运算符重载 T& operator[](const size_t pos); T& operator[](const size_t pos) const; // 修改操作 iterator insert(iterator pos, const T& val = T()); // 在pos迭代器位置前插入元素 iterator erase(iterator pos); // 删除pos迭代器位置的元素 void push_back(const T& x); // 尾插 void pop_back(); // 尾删 }; }
（2）成员函数的实现
① 默认成员函数
a. 构造函数
// 无参构造 vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} // 使用迭代器进行初始化构造 [first,last) // 注意：若使用vector的iterator做形参，会导致初始化的迭代器区间[first,last)只能是vector的迭代器 template<class InputIterator> vector(InputIterator first, InputIterator last) // [first,last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); first++; } }
类模板的成员函数模板，可以自己定义模板参数，比如：这样写的好处是可以传其它容器的迭代器（string、list ...），而不是仅限于用 vector 自己的迭代器 iterator，只要解引用后数据的类型能够和 vector 数据的类型匹配。
b. 拷贝构造函数（传统写法）
// 拷贝构造（深拷贝）的2种传统写法 // 写法1 // v2(v1) vector(const vector<T>& v) :_start(new T[v.capacity()]) , _finish(_start + v.size()) , _end_of_storage(_start + v.capacity()) { memcpy(_start, v._start, sizeof(T) * v.size()); // 拷贝元素 } // 写法2(推荐) // v2(v1) vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(v.capacity()); // 调整新容器容量大小(一次性把空间开好，效率高) for (const auto& e : v) // 尾插元素到新容器中(复用push_back函数) push_back(e); }
c. 赋值运算符重载函数（传统写法）
// 赋值运算符重载(深拷贝)的传统写法 // v2 = v1 vector<T>& operator=(const vector<T>& v) { if (this != &v) // 防止自己给自己赋值 { // 释放原空间 delete[] _start; _start = _finish = _end_of_storage = nullptr; // 插入元素 reserve(v.capacity()); // 调整容量大小 for (const auto& e : v) push_back(e); _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } return *this; }
d. 交换两个容器的内容：方便实现拷贝构造和赋值重载（现代写法）
// 交换两个容器的内容 // v1.swap(v2) void swap(vector<T>& v) { // 函数名冲突，指定去调用全局域里面的std::swap std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }
e. 拷贝构造函数（现代写法）
// 拷贝构造(深拷贝)的现代写法 // v2(v1) vector(const vector<T>& v) :_start(nullptr) // 当前对象是一个正在构造的对象，成员变量还未初始化，是一个随机值，所以先置空 , _finish(nullptr) , _end_of_storage(nullptr) { vector<T> tmp(v.begin(), v.end()); // 拿v的内容，调用构造函数构造一个临时对象tmp this->swap(tmp); // 将临时对象tmp和当前对象的成员变量分别进行交换 }
f. 赋值运算符重载函数（现代写法）
赋值重载一般都是推荐现代写法。
// 赋值运算符重载(深拷贝)的现代写法(推荐) // v2 = v1 vector<T>& operator=(vector<T> v) // 通过传值传参，拷贝构造出临时对象 { this->swap(v); // 交换临时对象和当前对象的内容 return *this; // 返回当前对象 }
g. 析构函数
~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }
② 容量操作
a. size、capacity、empty 函数
size_t size() const // 有效元素个数 { return _finish - _start; } size_t capacity() const // 容量大小 { return _end_of_storage - _start; } bool empty() const // 判空 { return size(); }
b. reserve 函数
// 调整容器的容量大小（capacity） void reserve(size_t n) { if (n > capacity()) // 如果n大于当前capacity大小 { size_t oldSize = size(); // 提前保存下旧空间size大小，便于后面更新_finish T* tmp = new T[n]; // 开辟并初始化新空间，n个T类型的对象 if (_start) { // void* memcpy (void * destination, const void * source, size_t num); memcpy(tmp, _start, sizeof(T) * oldSize); // 旧空间元素拷贝到新空间（浅拷贝） delete[] _start; // 释放旧空间 } _start = tmp; // 指向新空间 _finish = _start + oldSize; // 更新有效元素长度 _end_of_storage = _start + n; // 更新容量 } }
注意：reserve 函数内部使用 memcpy 函数对数据进行字节序拷贝，实际上是有问题的。
// 使用 memcpy 浅拷贝的问题 void test() { vector<string> v; v.reserve(4); // 调整vector的容量为4 v.push_back("111"); v.push_back("222"); v.push_back("333"); v.push_back("444"); v.push_back("555"); // 这里会发生扩容，调用reserve函数 for (auto& e : v) cout << e << endl; }
运行结果：
程序崩溃。
问题分析：
- memcpy 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
- 如果拷贝的是内置类型的元素，memcpy 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为 memcpy 的拷贝实际是浅拷贝。
- 开空间，插入 4 个 string 类对象。
- 插入第 5 个 string 类对象，引发扩容，调用 reserve 函数，使用 memcpy 按字节序拷贝元素到新空间中，是浅拷贝，导致两个对象共享同一份资源。
- 程序结束时，已被析构的空间再次被析构，导致程序崩溃。
解决 memcpy 浅拷贝的问题：
- 容器中存的是内置类型元素，直接赋值即可。
- 容器中存的是自定义类型元素，通过调用该自定义类型的赋值运算符重载数 operator= 完成深拷贝。
修改后的 reserve 函数如下：
// 调整容器的容量大小(capacity) void reserve(size_t n) { if (n > capacity()) // 如果n大于当前 capacity 大小 { size_t oldSize = size(); // 提前保存下旧空间size大小，便于后面更新_finish T* tmp = new T[n]; // 开辟并初始化新空间，n个T类型的对象 if (_start) { // 如果T是int，直接赋值即可 // 如果T是string，就调用string类的赋值重载(进行深拷贝) // 如果T是vector，就调用vector类的赋值重载(进行深拷贝) for (size_t i = 0; i < oldSize; i++) // 旧空间元素赋值到新空间 tmp[i] = _start[i]; // 赋值 delete[] _start; // 释放旧空间 } _start = tmp; // 指向新空间 _finish = _start + oldSize; // 更新有效元素长度 _end_of_storage = _start + n; // 更新容量 } }
结论：如果对象中涉及到资源管理时，千万不能使用 memcpy 进行对象之间的拷贝，因为 memcpy 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
c. resize 函数
// 调整容器的有效元素大小（size） void resize(size_t n, const T& val = T()) { // 如果n小于当前size，则有效元素个数缩小到n if (n < size()) { _finish = _start + n; } // 如果n大于当前size else if (n > size()) { // 如果n大于当前capacity，先进行增容 if (n > capacity()) reserve(n); // 多出的位置用val或者缺省值T()填充 while (_finish < _start + n) { *_finish = val; _finish++; // 有效元素长度+1 } } }
③ 访问操作
// []运算符重载(普通版本) T& operator[](const size_t pos) { assert(pos >= 0 && pos < size()); // 检查越界 return _start[pos]; } // []运算符重载(const版本) T& operator[](const size_t pos) const { assert(pos >= 0 && pos < size()); // 检查越界 return _start[pos]; }
④ 修改操作
a. insert 函数（注意迭代器失效问题）
iterator insert(iterator pos, const T& val = T()) { assert(pos >= _start && pos <= _finish); size_t len = pos - _start; // 记录下pos相对_start的长度 if (_finish == _end_of_storage) // 先检查是否需要扩容 { size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newcapacity); // 注意：扩容后，pos还指向旧空间，pos位置迭代器已失效，需要重置pos pos = _start + len; // 解决迭代器失效问题 } // 往后挪动元素 for (iterator end = _finish; end > pos; end--) { *end = *(end - 1); } *pos = val; // 在pos迭代器位置处插入元素 _finish++; // 有效元素长度+1 return pos; // 返回指向第一个新插入元素的迭代器 // pos是传值传参，形参改变不会影响实参，所以更需要返回pos }
b. erase 函数（注意迭代器失效问题）
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); // 往前挪动元素 for (iterator it = pos + 1; it < _finish; it++) { *(it - 1) = *it; } _finish--; // 有效元素长度-1 return pos; // 返回指向被删除元素下一个位置的迭代器 }
c. push_back 函数
void push_back(const T& x) { /* if (_finish == _end_of_storage) // 先检查是否需要增容 { size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reserve(newcapacity); } *_finish = x; // 尾插元素 _finish++; */ insert(_finish, x); }
d. pop_back 函数
void pop_back() { /* assert(!empty()); _finish--; */ erase(--end()); }
4、动态二维数组理解
class Solution { public: vector<vector<int>> generate(int n) { // 开辟和初始化杨辉三角存储空间 vector<vector<int>> vv(n); for (size_t i = 0; i < vv.size(); i++) { vv[i].resize(i + 1, 0); // 每一行第一个元素和最后一个元素初始化为1 vv[i][0] = 1; vv[i][vv[i].size() - 1] = 1; } // 填充杨辉三角 for (size_t i = 2; i < vv.size(); i++) // 从第3行开始 for (size_t j = 1; j < vv[i].size() - 1; j++) // 从第2列开始 vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j]; return vv; } };
xyl::vector> vv(n); 构造一个 vv 动态二维数组，vv 中总共有 n 个元素，每个元素都是 vector 类型的，每行没有包含任何元素
如果 n = 5 时如下所示：
vv 中元素填充完成之后，如下图所示：
使用标准库中 vector 构建动态二维数组时与上图实际是一致的。
