【C++详解】——vector类

📖 前言：本期介绍vector类。

---

🕒 1. vector的介绍

1. vector是表示可变大小数组的序列容器（可以理解为顺序表）。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习。

🕒 2. vector的使用

🔎 vector文档介绍
对于vector内部的成员函数，基本上和string相同，因此本文章在模拟实现之前只介绍大多使用函数的函数名以及功能，具体细节会在模拟实现中解释。

🕘 2.1 定义

构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x)（重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

🕘 2.2 iterator

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

这里会出现迭代器失效问题，如图我们发现迭代器可以看成指向某一数据的指针（实际上不一定是指针），但如果出现了扩容的情况（统一看成异地扩容）那么这个迭代器指向的位置就不再是我们想要进行操作的位置，这就是典型的迭代器失效问题，也就是野指针问题。具体介绍将会在下面的模拟实现中进行解释。

🕘 2.3 空间增长

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity

• capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
• reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题（即可以直接将扩容一次性到位）。如果比当前容量小时，不缩容，因为缩容有代价，以空间换时间。
• resize在开空间的同时还会进行初始化，影响size。

// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;v.reserve(100);sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

🕘 2.4 增删查改

增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
find	查找（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问

🕒 2. vector的模拟实现

首先定义一个vector类：

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}private: iterator _start; // 0iterator _finish; // sizeiterator _endofstorage; // capacity
};

🕘 2.1 构造函数

🕤 2.1.1 无参构造

vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}

🕤 2.1.2 拷贝构造

对于拷贝构造有两种写法：

• 传统写法：开空间、赋值
• 现代写法：通过迭代器的初始化构造

//传统写法 v2(v1)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());for (const auto& e : v) // 必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造{push_back(e);}}// 现代写法
template <class InputIterator>
vector(InputIterator first, InputIterator last) // 迭代器初始化:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);++first;}
}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{vector<T> tmp(v.begin(), v.end());swap(tmp); // this和tmp进行swap
}

🕤 2.1.3 构造并初始化n个val

vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for(size_t i = 0; i < n; i++){push_back(val);}
}

在测试的时候仅仅这样是会出错的，调试也印证了重载函数不会走上面函数，而是会走迭代器。原因为n是size_t而不是int类型，调用此函数就会发生隐式类型转换，编译器觉得不合适，便寻找更好的选择，于是找到了迭代器。解决方案就是再重载一个函数：vector(int n, const T& val = T())。为什么不直接将上一个函数的size_t改成int类型呢？因为我们是在模拟实现库中的vector。

🕘 2.2 iterator

iterator begin()
{return _start;
}iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

🕘 2.3 空间增长

size_t size() const 
{return _finish - _start;
}size_t capacity() const
{return _endofstorage - _start;
}
bool empty() const
{return _finish == _start;
}void resize(size_t n, T val = T())//这里的val是缺省
{if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}
}void reserve(size_t n) // 注意迭代器失效问题
{if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}
}

上面的reserve提到了迭代器失效问题，代码中已解决，即oldSize记录了size()的大小。那如果不记录size()的大小，那么_finish = tmp + size()中的size()由于之前的空间被销毁，也会被置为0,，此时的_finish就与_start就相同。

🕘 2.4 增删查改

这里需要注意迭代器失效问题，迭代器失效与扩容机制息息相关，而增删查改会频繁的调用扩容机制。

首先介绍不涉及迭代器失效的问题的成员函数：

void push_back(const T& x)
{if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}
void pop_back()
{assert(!empty());--_finish;
}

下面看看需要考虑迭代器失效问题的成员函数

🕤 2.4.1 insert

// 迭代器失效问题：异地扩容导致的野指针问题
iterator insert(iterator pos, const T& val) // 不传引用是因为有左值的影响：常量，即v.begin()
{assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start; // 处理失效问题，记录相对位置size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//扩容导致pos迭代器失效，需要更新处理一下pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;++_finish;return pos;
}

对于前插，是一定要考虑扩容问题的，而我们实现的方式也只有异地扩容，因此当我们触发了扩容机制后，就会引起迭代器失效的问题：

为了处理这个迭代器失效的问题，我们提前记录pos与_start的相对位置，即通过len = pos - _start记录，最后更新pos = _start + len，就可以解决这里迭代器失效的问题。

