C++STL（四）——vector模拟
目录
- 一、vector当中的成员变量介绍
- 二、默认成员函数
- 构造函数
- 拷贝构造函数
- 赋值运算符重载函数
- 析构函数
- 三、迭代器相关函数
- begin和end
- 四、容量和大小相关函数
- size和capacity
- reserve
- resize
- empty
- 五、修改容器内容相关函数
- push_back
- pop_back
- insert
- erase
- swap
- 六、访问容器相关函数
- operator[ ]
- 七、总结
一、vector当中的成员变量介绍
在vector当中有三个成员变量_start、_finish、_endofstorage。对应起始数据、有效数据、容量空间。
二、默认成员函数
构造函数
//无参构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
//含有n个值为val的数据
vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
//迭代器区间，左闭右开
template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
拷贝构造函数
vector的构造函数涉及深拷贝问题。
传统写法
拷贝构造的传统写法的思想是我们最容易想到的：先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。
//传统写法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
//调用了所存元素的赋值运算符重载函数，而string类的赋值运算符重载函数就是深拷贝
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_endofstorage = _start + v.capacity(); //整个容器的尾
}
注意： 将容器当中的数据一个个拷贝过来时不能使用memcpy函数，当vector存储的数据是内置类型或无需进行深拷贝的自定义类型时，可以使用memcpy函数，但当vector存储的数据是需要进行深拷贝的自定义类型时，就不能使用memcpy函数了。例如，当vector存储的数据是string类的时候。
memcpy的参数是void* 强转成char*按字节拷贝，而我们需求是深拷贝也就是在开一块空间将原有数据拷贝到新空间然后释放原空间，但memcpy是开出了新空间并没有把原空间数据拷贝到新空间，而是又把原数据再次拷贝到了原空间然后调用析构函数把原空间释放，新空间并没有数据，也就成了野指针。
现代写法
拷贝构造函数的现代写法也比较简单，使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来。
//现代写法
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同
for (auto e : v) //将容器v当中的数据一个个尾插过来
{
push_back(e);
}
}
在使用范围for对容器v进行遍历的过程中，变量e就是每一个数据的拷贝，然后将e尾插到构造出来的容器当中。就算容器v当中存储的数据是string类，在e拷贝时也会自动调用string的拷贝构造（深拷贝），所以也能够避免出现与使用memcpy时类似的问题。
如果vector当中存储的元素类型是内置类型（int）或浅拷贝的自定义类型（Date），使用memcpy函数进行进行拷贝构造是没问题的，但如果vector当中存储的元素类型是深拷贝的自定义类型（string），则使用memcpy函数将不能达到我们想要的效果。
赋值运算符重载函数
vector的赋值运算符重载也及深拷贝问题
传统写法
首先判断是否是给自己赋值，若是给自己赋值则无需进行操作。若不是给自己赋值，则先开辟一块和容器v大小相同的空间，然后将容器v当中的数据一个个拷贝过来，最后更新_finish和_endofstorage的值即可。
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //释放原来的空间
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_endofstorage = _start + v.capacity(); //整个容器的尾
}
return *this; //支持连续赋值
}
//现代写法
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{
swap(v);
return *this; //支持连续赋值
}
注意： 赋值运算符重载的现代写法也是进行的深拷贝，只不过是调用的vector的拷贝构造函数进行的深拷贝，在赋值运算符重载函数当中仅仅是将深拷贝出来的对象与左值进行了交换。
析构函数
对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针。
~vector()
{
if (_start)
{
_start = _finish = _endofstorage = nullptr;
}
}
三、迭代器相关函数
vector当中的迭代器是容器当中所存储数据类型的指针。
typedef T* iterator;
typedef const T* const_iterator;
begin和end
begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。
iterator begin()
{
return _start;
}
iterator begin()const
{
return _start;
}
iterator end()
{
return _finish;
}
iterator end()const
{
return _finish;
}
四、容量和大小相关函数
size和capacity
如图对应三个成员变量各自位置，可得出有效数据个数和最大容量
由于两个指针相减的结果，就是这两个指针之间对应类型的数据个数，所以size可以由_finish - _start得到，而capacity可以由_endofstorage - _start得到。
size_t size()const
{
return _finish - _start; //返回有效数据个数
}
size_t capacity()const
{
return _endofstorage - _start; //返回最大容量
}
reserve
reserve规则：
1、当n大于对象当前的capacity时，将capacity扩大到n或大于n。
2、当n小于对象当前的capacity时，什么也不做。
reserve函数先判断所给n是否大于当前容器的最大容量（否则无需进行任何操作），操作时直接开辟一块可以容纳n个数据的空间，然后将原容器当中的有效数据拷贝到该空间，之后将原容器存储数据的空间释放，并将新开辟的空间交给该容器维护，更新容器当中各个成员变量的值。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(n) * size());
for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
}
}
错误原因
修正：
/*
方法一:调换顺序先更新成员变量_finish = tmp(即_start)+ size()
为什么不能按原顺序直接写tmp + size()
因为size函数中size()= _finish - _start，_start还没有更新
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(n) * sz);
for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中
{
tmp[i] = _start[i];
}
delete[] _start;
}
_finish = tmp + size();
_start = tmp;
_endofstorage = _start + n;
}
}*/
//方法二:提前保存变量
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size(); //记录当前容器当中有效数据的个数
T* tmp = new T[n]; //开辟一块可以容纳n个数据的空间
if (_start) //判断容器是否为空
{
//memcpy(tmp, _start, sizeof(n) * sz); //拷贝数据到新空间
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start; //释放原空间
}
_start = tmp; //将tmp所维护的数据交给_start进行维护
_finish = _start + sz; //容器有效数据的尾
_endofstorage = _start + n; //整个容器的尾
}
}
resize
1、当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
2、当n小于当前的size时，将size缩小到n.
void resize(size_t n, const T& val = T()) //匿名对象
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++finish;
}
}
}
场景
void test4_vector()
{
ling::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.resize(10, 2);
for (auto e : v)
{
cout << e << " "; //1 2 3 4 2 2 2 2 2 2
}
cout << endl;
v.resize(3);
for (auto e : v)
{
cout << e << " "; //1 2 3
}
cout << endl;
}
注意： 在C++当中内置类型也可以看作是一个类，它们也有自己的默认构造函数，所以在给resize函数的参数val设置缺省值时，设置为T( )即可。
empty
empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。
bool empty()const
{
return _start == _finish;
}
五、修改容器内容相关函数
push_back
尾插，判断是否需要扩容，将数据插入，指针后移
void push_back(size_t x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
场景
void test1_vector()
{
ling::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
pop_back
尾删数据前先判断容器是否为空，若为空则做断言处理，若不为空则将_finish–。
//尾删数据
void pop_back()
{
assert(!empty()); //容器为空则断言
_finish--; //_finish指针前移
}
insert
insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。
当有4个或8个数据等等扩容边界时在插入数据会导致迭代器失效的问题，当扩充时，开空间后将数据拷贝到新空间后释放原空间，这时_start和_finish指向新空间，pos还指向原空间已经被释放，pos为野指针。
erase
erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖。
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1; //保存pos后一位数据
while (it != _finish) //依次往前挪覆盖数据
{
*(it - 1) = *it;
++it;
}
--_finish; //最后有效数据-1
return pos;
}
swap
交换两个容器的数据，可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
六、访问容器相关函数
operator[ ]
vector也支持我们使用“下标+[ ]”的方式对容器当中的数据进行访问，实现时直接返回对应位置的数据即可。
T& operator[](size_t pos)
{
assert(pos < size()); //判断合法性
return _start[pos]; //返回下标位置对应数据
}
T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
场景
void test1_vector()
{
ling::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto e : v)
{
cout << e << " "; //1 2 3 4
}
cout << endl;
//operator[]
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
for (auto e : v)
{
cout << e << " "; //2 3 4 5
}
cout << endl;
}
注意： 重载运算符[ ]时需要重载一个适用于const容器的，因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作，不能对数据进行修改。
七、总结
注意深拷贝扩容时不能使用memcpy，使用for语句遍历赋值
insert和erase返回类型为iterator要返回pos，如果是void容易造成迭代器失效
