🥁作者： 华丞臧
📕​​​​专栏：【C++】
各位读者老爷如果觉得博主写的不错，请诸位多多支持(点赞+收藏+关注)。如果有错误的地方，欢迎在评论区指出。

推荐一款刷题网站 👉LeetCode

---

---

一、vector的使用

C++中提供了vector容器，该容器是以连续的空间来存放数据，可以理解为封装过的数组，且这个数组是定义在堆上的。本章介绍一些vector的常用接口，更多的接口使用方法可以参考cplusplus网站。

1.1 常用构造

C++98中，vector提供了四个构造函数的接口，这些都是比较常用的，operate=也是非常常用的。
实例代码如下：

void Print(vector<int>& v)
{for (auto a : v){cout << a << " ";}cout << endl;
}
void test1()
{vector<int> v1; // 创建一个空对象vector<int> v2(5, 1); // 创建元素类型为int，元素个数为5的vector，并用1进行初始化vector<int> v3(v2.begin(), v2.end()); // 迭代器创建v3vector<int> v4(v3); // 拷贝构造vector<int> v5 = v4; // operate=Print(v1);Print(v2);Print(v3);Print(v4);Print(v5);
}

代码运行结果：

1.2 迭代器

迭代器无疑是vector容器较为重要的接口之一了，其中较为常用就是begin和end。有了迭代器后，我们就可以通过迭代器对容器中的数据进行访问读取修改等操作；迭代器隐藏了实现细节提供了统一的使用方式，同时迭代器还是范围for的底层实现。
实例代码如下：

void test2()
{vector<int> v1(10, 0);for (int i = 0; i < 10; i++)v1[i] = i;vector<int>::iterator it = v1.begin();// vector<int>::const_iterator it = v1.cbegin();while (it != v1.end()){cout << *it << " ";++it;}cout << endl;vector<int>::reverse_iterator it2 = v1.rbegin();// vector<int>::const_reverse_iterator it2 = v1.crbegin();while (it2 != v1.rend()){cout << *it2 << " ";++it2;}cout << endl;
}

从实例中可以看到，迭代器的使用方式与指针非常相似，但其实迭代器并不一定是指针。

1.3 容量

在vector容器提供的对容量操作的接口中，我们可以使用size查询当前vector容器中有效元素的个数，使用resize来增加有效元素的个数，使用capacity查看vector容器的容量大小，判断vector容器是否为空使用empty，reserve则是用来扩容的。
注意：resize不仅可以扩容，还可以缩容，但是不推荐，缩容会付出很大的代价。
实例代码如下：

void test3()
{vector<int> v;cout << "size: " << v.size() << endl;v.resize(10, 0);int i = 0;for (auto& e : v){cout << e << " ";e = i++;}cout << endl;cout << "size: " << v.size() << endl;v.reserve(100);cout << "capacity: " << v.capacity() << endl;if (v.empty()){cout << "empty" << endl;}else{cout << "nonempty" << endl;}v.resize(5);  // 可以缩容for (auto a : v){cout << a << " ";}cout << endl;cout << "size: " << v.size() << endl;
}

代码运行结果：

1.4 访问元素

• 对于vector来说，访问元素最好用的无疑是[]。在C++中，vector是一个容器，其底层是一段连续的空间类似数组；而[]的重载让vector可以像数组一样使用，只需要提供下标即可访问特定位置上的元素。at与[]类似，获取第n个位置上的元素。
• front用来获取vector首部元素，返回引用或const引用。
• back用来获取vector尾部元素，返回引用或const引用。

void test4()
{vector<int> v(10, 0);for (int i = 0; i < 10; i++)v[i] = i;cout << v[5] << endl;cout << "front: " << v.front() << endl;cout << "back: " << v.back() << endl;
}

代码运行结果如下：

1.5 修改元素

在官方库提供的修改元素的接口中，常见的接口有push_back、pop_back、insert、erase、swap、clear。不过因为vector实际是一段连续的空间，因此在指定位置插入删除效率极低，通常不会使用，当然还是得看实际需要使用。

二、vector模拟实现

2.1 vector接口

#include <iostream>
#include <assert.h>using namespace std;namespace zch
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;public:iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;public:vector(); template<class InputIterator>vector(InputIterator first, InputIterator last);vector(size_t n, const T& val);vector(long n, const T& val);vector(int n, const T& val);vector(const vector<T>& v);vector<T>& operator=(const vector<T>& v);void push_back(const T& val);void pop_back();iterator insert(iterator pos, const T& val);iterator erase(iterator pos);void reserve(int n);void resize(size_t n, const T& val = 0);size_t capacity() const;size_t size() const;bool empty() const;T& operator[](size_t i) const;~vector();void print();private: iterator _start;  // 头部iterator _finish; // 尾部iterator _endofstorage; // 结束位置，标记容量大小};
}

