vector使用及模拟
01.vector使用
1.1 vector介绍
- 可变数组容器：
vector是动态数组，支持随机访问，大小可自动扩展 - 连续存储：与数组一样使用连续内存，下标访问高效，但支持动态扩容
- 动态扩容机制：插入新元素时可能重新分配更大的数组，将原元素迁移至新数组，避免频繁扩容
- 空间分配策略：分配额外空间应对增长，扩容间隔按对数增长，确保尾部插入操作的时间复杂度为 O (1)
- 空间换时间：通过预分配冗余空间减少扩容次数，以额外内存开销换取高效动态增长
- 性能特性：随机访问效率极高，尾部插入 / 删除高效，中间操作效率较低；迭代器和引用稳定性优于
list
1.2 构造函数
| 接口说明 | 构造函数 |
|---|---|
| 默认构造 | vector<T> v; |
| 构造并初始化n个值val的容器 | vector<T>（size_t n, const T& val = T()） |
| 迭代器范围构造 | vector<T> v(iterator first, iterator last); |
| 拷贝构造 | vector<T> v(other_vector); |
| 从数组构造 | vector<T> v(arr, arr + size); |
// 无参构造即默认构造函数vector<int> v1;// 填充构造vector<int> v2(5); //[0,0,0,0,0]vector<int> v3(6, 1); //[1,1,1,1,1,1]// 将[ ， )范围内元素初始化为vectorint arr[3] = {1, 2, 3};vector<int> v4(arr, arr + 2);vector<int> v5(v3.begin(), v3.end());// 拷贝构造vector<int> v6(v3);
1.3 vector迭代器
在string和vector中迭代器使用频率不是很高(可以使用数组下标访问)，但在容器中使用迭代器遍历数据很实用。用来获取第一个或最后一个位置的iterator/const_iterator。反向迭代用法一样，不过是方向相反。
1.3.1 范围for
范围for用于遍历容器或数组的简化遍历方式。
语法：
for(变量声明 : 容器/数组 ){...}
int main(){ vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(7);//正向迭代器vector<int>::iterator it = v1.begin();while (it!=v1.end()){cout << *(it++) << " ";}cout << endl;for(auto i:v1){//范围forcout << i << " ";}cout << endl; //反向迭代器vector<int>::reverse_iterator rit = v1.rbegin();while(rit!=v1.rend()){cout << *(rit++) << " ";}cout << endl;system("pause");return 0;
}
1.4 空间操作函数
| 接口 | 功能说明 |
|---|---|
| size() | 获取 vector 中实际存储的元素个数 |
| capacity() | 获取vector 分配的总空间容量（capacity），capacity >= size） |
| empty() | 判断vector 是否为空 |
| resize() （重点） | 改变vector中size并且设置内容 |
| reserve() （重点） | 改变vector中的capacity(空间容量)大小**(扩容)** |
- capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size。
int main(){vector<int> v1;for(size_t i=1;i<=6){v1.push_back(i);}cout << "size:" << v1.size() << endl;cout << "capacity:" << v1.capacity() << endl;if (!v1.empty()){ // 为空返回truecout << "v1 is not empty" << endl;}// resize中值比size小时v1.resize(3);for (auto i : v1){cout << i << " "; //[1 2 3]}cout << endl;// resize中值比size大时v1.resize(9);for (auto j : v1){cout << j << " "; //[1 2 3 0 0 0 0 0 0],resize会改变vector中的内容}cout << endl;// reserve扩容cout << "Capacity before expansion: " << v1.capacity() << endl;v1.reserve(11);cout << "Capacity after expansion: " << v1.capacity() << endl;system("pause");return 0;
}
1.5 vector增删查改
说明
| 接口 | 功能说明 |
|---|---|
| push_back() （重点） | 尾插 |
| pop_back() （重点） | 删除尾部元素，size 减 1。 不释放内存（capacity 不变）。 |
| find() | 查找元素val，需引用算法接口 |
| insert() | 在pos位置之前插入数据val(也可以插入n个数据) |
| erase() | 删除pos位置的数据(或一段迭代器区间的数据) |
| swap() | 交换两个 vector 的内容（包括 size 和 capacity） |
| operator[] （重点） | 下标访问 |
int main(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for(auto i:v1){cout << i << " ";}cout << endl;//尾删2个元素v1.pop_back();v1.pop_back();for(auto j:v1){cout << j << " ";}cout << endl;auto f1 = find(v1.begin(), v1.end(),3);if(f1!=v1.end()){v1.erase(f1);}//erase删除一段迭代器区间的数据auto f3 = find(v1.begin(), v1.end(), 3);auto f4 = find(v1.begin(), v1.end(), 5);v1.erase(f3, f4);for (auto i : v1){cout << i << " ";}cout << endl;//swap交换vector<int> v(5, 1);v1.swap(v);//下标访问for (int i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;system("pause");return 0;
}
02. vector模拟实现
与顺序表不成员变量有所区别，在vector中使用start，finish，end_of_storage迭代器作为成员变量。
内存布局：[X X X X X _ _ _ _ _]↑ ↑ ↑_start _finish _end_of_storage- _start：指向第一个元素 'X'
- _finish：指向第6个位置（未使用）
- _end_of_storage：指向第11个位置（内存边界）
reserve(n)会调整_end_of_storage，确保至少能容纳n个元素，而不改变_finish。
2.1 无参构造
无参构造，就是默认构造函数，将成员变量都初始化成nullptr。
Vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}
2.2 构造并初始化n个val值
Vector(size_t n, const T &val = T()){_start = new T[n];for (size_t i = 0; i < n; i++){_start[i] = val;}_end_of_storage = _finish = _start + n;}
2.3 范围构造
使用迭代器区间进行初始化，这里不一定是vector的迭代器，所以写成模板。
template<class InputIterator>vector(InputIterator first, InputIterator last){size_t sz = last - first;start = new T[sz];finish = start;while (first != last){*finish = *first;++finish;++first;}end_of_storage = start + sz;}
2.4 拷贝构造
深拷贝
Vector(const T &v): _start(new T[v.size()]), _finish(_start + v.size()), _end_of_storage(_start + v.capacity()){if (_start){memcpy(_start, v._start, sizeof(T) * v.size());}}
2.5 析构函数
释放动态开辟的空间
~Vector(){if (_start){delete[] _start;}_start = _finish = _end_of_storage = nullptr;}
2.6 赋值运算符重载
深拷贝
Vector<T> &operator=(const Vector &v){ // v1=v2;if (_start){delete[] _start;}_start = new T[v.size()];for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.size();}/* vector<T>& operator=(vector v){swap(v);return *this;}*/
2.7 迭代器
//迭代器iteratortypedef 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; }
2.8 容量操作函数
size_t size() const{return _finish - _start;}size_t capacity() const{_end_of_storage - _start;}bool empty() const{return _start == _finish;}
2.9 扩容
void reserve(size_t n){if (n > capacity()){// 提前算好，防止后面指针变化指向两段空间size_t sz = size();T *tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}
2.10 push_back()
void push_back(const T& val ){if (_finish==_end_of_storage){size_t newcapcity = (capacity() == 0) ? 2 : 2 * capacity();reserve(newcapcity);}*_finish = val;++_finish;// == insert(_finish, val);}
2.11 pop_back()
void pop_back(){assert(_start != _finish);--_finish;}
2.12 insert()
扩容之后还有一个迭代器失效问题，即开辟了新空间，但是迭代器指针扔指向旧空间，需要重新给pos赋值。
void insert(T* pos,const T&val){size_t sz = pos - begin();if (_finish==_end_of_storage){size_t newcapcity = (capacity() == 0) ? 2 : 2 * capacity();reserve(newcapcity);pos = _start + sz;}//诺数据T *end = _finish;while(end!=pos){*end = *(end - 1);--end;}*pos = val;_finish++; }
2.13 erase()
T* erase(iterator pos){size_t sz = _finish - pos;for (int i = 0; i < sz; i++) {pos[i] = pos[i + 1];}_finish -= 1;return pos;}
#include <iostream>
#include <algorithm>
#include <cassert>using namespace std;
template <class T>
class Vector
{typedef T *iterator;public:Vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}Vector(size_t n, const T &val = T()){_start = new T[n];for (size_t i = 0; i < n; i++){_start[i] = val;}_end_of_storage = _finish = _start + n;}T &operator[](int n){return _start[n];}// 拷贝构造Vector(const T &v): _start(new T[v.size()]), _finish(_start + v.size()), _end_of_storage(_start + v.capacity()){if (_start){memcpy(_start, v._start, sizeof(T) * v.size());}}/*template<class InputIterator>Vector(InputIterator first, InputIterator last){size_t sz = last - first;_start = new T[sz];_finish = _start;while (first != last){*_finish = *first;++_finish;++first;}_end_of_storage = _start + sz;}*/T &operator[](size_t i){return this->_start[i];}Vector<T> &operator=(const Vector &v){ // v1=v2;if (_start){delete[] _start;}_start = new T[v.size()];for (size_t i = 0; i < v.size(); i++){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.size();}void reserve(size_t n){if (n > capacity()){// 提前算好，防止后面指针变化指向两段空间size_t sz = size();T *tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}iterator &begin(){return _start;}iterator &end(){return _finish;}void push_back(const T &val){if (_finish == _end_of_storage){size_t newcapcity = (capacity() == 0) ? 2 : 2 * capacity();reserve(newcapcity);}*_finish = val;++_finish;// == insert(_finish, val);}void pop_back(){assert(_start != _finish);--_finish;}void insert(T *pos, const T &val){size_t sz = pos - begin();if (_finish == _end_of_storage){size_t newcapcity = (capacity() == 0) ? 2 : 2 * capacity();reserve(newcapcity);pos = _start + sz;}// 诺数据T *end = _finish;while (end != pos){*end = *(end - 1);--end;}*pos = val;_finish++;}T* erase(iterator pos){size_t sz = _finish - pos;for (int i = 0; i < sz; i++){pos[i] = pos[i + 1];}_finish -= 1;return pos;}void swap(Vector<T> &v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish = _start;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}bool empty() const{return _start == _finish;}~Vector(){if (_start){delete[] _start;}_start = _finish = _end_of_storage = nullptr;}private:T *_start;iterator _finish;iterator _end_of_storage;
};int main()
{Vector<int> v1(5, 2); //[2 2 2 2 2]cout << v1[0] << endl;cout << v1.size() << "--" << v1.capacity() << endl;Vector<int> v2(v1);cout << "copy constructor-->";for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << " ";}cout << endl;cout << "v4: ";Vector<int> v4 = v1;for (size_t i = 0; i < v2.size(); i++){cout << v4[i] << " ";}cout << endl;cout << "v5: ";Vector<int> v5;cout << v5.capacity() << endl;v5.push_back(1);v5.push_back(1);v5.push_back(1);v5.push_back(1);cout << v5.capacity() << endl;for (size_t i = 0; i < v5.size(); i++){cout << v5[i] << " ";}cout << endl;cout << ":pop--> ";v5.pop_back();for (size_t i = 0; i < v5.size(); i++){cout << v5[i] << " ";}cout << endl;cout << ":insert--> ";v5.insert(v5.begin() + 2, 3);for (size_t i = 0; i < v5.size(); i++){cout << v5[i] << " ";}cout << endl;system("pause");return 0;
}