虽然函数内部的迭代器失效问题解决了，但我们知道，在这个函数中的pos只是外部pos的一份临时拷贝，改变这里的pos外部的pos并不会改变，因此外部的pos也会由于异地扩容之后导致野指针，那么我们可以采用返回值更新pos。

🕤 2.4.2 erase

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin-1) = *begin;++begin;}--_finish;return pos;
}

🕤 2.4.3 swap

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

🕘 2.5 其他

~vector()//析构
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}// v1 = v2
// v1 = v1;  // 极少数情况，能保证正确性，所以这里就这样写没什么问题vector<T>& operator=(vector<T> v) // 由于直接swap，因此不能传引用
{swap(v);return *this;
}
void clear()
{_finish = _start; // 不能置空，会发现内存泄漏
}

🕒 3. 深拷贝问题

🕘 3.1 vector<vector< int >>

我们用上面模拟实现的代码进行观察

void test_vectorarray()
{vector<vector<int>> vv;vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;}cout << endl;
}

可以看到，插入四行是没问题的，那再插入一行（加上一个vv.push_back(v);）会怎么样呢

很明显，扩容出了问题，根据经验，大概率是异地扩容后出现了浅拷贝问题，即我们异地扩容产生的变量的指向仍然是之前指向的位置，并且由于异地扩容之后，会delete[]原空间，这就导致异地扩容的指向也变成了野指针。

当我们到了第五个push_back，也就是需要扩容的时候，我们发现：tmp与原本_start的位置指向的是同一个位置（注意外部的_start与内部的第一个_start指向的位置是一样的），这是由于memcpy引起的，而我们知道，memcpy所引起的异地扩容会释放旧空间，即释放旧位置所指向的位置，但这一释放，就导致了新开辟的tmp内部的指针变量指向的空间也被释放了。

既然浅拷贝的memcpy不行，那我们就可以通过赋值的方式在拷贝中开辟新空间，进行深拷贝：

void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*oldSize);for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}}

即将reserve中的memcpy换成如图所示的方式，这样赋值拷贝会开辟新空间（上面的代码中就是开辟了新空间），我们就可以避免浅拷贝的问题。

因此我们也需要注意： 在C++中要避免使用C语言中的函数：memcpy、realloc、malloc等

🕘 3.2 vector< string >

事实上，string与vector<int>的道理是相同的，如果我们仍然用memcpy，会发现在需要扩容的过程中仍然出现浅拷贝造成的错误，用赋值就没有问题。由此可以理解，自定义类型的情况下都会发生这种扩容出现的问题，而内置类型并不会发生。

void test_vectorstring()
{vector<string> v;v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111"); // 扩容for (size_t i = 0; i < v.size(); i++){for (size_t j = 0; j < v[i].size(); j++){cout << v[i][j] << " ";}cout << endl;}cout << endl;
}

🕒 4. 模拟实现vector汇总

//myvector.h
#pragma oncenamespace myvector
{template<class T>class vector{public: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;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//传统写法 v2(v1)//vector(const vector<T>& v)//	:_start(nullptr)//	, _finish(nullptr)//	, _endofstorage(nullptr)//{//	reserve(v.capacity());//	for (const auto& e : v) // 必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造//	{//		push_back(e);//	}//}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}// 现代写法template <class InputIterator>vector(InputIterator first, InputIterator last) // 迭代器初始化:_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp); // this和tmp进行swap}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}// v1 = v2// v1 = v1;  // 极少数情况，能保证正确性，所以这里就这样写没什么问题vector<T>& operator=(vector<T> v){swap(v);return *this;}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*oldSize);for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}bool empty() const{return _finish == _start;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void push_back(const T& x){if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}// 迭代器失效问题：异地扩容导致的野指针问题iterator insert(iterator pos, const T& val) // 不传引用是因为有左值的影响：常量，即v.begin(){assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start;// 处理失效问题，记录相对位置size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);// 扩容会导致pos迭代器失效，需要更新处理一下pos = _start + len;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *(begin);++begin;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}void clear(){_finish = _start;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

---

OK，以上就是本期知识点“vector类”的知识啦~~ ，感谢友友们的阅读。后续还会继续更新，欢迎持续关注哟📌~
💫如果有错误❌，欢迎批评指正呀👀~让我们一起相互进步🚀
🎉如果觉得收获满满，可以点点赞👍支持一下哟~

❗ 转载请注明出处
作者：HinsCoder
博客链接：🔎 作者博客主页