【C++】vector的模拟实现
目录
导读
我们在上期讲解了vector的一下基本使用，今天我们来模拟实现一下vector。
1. vector的核心框架接口
vector类有三个成员变量：start，finish和end_of_storage。
这三个成员变量可以用于遍历vector中的元素、确定vector的大小和容量，或者进行其他操作。
start：指向vector中第一个元素的指针或迭代器。它表示vector中数据的起始位置。
finish：指向vector中最后一个元素的下一个位置的指针或迭代器。它表示vector中数据的结束位置。
end_of_storage：指向vector内部存储空间的末尾的指针或迭代器。它表示vector内部存储空间的结束位置。
start、finish和end_of_storage三者之间的关系是：start <= finish <= end_of_storage。
namespace my_vector
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef T* const_iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}2. 构造函数
2.1 基本构造
我们在上面已经初始化过了。
vector()
{}2.2 拷贝构造（传统写法）
创建了一个大小与传入向量的容量相同的动态数组，并将其地址赋给临时指针tmp。
接下来的
for循环遍历传入向量的每个元素，并逐个将其赋值给临时数组中对应位置的元素。最后，将临时数组的起始地址赋给数据成员
_start，将结束地址赋给数据成员_finish，将容量末尾地址赋给数据成员_end_of_storage，完成拷贝构造函数的工作。
vector(const vector& v)
{
//capacity（）和size（）后面会写实现方法
T* tmp = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++)
{
tmp[i] = v[i];
}
_start = tmp;
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
2.3 析构函数
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}2.4 operator=运算符重载（传统写法）
通过判断
this指针与传入向量的地址是否相等来避免自赋值的情况。如果不是自赋值，首先通过
delete[] _start;释放当前对象的动态数组然后通过
new T[v.capacity()];重新分配一个大小与传入向量的容量相同的动态数组，并将其起始地址赋给_start。再用使用
memcpy函数将传入向量的数据复制到重新分配的动态数组中。
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
}
return *this;
}2.5 swap函数
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}2.5 operator=运算符重载（现代写法）
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}3. vector遍历
3.1 size()和capacity()
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}3.2 operator[]遍历
可以通过下标访问向量中的元素，并且根据是常量还是非常量对象，返回相应的引用类型或常引用类型，以实现读写和只读的访问操作。
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}3.3 迭代器和范围for
begin和end获取
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}测试代码：
void test_vector1()
{
vector<int> v1 = { 1,2,3,4 };
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
*it += 1;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
}4. vector常见函数
4.1 reserve函数
我们在进行使用循环遍历
_start到_finish之间的元素，并将其赋值给tmp指针所指向的位置之前，需要记录之前的size大小。这是因为我们后面需要先把原先_start给释放，如果不提前记录就会丢失数据，不知道原先有多少个元素，也就无法确定新的_finish的位置。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t old_size = size();
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_endofstorage = tmp + n;
}
}4.2 resize函数
调用
reserve(n)函数来预留至少能容纳n个元素的内存空间。然后，通过一个循环将指定值
val添加到_finish指针所指向的位置，直到_finish指针达到新的大小n，即_finish < _start + n。如果
n小于当前大小，则需要进行大小调整。将
_finish指针指向新的末尾位置_finish = _start + n，即删除多余的元素。这样就实现了调整向量的大小为
n，并在必要时添加或删除元素。
void resize(size_t n, const T& val = T())
{
if (n > size())
{
reserve(n);
// 插入
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
//删除
_finish = _start + n;
}
}4.3 insert函数
首先，使用断言
assert来确保插入位置pos在有效范围内，即在_start和_finish之间。然后，检查向量是否已满，即
_finish是否等于_endofstorage。如果已满，需要进行内存扩容。调用
reserve()函数来扩容向量的容量。如果当前容量为0，则扩容为4；否则扩容为当前容量的两倍。然后，通过计算
len来获取插入位置在_start中的偏移量。然后将
pos更新为_start + len，即新的插入位置。接下来，使用迭代器
iteratorit初始化为_finish的前一个位置。然后，通过一个循环将
it从_finish - 1向pos移动，将每个元素依次向后移动一个位置。在循环中，每个元素通过赋值运算符
=将其值赋给下一个位置*(it + 1)。完成元素的移动后，将插入位置
pos赋值为val。最后，将
_finish指针向后移动一个位置，即新增了一个元素。
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator it = _finish - 1;
while (it>=pos)
{
*(it + 1) = *it;
--it;
}
*pos = val;
++_finish;
}4.4 erase函数
首先，使用断言
assert来确保删除位置pos在有效范围内，即在_start和_finish之间。然后，将迭代器
iteratorit初始化为pos的下一个位置，即pos + 1。然后，通过一个循环将
it从pos + 1向_finish移动，将每个元素向前移动一个位置。在循环中，每个元素通过赋值运算符
=将其值赋给上一个位置*(it - 1)。完成元素的移动后，将
_finish指针向前移动一个位置，即删除了一个元素。最后，返回被删除元素的位置
pos。
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}4.5 push_back函数
我们前面既然已经实现了insert函数，那就直接调用，在尾部插入一个元素。
void push_back(const T& val)
{
insert(end(), val);
}4.6 pop_back函数
和前面一样，直接调用已经实现的erase函数，删除尾部元素即可。
void pop_back()
{
erase(end() - 1);
}4.7 empty函数
直接判断_start和_finish是不是在同一位置。
bool empty()
{
return _start == _finish;
}5. 构造函数和拷贝构造完善
5.1 拷贝构造（现代写法）
我们既然已经实现了push_back函数，可以直接开辟一个新的空间，
用尾插的形式把原先的数据拷贝过来。
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}5.2 构造函数
初始化构造
实现了一个构造函数，用于通过重复一个值来初始化向量对象。
第一个构造函数接受一个整数
n和一个值value，默认为类型T的默认值T()。首先调用reserve函数来保证向量的容量至少为n，然后通过一个循环调用push_back函数n次，将值value添加到向量的末尾。第二个构造函数接受一个
size_t类型的参数n和一个值value，其余与第一个构造函数类似。
vector(int n, const T& value = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
vector(size_t n, const T& value = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(value);
}
}列表构造
构造函数接受一个
initializer_list<T>类型的参数il，表示初始化列表。首先调用reserve函数来保证向量的容量至少为初始化列表中的元素个数，然后通过一个循环遍历初始化列表，将每个元素都添加到向量的末尾，使用push_back函数实现。这个构造函数的作用是创建一个包含初始化列表中的元素的向量对象。通过初始化列表可以直接在创建向量对象的同时，指定向量的初始内容。
// vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}区间构造
构造函数接受两个迭代器类型的参数
first和last，表示要复制的元素的范围。通过一个循环，将从
first到last的元素依次调用push_back函数添加到向量的末尾。这个构造函数的作用是创建一个包含迭代器范围内元素的向量对象。通过传入迭代器范围，可以将其他容器中的元素复制到向量中，或者从一个自定义的数据结构中取出元素并添加到向量中。这样可以方便地初始化向量对象，而不必手动逐个添加元素。
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}6. 代码整理
6.1 vector.h文件
#pragma once
#include <assert.h>
namespace my_vector
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector()
{}
//v2(v1)构造函数
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
// vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 };
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
vector(int n, const T& value = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
vector(size_t n, const T& value = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
// 类模板的成员函数可以是函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t old_size = size();
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_endofstorage = tmp + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n > size())
{
reserve(n);
// 插入
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
//删除
_finish = _start + n;
}
}
bool empty()
{
return _start == _finish;
}
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator it = _finish - 1;
while (it>=pos)
{
*(it + 1) = *it;
--it;
}
*pos = val;
++_finish;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
erase(end() - 1);
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
// 函数模板
template<class T>
void print_vector(const vector<T>&v)
{
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
void test_vector1()
{
vector<int> v1 = { 1,2,3,4 };
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
*it += 1;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
}
}
6.2 test.cpp文件
#include <iostream>
using namespace std;
#include "vector.h"
int main()
{
my_vector::test_vector1();
return 0;
}