C++:模拟实现STL的vector

目录

一.vector类

1.vector类的构造及析构

2.定义迭代器

3.size()和capacity()

4.operator [ ] 

5.resize()和reserve()

6.插入和删除

二.整体代码

1.vector.h

2.vector.cpp

---

上一节中了解了vector中部分接口的使用,在这里我们模拟实现vector,为了避免与库中的起冲突,在这里使用命名空间

一.vector类

1.vector类的构造及析构

vector类中我们有三个对象_start,_finish,_endofstorage

构造函数

	vector() :_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}

拷贝构造

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

但是我们可以采取一个更简单的方法,将值插入要拷贝的对象中

	//v2(v1)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//将v1的数据插入v2for (const auto& ch : v){reserve(v.capacity());push_back(ch);}}

赋值

vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}void swap(vector<T>& v)
{::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);
}

析构

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

2.定义迭代器

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;}

3.size()和capacity()

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

4.operator [ ] 

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

5.resize()和reserve()

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);按字节拷贝,浅拷贝for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];//调用operator=深拷贝}delete[] _start;}_start = tmp;_finish = tmp + sz;_endofstorage = tmp + n;}
}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

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

pop_back

	void pop_back(){assert(_start < _finish);--_finish;}

insert

	void insert(iterator pos, const T& x){assert(pos <= _finish);if (_finish == _endofstorage){size_t n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);//如果增容原来的pos就失效了,需要重新计算位置pos = _start + n;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}

当我们实现insert后,push_back就可以用复用实现

void push_back(const T& x)
{insert(_finish, x);
}

erase

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

同样实现了erase,pop_back也可以复用

	void pop_back(){erase(_finish - 1);}

二.整体代码

1.vector.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace wzyl
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector() :_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}/*vector(const vector<T>& v){_start = new T[v.capacity()];_finish = _start;_endofstorage = _start + v.capacity();for (size_t i = 0; i < v.size(); ++i){*_finish = v[i];++_finish;}}*///v2(v1)vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//将v1的数据插入v2for (const auto& ch : v){reserve(v.capacity());push_back(ch);}}vector<T>& operator=(vector<T> v){swap(v);return *this;}void swap(vector<T>& v){::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);按字节拷贝,浅拷贝for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];//调用operator=深拷贝}delete[] _start;}_start = tmp;_finish = tmp + sz;_endofstorage = tmp + n;}}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& x){/*if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;*/insert(_finish, x);}void pop_back(){/*assert(_start < _finish);--_finish;*/erase(_finish - 1);}void insert(iterator pos, const T& x){assert(pos <= _finish);if (_finish == _endofstorage){size_t n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);//如果增容原来的pos就失效了,需要重新计算位置pos = _start + n;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}iterator erase(iterator pos){assert(pos < _finish);iterator it = pos;while (it < _finish){*it = *(it + 1);++it;}--_finish;return pos;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}private:iterator _start;iterator _finish;iterator _endofstorage;};void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;cout << v.capacity() << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto& ch : v){cout << ch << " ";}cout << endl;for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.insert(v.begin(), 0);for (auto& ch : v){cout << ch << " ";}cout << endl;vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}for (auto ch : v){cout << ch << " ";}cout << endl;}void test_vector3(){vector<int> v;v.reserve(10);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto ch : v){cout << ch << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl << endl;v.resize(4);for (auto ch : v){cout << ch << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl << endl;v.resize(8);for (auto ch : v){cout << ch << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl << endl;v.resize(12);for (auto ch : v){cout << ch << " ";}cout << endl;cout << v.size() << endl;cout << v.capacity() << endl << endl;}void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<int> v2(v1);for (auto ch : v1){cout << ch << " ";}cout << endl;for (auto ch : v2){cout << ch << " ";}cout << endl;vector<int> v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);v3.push_back(40);v1 = v3;for (auto ch : v1){cout << ch << " ";}cout << endl;}
}

2.vector.cpp

#include"vector.h"int main()
{//wzyl::test_vector1();//wzyl::test_vector2();//wzyl::test_vector3();//wzyl::test_vector4();
}