C++ vector类模拟实现

目录

一、成员变量

二、构造函数

1.默认构造 

 2.拷贝构造

3.迭代器构造

4.使用n个值构造

5.赋值拷贝

三、析构函数 

四、vector重要成员函数

1.size和capacity函数

 2.reserve函数

 3.resize函数

 4.push_back函数

5.insert函数

6.erase函数 

7.重载operator[]

---

一、成员变量

STL库里面，vector的成员变量和string有一些不一样，他的成员变量是用了迭代器

_start是数组起始位置

_finish是数据内容结束位置的下一个

_endofstorage是开辟的空间结束位置的下一个。

 

那么vector的迭代器是又是什么呢？

vector使用了模版，他可以适配各种类型，他的迭代器就是这个模板类型的指针。

 因为vector和string一样，本质上就是数组，开辟的空间在内存上是连续的，因此使用指针当迭代器是在合理不过了。

二、构造函数

我们模仿一下STL里面的vector，没有使用适配器。

1.默认构造 

vector的默认构造很简单，直接写上就好，内容都可以不需要，因为我们在成员变量哪里给到了初始值，他会在初始化列表中自动调用，因此这里可以不需要写初始化列表。

那么我们可以不可以不要下面这局代码呢？   

答案是不可以的，因为我们后续还会写上其他的构造函数，那么编译器就不会提供默认生成的构造函数了。那这样我们普通的一个代码  vector<int> v  就会报错

vector()
{}

 2.拷贝构造

拷贝构造调用了push_back函数，先开辟好空间，防止后续再扩容，后续尾插即可。

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

3.迭代器构造

这里使用了模板来处理，因为我们不仅仅想使用vector迭代器去构造类对象，我们还想使用其他类对象的迭代器去构造。也是利用尾插即可。

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

4.使用n个值构造

开辟n个空间，并全部赋值为给到的val参数。

vector(int n, const T& val = T())
{resize(n, val);
}vector(size_t n, const T& val = T())
{resize(n,val);
}

 这里为什么我们要重载呢，一个写出int类型，一个写成size_t类型？

我们先不写上面的int重载，下面这句代码，使用n个val进行拷贝，竟然报错了，为啥会这样？

48行有问题，我们发现，明明我想调用的是58行的拷贝构造，为啥会到模板那里去？

是因为此时所传的 10 和 1 都是int类型，而下面那个是 size_t和 int 两个类型，编译器认为你要用这个模板来初始化，因此会调用生成 InputIterator为int的函数，int类型去解引用，那可不就报错了嘛，为了让编译器认识两个整形，我们就重载了vector，使他能够知道我们的意思。

5.赋值拷贝

利用了很现代的写法，参数我们不传&，就会拷贝构造一个临时对象，这个临时对象刚好是我this需要的内容，我直接和你swap一下，你身上就有了我不要的内容了，同时出了作用域你会析构，我会引用返回，就完成了赋值拷贝。

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

三、析构函数 

easy，直接delete[]  ，顺便置空即可。

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

四、vector重要成员函数

1.size和capacity函数

由于我们成员变量都是迭代器(实现方式为指针)，因此size()的大小和capacity()都可以用迭代器相减的方式得到。

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

 2.reserve函数

reserve可以开辟空间，n比现在的空间大才开辟，比现在的空间小则不管，不会删除数据。

如果需要开辟空间，则会先new出新的空间，把原有的数据数据拷贝到这个空间里，再删除原有的数据，同时对成员变量进行修改。

注意我们在拷贝的时候不能使用memcpy，因为用memcpy拷贝，如果类型为自定义类型，就仅仅是浅拷贝，浅拷贝会在开辟新空间的时候进行delete，一旦delete，新空间也被delete了。

这里我们选择了使用循环赋值，因为自定义类型会调用他的赋值拷贝，而他的赋值拷贝一般是深拷贝(只要写了的话)，因此我们再扩容的时候就不会因为delete而发生错误了。

void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy对自定义类型是浅拷贝//memcpy(tmp, _start, sz * sizeof(T));//循环赋值，会调用自定义类型的赋值拷贝，就是深拷贝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}

 3.resize函数

resize会改变vector的size()。

如果传的n要比size()小，那么就变成这个长度。

如果n比size()大，就要先看扩不扩容，但是无论扩不扩容，我们都可以直接调用reserve函数，需要扩你就扩，不需要也没啥影响，后面在将你传过来的值，赋值给还未初始化的空间。

