C++：STL中vector的使用和模拟实现

在上一篇中讲到了string类，string并不属于STL中因为string出现的比STL早，但是在使用方法上两者有相似之处，学习完string后再来看vector会容易的多，接着往下阅读，一定会有收获滴！

vector的介绍

vector的使用

vector的构造函数

vector的拷贝构造

vector iterator 的使用

vector的空间

vector增删改

vector的介绍

1.string是存储字符串的类，vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。

vector的使用

对于vector的接口有很多，想要更仔细的看这里：https://legacy.cplusplus.com/reference/vector/vector/?kw=vector

vector的构造函数

vector的构造函数重载了好几种，所以初始化的方法也有多种。

vector() //无参构造vector(size_t n,const value_type& val = value_type()) //构造并初始化n个valvector(InputIterator ﬁrst, InputIterator last) //使用迭代器来初始化

对于第二种的构造函数中value_type()会去调用该类型的构造函数，第三种使用迭代器来构造，对于vector的迭代器就是原生指针，区间是左闭右开。

示例：

int a[5] = { 1,2,3,4,5 };vector<int> v(a, a + 4);for (auto e : v){cout << e << " ";}cout << endl;vector<int>::iterator it = v.begin();vector<int> v1(v.begin(), v.end());for (auto e : v1){cout << e << " ";}cout << endl;

运行结果：

模拟实现：
成员变量：

typedef T* iterator;
typedef const T* const_iterator;iterator _start = nullptr;// 指向数据块的开始
iterator _finish = nullptr;// 指向有效数据的尾
iterator _end_Of_Storage = nullptr;// 指向存储容量的尾

        vector(){}vector(size_t n, const T& value = T()){resize(n,value);}vector(int n, const T& value = T()){resize(n, value);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

vector的拷贝构造

vector的拷贝构造是指创建一个新的vector对象，其内容与原vector对象完全相同。

vector (const vector& x);

模拟实现：

vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v. _start[i];}_finish = _start + v.size();_end_Of_Storage = _start + v.capacity();}

在模拟实现时需要注意，拷贝分为浅拷贝和深拷贝，如果在vector的实现中使用浅拷贝就会出问题，会出现析构两次以及野指针的问题，所以需要深拷贝。

vector iterator 的使用

查看vector文档可以看到vector的迭代器

begin()和end()：获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator。

模拟实现：

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

vector的空间

size() 返回 vector 当前存储的元素数量，是实际已使用的空间大小。
示例：

std::vector<int> vec = {1, 2, 3};
std::cout << vec.size(); // 输出 3

capacity() 返回 vector 当前分配的存储空间大小（以元素数量计），可能大于或等于 size()。
示例：

std::vector<int> vec;
vec.reserve(10);
std::cout << vec.capacity(); // 输出 10（size 仍为 0）

resize(n) 调整 vector 的 size 为 n：

若 n < size()，多余元素被删除。
若 n > size()，新增元素默认初始化（或通过第二个参数指定值）。
示例：

std::vector<int> vec = {1, 2, 3};
vec.resize(5);      // 变为 {1, 2, 3, 0, 0}
vec.resize(2);       // 变为 {1, 2}

reserve(n) 预分配至少容纳 n 个元素的内存空间，避免多次动态扩容（仅影响 capacity，不改变 size）。
示例：

std::vector<int> vec;
vec.reserve(100);    // 提前分配空间
vec.push_back(1);    // 不会触发扩容

区别：

size 是实际元素数量，capacity 是当前分配的内存容量。
resize 修改 size 并可能初始化/删除元素，reserve 仅调整 capacity 不改变 size。
频繁插入数据时，reserve 可减少重新分配开销。

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。 reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。 resize在开空间的同时还会进行初始化，影响size。

模拟实现：

          size_t size() const{return _finish - _start;}size_t capacity() const{return _end_Of_Storage - _start;}void reserve(size_t n){if (n > capacity()){size_t oldsz = size();T* tmp = new T[n];/*memcpy(tmp, _start, n * sizeof(T));*/for (size_t i = 0; i < oldsz; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + oldsz;_end_Of_Storage = _start + n;}}void resize(size_t n, const T& value = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = value;_finish++;}}}

vector增删改

尾插：push_back() 在 vector 末尾添加元素：

vector<int> vec = {1, 2, 3};
vec.push_back(4); // vec: {1, 2, 3, 4}

模拟实现：

void push_back(const T& x){/*if (size() == capacity()){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;*/insert(end(), x);}

如果不用insert函数就使用注释那一段代码来实现尾插，效果是一样的，只不过先实现insert函数的话写尾插会更方便一点。

insert（）在指定位置插入元素：

vec.insert(vec.begin() + 1, 5); // vec: {1, 5, 2, 3, 4}

模拟实现：

iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (size() == capacity()){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (pos <= end){*(end+1) = *end;end--;}*pos = x;++_finish;return pos;}

erase()删除指定位置的元素：

vec.erase(vec.begin() + 2); // 删除第3个元素，vec: {1, 5, 3, 4}
vec.erase(vec.begin(), vec.begin() + 2); // 删除前2个元素，vec: {3, 4}

在使用erase需要注意迭代器失效的问题，直接删除当前迭代器指向的元素会导致该迭代器失效。

例如：

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin() + 1;
vec.erase(it); // it失效
// 此时访问*it是未定义行为

以及循环删除多个元素：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ++it) {if (*it % 2 == 0) {vec.erase(it); // it失效后，++it行为未定义}
}

对于这些我们需要重新来定义迭代器it，erase会返回指向被删除下一位置的迭代器，所以我们需要重新接收更新迭代器，正确处理方法：

std::vector<int> vec = {1, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ) {if (*it % 2 == 0) {it = vec.erase(it); // 更新迭代器} else {++it;}
}

模拟实现：

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

对于erase删除数据在vector中就是需要挪动数据，直接将需要删除的数据覆盖，将后面的数据往前挪，最后返回被删除元素的位置。在进行删除动作之前需要进行断言，不可越界访问。

尾删：pop_back()：删除最后一个元素

vec.pop_back(); // vec: {1, 5, 2, 3, 4}

模拟实现：

如果先实现好erase函数，pop_back函数就很好写了。

void pop_back(){/*if(_finish != _start)--_finish;*/erase(end());}

vector的使用就介绍到这里啦，这也是常用的函数，需要了解更多可以查看vector文档来学习，如果你已经了解string类，想必vector也手到擒来，string类和STL的用法相似，学会其中一种，再去学习其它STL就比较容易。