【浅尝C++】STL第二弹=＞迭代器失效详解/vector常用接口使用示例/vector底层结构探索/vector模拟实现代码详解

🏠专栏介绍：浅尝C++专栏是用于记录C++语法基础、STL及内存剖析等。
🎯每日格言：每日努力一点点，技术变化看得见。

---

vector介绍

vector就是一个可以自动扩大容量的数组，它与顺序表具有相同的性质，如适合随机访问、尾部插入删除效率高。关于顺序表的特点，可以查阅该篇文章→数据结构线性表（含顺序表及链表）介绍

下面给出6条关于vector的概括性介绍：

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

vector常用接口及使用示例

构造类函数

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

下面给出vector各种构造类函数的使用示例↓↓↓

#include <iostream>
#include <vector>
using namespace std;void testVector()
{//无参构造vector<int> vc1;//5个'c'构造vectorvector<char> vc2(5, 'c');for(auto ch : vc2){cout << ch << " "; }cout << endl;//使用vc2构造vc3vector<char> vc3(vc2);for(auto ch : vc3){cout << ch << " "; }cout << endl;//使用容器的起始与终止迭代器构造vectorstring s = "Jammingpro";vector<char>vc4(s.begin(), s.end());for(auto ch : vc4){cout << ch << " "; }cout << endl;
}int main()
{testVector();return 0;
}

迭代器的使用

迭代器	接口说明
begin + end	begin获取第一个数据的位置，end获取最后一个数据的下一个位置
rbegin + rend	rbegin获取最后一个数据的位置，rend获取第一个数据的前一个位置

如上图所示，begin指向第一个元素的位置，end指向向最后一个元素的下一个位置。下面给出begin和end这俩迭代器的使用示例