2.2 接口实现

2.2.1 构造和拷贝构造

在C++98中，vector官方库提供了4种构造函数，分别是空对象构造、迭代器构造、拷贝构造以及给定数量和初始值的构造，那么在我们自己实现的vector中也可以尝试提供这几种构造函数的接口。

需要注意的是给定元素数量和初始值得构造函数，其中用户在传值时元素个数的类型不确定，是否为有符号类型也不确定，因此为了防止传值时发生强制类型转换存在隐患，我们可以每个类型都重载一个接口。

vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "默认构造" << endl;
}   template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "迭代器构造" << endl;for(; first != last; ++first){push_back(*first);}
}vector(size_t n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(long n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(int n, const T& val)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{reserve(n);for(int i = 0; i < n; ++i){push_back(val);}
}vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{cout << "拷贝构造" << endl;_start = new T[v.capacity()];for(int i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();
}

2.2.2 迭代器

前文提到过，vector容器是一种空间连续的容器，因此vector的迭代器实现较为简单，只需要返回其指定位置的指针即可。这里我实现了简单的正向迭代器的const和非const接口，反向迭代器实现较为复杂，需要封装并重载operator++。

public:typedef T* iterator;typedef const T* const_iterator;
public:iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

2.2.3 增删元素

push_back

对于push_back而言，唯一需要注意的就是扩容的问题。我这里采用每次扩容2倍的策略，这样既不会频繁扩容，也不会造成空间浪费。

void push_back(const T& val)
{if(_finish == _endofstorage){size_t newCapacity = capacity() == 0? 4 : 2 * capacity();reserve(newCapacity);}*_finish = val;++_finish;
}

pop_back

void pop_back()
{assert(!empty());--_finish;
}

insert

insert除了需要注意扩容的问题，还需要注意边界情况下元素插入问题。同时在插入元素时还需要挪动元素，因此insert插入位置越靠近头部效率越低。在官方库中，insert返回一个迭代器类型。

iterator insert(iterator pos, const T& val)
{if(_finish == _endofstorage){size_t len = pos - _start;size_t newCapacity = capacity() == 0? 4 : 2 * capacity();reserve(newCapacity);pos = _start + len;}iterator end = _finish;while(end >= pos + 1){*end = *(end - 1);--end;}*end = val;++_finish;
}

erase

与insert类似的是，erase也需要挪动数据，因此效率也较低，同样erase返回一个迭代器类型。

iterator erase(iterator pos)
{assert(!empty());for(iterator i = pos; i < _finish - 1; ++i){*i = *(i + 1);}--_finish;return pos;
}

clear

在模拟实现的vector中，_start表示首部，_finish表示最后一个有效元素的下一个位置。

void clear()
{_start = _finish;
}

swap

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

2.2.4 访问元素

operate[]

vector重载了[]，这样我们使用下标就可以访问并且修改vector当中的元素。

T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

2.2.5 容量

reserve

用来扩容，这里实现的reserve不支持缩容，并且只有扩容大小大于原有容量大小才会扩容，一般也不会用到缩容。

void reserve(int n)
{if(n > capacity()){T* start = new T[n];size_t sz = size();if(_start){for(int i = 0; i < sz; ++i){start[i] = _start[i];}}swap(start, _start);_finish = _start + sz;_endofstorage = _start + n;delete[] start;}
}

resize

用来对有效元素的操作，可以进行扩容，与reserve不同，resize会改变对象中有效元素的个数。

void resize(size_t n, const T& val = 0)
{if(n < size()){_finish = _start + n;}else{if(n > capacity()){reserve(n);}while(_finish < _start + n){//push_back(val);*_finish = val;++_finish;}}
}

capacity

获取vector对象容量大小

size_t capacity() const
{return _endofstorage - _start;
}

size

获取vector有效元素个数。

size_t size() const
{return _finish - _start;
}

empty

清空元素。

bool empty() const
{return _start == _finish;
}

2.3 测试

void test1()
{zch::vector<int> a;for(int i = 0; i < 10; ++i){a.push_back(i);}a.print();zch::vector<int> b(10, 5);b.print();a.resize(20);b.resize(5);a.print();b.print();vector<int> c;c.reserve(20);cout << c.size() << " " << c.capacity() << endl;if(c.empty()){cout << "yes" << endl;}else {cout << "no" << endl;}vector<int> d = a; a.insert(a.begin(), 55);b.insert(b.begin() + 5, 55);a.erase(a.begin());a.print();b.print();d.print();
}

程序测试结果如下图所示：