注意在C++中一切类型都算对象，包括内置类型，因此我们传参给到的默认参数为T()  就像一个类的默认构造一样。 

void resize(size_t n,const T& val = T())
{if (n <= size()){_finish = _start + n;}else{reserve(n);for (size_t i = size(); i < n; i++){_start[i] = val;}_finish = _start + n;}
}

 4.push_back函数

push_back函数先判断空间满了没有，满了就去扩容，空间capacity()为0就给4，不为0就给2倍。

然后再*_finish这里赋值，_finish++即可。

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

5.insert函数

insert函数传的参数不是索引，而是迭代器！！！

只要有插入，我们都得判断是否扩容，由于这里传递的是迭代器(vector中是指针)，扩容有可能是异地扩容，因此地址会发生改变，我们扩容前先记录一下pos相对于_start的位置，扩容后再加上这个位置赋值给pos才对。

后续就是挪动数据，挪动完赋值，_finish++，最后要返回pos（可以防止迭代器失效）。

iterator insert(iterator pos,const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (size() == capacity()){size_t len = pos - _start; //扩容后_start位置可能会发生改变了，因此要记录pos的相对位置，改变pos的值size_t cp = capacity() == 0 ? 4 : capacity() * 2;reserve(cp);pos = _start+len;}iterator end = _finish - 1;while (end >= pos){*(end + 1)  = *end;end--;}*pos = x;_finish++;return pos;
}

6.erase函数 

erase比insert还要简单一点，也是挪动数据，方向不一样，insert是从后往前数据往后挪动，erase是从当前位置往后向前挪动数据。再_finish--，最后返回pos（这也是为了防止迭代器失效）。

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

7.重载operator[]

 分为普通版本和const版本，普通可读可写，const只能读。

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
//不可修改
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];  
}

最后附上总代码 

vector.h

#pragma once
namespace kky
{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;}vector(){}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(int n, const T& val = T()){resize(n, val);}//vector(size_t n, const T& val = T())//{//	resize(n,val);//}vector<T>& operator=(vector<T> v){swap(_start,v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy对自定义类型是浅拷贝//memcpy(tmp, _start, sz * sizeof(T));//循环赋值，会调用自定义类型的赋值拷贝，就是深拷贝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void resize(size_t n,const T& val = T()){if (n <= size()){_finish = _start + n;}else{reserve(n);for (size_t i = size(); i < n; i++){_start[i] = val;}_finish = _start + n;}}void push_back(const T& x){if (size() == capacity()){size_t cp = capacity() == 0 ? 4 : capacity() * 2;reserve(cp);}*_finish = x;_finish++;}iterator insert(iterator pos,const T& x){assert(pos >= _start);assert(pos <= _finish);if (size() == capacity()){size_t len = pos - _start; //扩容后_start位置可能会发生改变了，因此要记录pos的相对位置，改变pos的值size_t cp = capacity() == 0 ? 4 : capacity() * 2;reserve(cp);pos = _start+len;}iterator end = _finish - 1;while (end >= pos){*(end + 1)  = *end;end--;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos;while (it < _finish - 1){*it = *(it +1);++it;}_finish--;return pos;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}//不可修改const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];  }private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};void test01(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;for (auto e : v){cout << e << " ";}}void test02(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.resize(10, 6);for (auto e : v){cout << e << " ";}cout << endl;v.insert(v.begin(), 30);for (auto e : v){cout << e << " ";}cout << endl;}void test03(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin());for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin()+2);for (auto e : v){cout << e << " ";}}void test04(){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);vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{it++;}}for (auto e : v){cout << e << " ";}}void test05(){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);vector<int> v2(v);for (auto e : v){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;vector<int> v3;v3.push_back(1);v3 = v;for (auto e : v3){cout << e << " ";}}void test06(){vector<int> v(10, 1);for (auto e : v){cout << e << " ";}cout << endl;std::string s("123456");vector<int> v1(s.begin(), s.end());for (auto e : v1){cout << e << " ";}cout << endl;}void test07(){vector<int>v1(10, 1);vector<int>v2(10, 2);v1 = v2;for (auto e : v1){cout << e << " ";}cout << endl;}
}

test.cpp

#include <iostream>
using namespace std;
#include<cassert>
#include"vector.h"
int main()
{kky::test07();}