#include <iostream>
#include <vector>
using namespace std;void testVector()
{vector<int> vc = {1,2,3,4,5,6,7,8};vector<int>::iterator it = vc.begin();while(it != vc.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{testVector();return 0;
}

这里可以先将迭代器先理解为数组指针，it指向数组的首地址，++it就可以将指针指向下一个元素的首地址。下文将对vector的迭代器进行模拟实现。

对于反向迭代器来说，rbegin指向最后一个元素，rend指向首元素的前一个位置。其他操作与正向迭代器begin与end没有区别。对反向迭代器进行++操作，等同于对指针-1操作。也就说，反向迭代器初始化为rbegin后，每执行一次++操作，迭代器就会向前移动一个位置，而不是向后移动。

#include <iostream>
#include <vector>
using namespace std;void testVector()
{vector<int> vc = {1,2,3,4,5,6,7,8};vector<int>::reverse_iterator it = vc.rbegin();while(it != vc.rend()){cout << *it << " ";++it;}cout << endl;
}int main()
{testVector();return 0;
}

普通迭代器的类型为iterator、反向迭代器的类型为reverse_iterator，除了这两种迭代器，还有const_iterator和const_reverse_iterator，这两个迭代器用于对const类型的容器进行正反向遍历，它们不能对容器内的数据进行修改，而非const迭代器可以修改容器内的数据。↓↓↓

#include <iostream>
#include <vector>
using namespace std;void testConstVector(const vector<int> vc)
{vector<int> vc = {1,2,3,4,5,6};vector<int>::const_iterator it = vc.begin();while(it != vc.end()){*it += 1;//error!!++it;}
}void testVector()
{vector<int> vc = {1,2,3,4,5,6};vector<int>::iterator it = vc.begin();while(it != vc.end()){*it += 1;//ok!!++it;}for(auto e : vc){cout << *it << " ";}cout << endl;
}int main()
{testVector();return 0;
}

容量操作

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

vector的capacity（容量）一般都会size（有效数据个数）要大。因为vector的底层是包含连续空间的顺序表，扩容时可能需要大量移动数据，扩容效率较低。因而，vector会在扩容时，按照1.5倍或2倍扩容。

下面代码用于验证vs下与g++下vector的扩容规律↓↓↓

#include <iostream>
#include <vector>
using namespace std;void testVector()
{vector<int> vc;int sz = vc.capacity();//获取初始容量for(int i = 0; i < 100; i++){vc.push_back(i);if(sz != vc.capacity()){sz = vc.capacity();cout << "vector capacity change to : " << sz << endl;}}
}int main()
{testVector();return 0;
}

vs下执行结果如下图所示，说明vs按照1.5倍左右进行扩容。

而g++下执行结果入下图所示，说明g++按照2倍左右进行扩容。

empty用于判断vector容器中的有效数据数量是否为0；reserve用于提前给vector开辟空间，如果我们预先知道将要插入1000个数据，则我们可以预先开辟1000个空间，这样可以避免频繁扩容导致的效率损失。resize：当resize指定大小n小于有效数据个数时，则会将位于下标n及n后面的有效数据删除；当resize指定大小n大于有效数据个数时，则会在size到n-1的位置填充resize传入参数中指定的数据。

下面给出这3个函数的使用示例↓↓↓

#include <iostream>
#include <vector>
using namespace std;void testVector()
{vector<int> vc;if(vc.empty()){cout << "vc is empty" << endl;}cout << "vc's capacity is " << vc.capacity() << endl;vc.reserve(100);cout << "vc's capacity is " << vc.capacity() << endl;for(int i = 0; i < 100; i++){vc.push_back(i);}cout << "vc's size is " << vc.size() << endl;
}int main()
{testVector();return 0;
}

增删改查

接口声明	接口说明
push_back	尾插
pop_back	尾删
insert	在pos前插入val
erase	删除pos位置的数据
swap	交换两个vector的数据空间
operator[ ]	想数组一样使用[ ]进行访问

下面给出上面各个接口的使用示例↓↓↓

#include <iostream>
#include <vector>
using namespace std;void testVector()
{vector<int> vc;vc.push_back(1);vc.push_back(2);vc.push_back(3);vc.push_back(4);vc.push_back(5);cout << "after push back:";for(auto ch : vc){cout << ch << " ";}cout << endl;vc.pop_back();cout << "after pop back:";for(auto ch : vc){cout << ch << " ";}cout << endl;vc.insert(vc.begin(), 888);cout << "after insert:";for(auto ch : vc){cout << ch << " ";}cout << endl;vc.erase(vc.begin());cout << "after erase:";for(auto ch : vc){cout << ch << " ";}cout << endl;vector<int> vc2 = {666,777,888};cout << "before swap vc2 is:" ;for(auto ch : vc2){cout << ch << " ";}cout << endl;vc2.swap(vc);cout << "after swap:";for(auto ch : vc){cout << ch << " ";}cout << endl;vc2[2] = 999;cout << "after operator[]:";for(auto ch : vc2){cout << ch << " ";}cout << endl;
}int main()
{testVector();return 0;
}

迭代器失效详解与vector底层结构探索

我们可以通过vs的监视窗口查看到，vector底层总共3个指针，_first指向堆区开辟空间的首地址，_last指向最后一个有效元素的下一位置，_end指向指向容量的下一位置。

而迭代器底层是什么呢？由下图可以看到，vector迭代器底层是一个指向堆区空间的指针。

如果我们在vector扩容器，执行vector<int>::iteartor it = vc.begin()则可以获得vc的_first指针内容，及it的指针指向0x00000000。如果此时插入数据后，vc发生扩容，将旧空间数据拷贝到新空间，并将旧空间释放，新的_first指针内容变为0x00FCA580，而此时it中的指针仍然指向旧空间，如果此时对it进行解引用操作，就会发生非法访问的错误。（下图演示了该文字表述的内容）

vector模拟实现

我们参照SGI版本的STL命名方式，它的_start指向指向开辟的空间首地址，_final指向最后一个后效数据的下一位置，_end_of_storage指向开辟空间最后一个位置的下一位置。

下面给出即将模拟实现的vector类的框架（含默认构造及析构函数）↓↓↓

template<class T>
class vector
{
public:vector(){}~vector(){if(_start){delete[] _start;_start = _final = _end_of_storage = nullptr;}}
private:T* _start = nullptr;T* _final = nullptr;T* _end_of_storage = nullptr;
};

构造类函数

编译器自动生成的默认构造函数与拷贝赋值都是对_first、_final、_end_of_storage进行值拷贝。如下图所示。若使用vc来构造vc2，则会使得vc和vc2的成员变量保存同一份地址，当vc析构释放_first指向的空间后，vc2再析构时也会重复释放该空间，导致出错。

因此，我们需要重写拷贝构造与拷贝赋值函数

vector(const vector<T>& vc)
{_final = vc._size;_end_of_storage = vc._end_of_storage;_start = new T[_end_of_storage];memcpy(_start, vc._start, sizeof(T) * vc.size());
}vector<T>& operator=(const vector<T> vc)
{if (this != &vc){T* tmp = new T[vc._end_of_storage];memcpy(tmp, vc._start, sizeof(T) * vc._size);if (_start) delete[] _start;_start = tmp;_final = _start + vc.size();_end_of_storage = _start + vc.capacity();}
}

属性获取类函数

下面实现的empty、size、capacity、operator[]函数↓↓↓

bool empty() const
{return _start == _final;
}
size_t size() const
{return _final - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
T& operator[](const size_t pos)
{assert(pos < size());return _start[pos];
}

扩容与容量重置函数

void reserve(const size_t& n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * sz);if (_start) delete[] _start;_start = tmp;_final = _start + sz;_end_of_storage = _start + n;}
}void resize(const size_t& sz, const T& val = T())
{if (sz <= size()){_final = _start + sz;}else{if (sz > capacity()){reserve(sz);}for (int i = size(); i < sz; i++){_start[i] = val;}_final = _start + sz;}
}

插入与删除函数

void push_back(const T& val)
{if (size() == capacity()){int newsize = capacity() == 0 ? 10 : 2 * capacity();reserve(newsize);}_start[size()] = val;_final++;
}
void pop_back()
{assert(!empty());_final--;
}
void insert(T* pos, const T& val)
{if (size() == capacity()){int newsize = capacity() == 0 ? 10 : 2 * capacity();reserve(newsize);}T* it = _final;while (it > pos){*it = *(it - 1);--it;}*pos = val;_final++;
}
void erase(T* pos)
{assert(!empty());T* it = pos;while (it < _final){*it = *(it + 1);++it;}--_final;
}

vector模拟实现代码汇总（含正向迭代器）

★ps：insert可能会引起vector产生扩容，导致迭代器失效，SGI版本STL中将需要新的迭代器返回。下面代码中insert与erase与SGI版本返回值保持一致。

namespace jammingpro
{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public:iterator begin(){return _start;}iterator end(){return _final;}const_iterator begin() const{return _start;}const_iterator end() const{return _final;}vector(){}vector(const vector<T>& vc){_final = vc._size;_end_of_storage = vc._end_of_storage;_start = new T[_end_of_storage];memcpy(_start, vc._start, sizeof(T) * vc.size());}vector<T>& operator=(const vector<T> vc){if (this != &vc){T* tmp = new T[vc._end_of_storage];memcpy(tmp, vc._start, sizeof(T) * vc._size);if (_start) delete[] _start;_start = tmp;_final = _start + vc.size();_end_of_storage = _start + vc.capacity();}}~vector(){if (_start){delete[] _start;_start = _final = _end_of_storage = nullptr;}}bool empty() const{return _start == _final;}size_t size() const{return _final - _start;}size_t capacity() const{return _end_of_storage - _start;}T& operator[](const size_t pos){assert(pos < size());return _start[pos];}void reserve(const size_t& n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * sz);if (_start) delete[] _start;_start = tmp;_final = _start + sz;_end_of_storage = _start + n;}}void resize(const size_t& sz, const T& val = T()){if (sz <= size()){_final = _start + sz;}else{if (sz > capacity()){reserve(sz);}for (int i = size(); i < sz; i++){_start[i] = val;}_final = _start + sz;}}void push_back(const T& val){if (size() == capacity()){int newsize = capacity() == 0 ? 10 : 2 * capacity();reserve(newsize);}_start[size()] = val;_final++;}void pop_back(){assert(!empty());_final--;}iterator insert(T* pos, const T& val){int sz = pos - _start;if (size() == capacity()){int newsize = capacity() == 0 ? 10 : 2 * capacity();reserve(newsize);}T* it = _final;while (it > pos){*it = *(it - 1);--it;}*(_start + sz) = val;_final++;return _start + sz;}iterator erase(T* pos){assert(!empty());T* it = pos;while (it < _final){*it = *(it + 1);++it;}--_final;return pos;}private:T* _start = nullptr;T* _final = nullptr;T* _end_of_storage = nullptr;};
}

vector实现二维数组

如果想使用vector二维数组可以定义如下代码：

void test()
{vector<vector<int>>vc(5, vector<int>(6, 0));
}

上面的代码相当于创建了一个包含5个vector的vector容器

🎈欢迎进入浅尝C++专栏，查看更多文章。
如果上述内容有任何问题，欢迎在下方留言区指正b(￣▽￣)d