【C++ STL】手撕vector,深入理解vector的底层

前言

vector是一个类模板,它本质是一个顺序表,通过我们之前的学习,我们一般会这样来定义一个顺序表:

template<class T>
class vector
{T* _a;size_t _size;size_t _capacity;
};

这种定义方式当然是可以的,但是我们通过看P.J.版本的stl的源码会发现,其中对vector的定义大概是这样的:

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;// 最后一个元素的下一个位置iterator _end_of_storage = nullptr;//当前容量的下一个位置};

他是通过三个指针来维护这个顺序表的,我们这篇博客也是采用这种定义方式来实现一个简易版vector的.

一.默认成员函数

1.1常用的构造函数

1.1.1默认构造函数

默认构造是实现一个空的vector，不分配任何内存。
代码实现:

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}

测试用例:

int main()
{vector<int> v;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;return 0;
}

输出结果:

size:0
capacity:0

1.1.2 n个 val值的构造函数

初始化一个vector,其中用n个val值得对象来填充.
代码示例:

		void reserve(size_t n)  {if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//不可以这样写,因为如果vector中存的类型是自定义类型,存在浅拷贝的问题//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}vector(size_t n, const T& val = T()){//考虑到扩容带来的效率低下问题,我们可以提前开好足够大的空间reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

测试用例:

int main()
{vector<int> v2(10 , 1);cout << "size:" << v2.size() << endl;cout << "capacity:" << v2.capacity() << endl;return 0;
}

输出结果:

size:10
capacity:10

1.1.3 迭代器区间构造

代码实现:

		template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

测试用例:

int main()
{string s1 = "aaaaaaa";vector<char> v3(s1.begin(), s1.end());return 0;
}

输出结果:

1.1.4 initializer_list 的构造

用一个初始化列表来构造
代码实现:

		vector(initializer_list<T> il){reserve(il.size());for (const auto& e : il){push_back(e);}}

测试用例:

int main()
{vector<int> v4{ 1,2,3,4,5,6,7,8,9 };return 0;
}

输出结果:

1.2析构函数

析构函数:完成对象中的资源的回收清理,防止出现内存泄露.

代码实现:

		~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

1.3拷贝构造函数

代码实现:

		vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}

测试用例:

int main()
{	vector<int> v4{ 1,2,3,4,5,6,7,8,9 };vector<int> v5 = v4;return 0;
}

输出结果:

1.4赋值运算符重载

代码实现:

		void swap(vector<int>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//依旧是熟悉的现代写法vector<T>& operator=(vector<T> v){swap(v);return *this;}

这里复用的是拷贝构造,拷贝构造我们已经测试过了没有什么问题,这里应该也是正常的,这里就不测试了.

二.元素的插入,删除,查找操作

2.1 operator[]重载函数

这里我们需要重载两个版本,一个是普通对象调用,另一个是const对象调用.
代码实现:

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

测试用例:

int main()
{vector<int> v1{ 1,2,3,4,5,6,7,8,9 };for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5 6 7 8 9

2.2 push_back函数:尾插一个元素

代码实现:

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

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5

2.3 pop_back函数:尾删一个元素

实现思路:
1.将_finish指针向前移动一位，即删除最后一个元素。
2.当size已经为0,即vector中已经没有数据时,就不再删除.
代码实现:

		void pop_back(){assert(size() > 0);--_finish;}

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.pop_back();for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5
1 2 3 4

2.4 insert函数:指定位置插入元素

这里需要注意迭代器失效的问题,如果不了解什么是迭代器失效的小伙伴,可以去:vector ,里面有迭代器失效场景的详细介绍.
代码实现:

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

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.insert(v1.begin() + 2, 1000);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5
1 2 1000 3 4 5

2.5 erase:删除指定位置的元素

erase同样也要注意迭代器失效.我们要通过返回一个更新之后的迭代器来避免迭代器失效场景的出现.

代码实现:

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

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.erase(v1.begin() + 2);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;}return 0;
}

输出结果:

1 2 3 4 5
1 2 4 5

三.front和back函数以及迭代器的实现

3.1 front函数: 获取第一个元素

代码实现:

		T& front(){assert(size() > 0);return _start[0];}const T& front() const{assert(size() > 0);return _start[0];}

3.2 back函数: 获取最后一个元素

代码实现:

		T& front(){assert(size() > 0);return _start[0];}const T& front() const{assert(size() > 0);return _start[0];}

3.3 begin和end函数

代码实现:

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

3.4 swap函数

代码实现:

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

希望对大家有所帮助,感谢观看!