【C++精华铺】11.STL vector模拟实现

1.序言

        STL（Standard Template Library）是C++的标准库之一，提供了一系列的模板类和函数，用于实现常用的数据结构和算法。其中，STL的vector是一个动态数组，可以根据需要自动调整大小。

        vector可以存储任意类型的对象，并且可以在尾部插入和删除元素，还可以随机访问和修改任意位置的元素。它的实现使用了动态内存分配，因此在插入和删除元素时，可能会触发内存重新分配和数据拷贝，导致效率降低。

        vector提供了一系列的成员函数和操作符，用于操作和访问其中的元素。一些常用的成员函数包括：push_back()用于在尾部插入元素，pop_back()用于删除尾部元素，size()用于返回元素个数，empty()用于判断是否为空，clear()用于清空元素，等等。

        除了基本的操作函数之外，vector还提供了一些高级的操作，例如使用迭代器(iterator)遍历元素、使用算法函数对元素进行排序、使用resize()改变容器大小、使用reserve()预留容器空间等。

        总之，STL的vector是一个非常有用的数据结构，可以方便地实现动态数组，并且提供了丰富的操作函数和算法，方便程序员进行操作和处理。

2.vector的整体框架

template<class T>
class Vector
{
public://迭代器类型typedef T* iterator;typedef const T* const_iterator;//...private:iterator _start;//数据存储首地址iterator _finish;//有效数据尾部地址下一个地址。iterator _end_of_storage;//容量尾地址下一个地址
};

3.构造与析构

vector()
{} //因为我们给属性添加了缺省值，这里自动使用缺省值初始化~vector()
{delete[] _start; //使用delete[]是因为vector也用于自定义类型，自动调用析构_start = _finish = _end_of_storage = nullptr;
}

4.size() 和 capacity()

        size() 返回元素个数，capacity() 返回容量。

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

5.reserve() 和 resize()

        reserve() 在容量不足时会进行扩容，需要注重的便是深浅拷贝。resize() 当n小于size()时就会删除超出n位置的元素，如果n大于size()，大于size()的部分会进行初始化。如下：

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];if (_start){for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];         //运算符重载深拷贝}delete[] _start;}_finish = tmp + size();_end_of_storage = tmp + n;_start = tmp;}
}
void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while(_finish != _start + n){*(_finish) = val;_finish++;}}
}

6.push_back() 和 pop_back()

        过于简单没什么好说的，注意检查容量。

void push_back(const T& val)
{if (_end_of_storage == _finish)  {reserve(capacity == 0 ? 4 : capacity() * 2);}*(_finish) = val;_finish++;
}bool empty()const
{return size() == 0;
}
void pop_back()
{assert(!empty());_finish--;
}

7.其他构造

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(size_t n, const T& val = T())
{_start = new T[n];for (size_t i = 0; i < n; i++){push_back(val);}
}
vector(int n, const T& val = T())  //防止优先匹配模板
{_start = new T[n];for (size_t i = 0; i < n; i++){push_back(val);}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

8.insert() 和 erase()

        insert() 在插入时可能进行扩容，扩容后迭代器失效，需要更新pos，erase() 使用时比如删除最后一个元素，导致pos处于无效位置也会导致pos失效。

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

9.operator[]

T& operator[](size_t pos)
{assert(pos < size() && pos >= 0);return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size() && pos >= 0);return _start[pos];
}

10.赋值重载

vector<T>& operator=(const vector<T>& v)
{T* tmp = new T[v.capacity];for (size_t i = 1; i < v.size(); i++){tmp[i] = v._start[i];}if (_start){delete[] _start;}_start = tmp;_finish = _start + v.size();_end_of_storage = _start + v.capacity();return *this;
}

11.迭代器

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

12.整体代码

#include<iostream>
#include<assert.h>
using namespace std;
namespace zy
{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() && pos >= 0);return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size() && pos >= 0);return _start[pos];}vector(){}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}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(size_t n, const T& val = T()){_start = new T[n];for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T())  //防止优先匹配模板{_start = new T[n];for (size_t i = 0; i < n; i++){push_back(val);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (_start){for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_finish = tmp + size();_end_of_storage = tmp + n;_start = tmp;}}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while(_finish != _start + n){*(_finish) = val;_finish++;}}}void push_back(const T& val){if (_end_of_storage == _finish)  {reserve(capacity == 0 ? 4 : capacity() * 2);}*(_finish) = val;_finish++;}bool empty()const{return size() == 0;}void pop_back(){assert(!empty());_finish--;}iterator insert(iterator pos,const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (end > pos){*(end) = *(end - 1);}*pos = val;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator start = pos;while (start < _finish - 1){*start = *(start + 1);start++;}_finish--;return pos;}vector<T>& operator=(const vector<T>& v){T* tmp = new T[v.capacity];for (size_t i = 1; i < v.size(); i++){tmp[i] = v._start[i];}if (_start){delete[] _start;}_start = tmp;_finish = _start + v.size();_end_of_storage = _start + v.capacity();return *this;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};}