【C++】模拟实现vector
心怀花木 2024-10-02 10:35:06 阅读 86
在上篇中我们已经了解过的vector各种接口的功能使用，接下来我们就试着模拟实现一下吧！
注意：我们在此实现的和C++标准库中实现的有所不同，其目的主要是帮助大家大概理解底层原理。
我们模拟vector容器的大致框架是：
<code>template<class T>
class vector
{
public:
typedef T* iterator; //普通迭代器
typedef const T* const_iterator; //const迭代器
//...
private:
iterator _start = nullptr; //指向容器起始位置(第一个有效数据)
iterator _finish = nullptr; //指向容器最后一个有效数据的下一个位置
iterator _end_of_storage = nullptr; //指向容器所开空间的最后一个位置的下一个位置
};
注意这里要与string类进行区别，我们在模拟string类时它有3个成员变量，其中，2个内置类型分别表示数据个数和容量大小，还有1个指针，指向空间起始位置，在这里我们换成了3个指针，它可以间接表示数据个数和容量大小，它和之前写的差别不大，只是形式上略有不同。
inerator是参数模板T类型的指针，容器中数据元素的类型是T。
我们本篇以实现为主，不再细讲各个函数功能介绍。
如果大家对各个成员函数还不太了解其功能时，可以去先看一下这篇文章->vector容器的基本使用
一、成员函数
1、size()
//返回vector容器元素个数
size_t size() const
{
return _finish - _start;
}
2、capacity()
//返回vector容器容量大小
size_t capacity() const
{
return _end_of_storage - _start;
}
3、empty()
//判断容器中元素是否为空，若为空返回true，否则返回false
bool empty()
{
return _start == _finish;
}
4、clear()
//清空容器中的数据，容量不变
void clear()
{
_finish = _start;
}
4、operator[]
//返回下标为i位置上的值
T& operator[](size_t i)
{
assert(i < size()); //若i>=size()，说明越界了，程序就会发生断言错误
return _start[i];
}
空间是在堆上开辟的，所以可以传引用返回，传引用范围的目的是：(1)若T是自定义类型就可以减少一次拷贝构造。(2)方便我们修改对应下标的值。
如果对象被const修饰，也就是禁止修改对应的值，我们可以再写一个重载函数：
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
5、reserve()
//预留n个元素的空间
void reserve(size_t n)
{
if (n > capacity())
{
//扩容
T* tmp = new T[n]; //新开一段空间
memcpy(tmp, _start, sizeof(T) * size()); //旧空间的值赋给新空间
delete[] _start; //释放旧空间
_start = tmp; //获得新空间
_finish = _start + size(); //改变_finish
_end_of_storage = _start + n; //改变_end_of_storage
}
}
当n大于capacity时，我们将扩容，当n小于capacity时，C++标准明确不缩容，所以我们什么也不做。
扩容的逻辑就是新开一段空间，将原有的空间中的值拷贝给新空间，然后释放旧的空间，将我们新开的空间作为现在的空间。
6、resize()
//改变元素个数
void resize(size_t n, T val = T())
{
if (n < size()) //如果n小于size()就更新_finish
{
_finish = _start + n;
}
else //否则就需要扩容
{
reserve(n); //reserve会检查，大于capacity才会扩容，如果扩容，不多扩，要多大给多大
while (_finish < _start + n)
{
*_finish = val; //初始化新添加的元素值为val
++_finish;
}
}
}
一些函数参数有缺省值，但在此之前见到的缺省值一般都是内置类型，这里却不同，因为在模板被调用之前T的类型是未知的，它有可能是自定义类型，若是自定义类型，就不能单纯的给内置类型的缺省值，所以我们这里给的是T类型的默认构造参数。
那如果T是内置类型，这样行吗？内置类型也有构造函数？
我们暂且可以认为内置类型有构造函数，我们可以看几个例子：
int main()
{
int a = int();
int b = int(1);
int c(10);
cout << "a:" << a << endl;
cout << "b:" << b << endl;
cout << "c:" << c << endl;
return 0;
}
运行结果：
从代码的写法风格和结果上，我们可以认为内置类型有构造函数。
利用resize我们可以直接初始化：
<code>vector<int> v;
v.resize(10,1); //初始化为10个1
我们写一段代码来测试一下：
在主函数中调用test_vector0()：
void test_vector0()
{
vector<int> v;
v.resize(10, 1);
print_container(v);
v.reserve(20); //初始空间给20
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//1、size() < n < capacity()
v.resize(15, 2);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//2、n > capacity()
v.resize(30, 100);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//3、n < size()
v.resize(5);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
}
运行结果：
这里的print_container()是我们自己写的通用容器的打印方法，大家在下面的9(3)可以看到。
7、push_back()
它的功能是在尾部插入一个元素。
<code>//尾插，在最后一个有效元素后插入一个新元素
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
//扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
插入前，先判断需不需要扩容，若需要就先扩容，之后再进行尾插并更新_finish指针。
我们写完了尾插可以先测试一下，看看功能是否正确：
在主函数中调用test_vector1()：
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);
for (size_t i = 0;i < v.size();++i)
cout << v[i] << " ";
}
运行结果：
程序崩溃了，这是什么原因导致的呢？
在插入数据时，首先要判断是否扩容，我们首次尾插，_strat和_finish是相同的，所以要扩容。问题就出在这扩容上。经过调试：
我们发现，扩容后_finish竟然还是空指针，那一会插入数据必然报错，空指针不可以解引用的。
所以，问题的根本是在_finish = _start + size()；这行代码。_start因该是没问题的，它不再是空指针了，而是一个新的值，最终定位，问题出在size()上。
此时的size()中，_finish是扩容前的，_start是扩容后的，而_finish = _start + size()中的_strat也是扩容后的，所以抵消掉就是_finish = _finish，扩容前的_finish我们默认给的就是nullptr。所以问题出在这里。
我们可以对reserve()进行简单的修改：
<code>void reserve(size_t n)
{
if (n > capacity())
{
//扩容
T* tmp = new T[n]; //新开一段空间
memcpy(tmp, _start, sizeof(T) * size()); //旧空间的值赋给新空间
delete[] _start; //释放旧空间
_finish = tmp + size(); //先修改_finish
_start = tmp; //再修改_start
_end_of_storage = _start + n; //改变_end_of_storage
}
}
这样size()中的_finish和_start都是扩容前的了，这样就解决了问题。但不难免有些人会感觉看着别扭，万一有些人有强迫症，就要先写_start = tmp 再写 _finish = tmp + size(); 那程序就还是会崩溃。有没有方法既可以看着舒服，又可以使程序正常运行呢？
答案是有的。
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size(); //扩容前先记录数据个数
//扩容
T* tmp = new T[n]; //新开一段空间
memcpy(tmp, _start, sizeof(T) * old_size); //旧空间的值赋给新空间
delete[] _start; //释放旧空间
//都用tmp，这样可以随便调整它们3个的位置
_start = tmp; //获得新空间
_finish = tmp + old_size; //改变_finish
_end_of_storage = tmp + n; //改变_end_of_storage
}
}
我们在扩容前，定义一个old_size就解决问题啦，它用于记录扩容前数据个数。
8、pop_back()
//尾删，删除最后一个有效元素
void pop_back()
{
assert(!empty());
--_finish;
}
9、迭代器
(1)begin()
普通迭代器：
iterator begin()
{
return _start;
}
const迭代器：
const_iterator begin() const
{
return _start;
}
(2)end()
普通迭代器：
iterator end()
{
return _finish;
}
const迭代器：
const_iterator end() const
{
return _finish;
}
(3)print_container()
我们在类外面来写一个通用的，打印容器中数据的函数。
template<class Container>
void print_container(const Container& v)
{
//vector<T>::const_iterator表达含义不清淅，这种写法既可以将const_iterator看作静态成员变量，也可以将它看作类型
//规定--不能在没有实例化的类模板里面取东西。因为编译器不能区分这里的
//const_iterator是类型还是静态成员变量，如果不加typename在语法上就会报错
//如果加了typename编译器就知道了这是类型而不是静态成员变量，编译器认为在语法上没问题，所以不会报错
//typename Container::const_iterator it = v.begin();
auto it = v.begin(); //简单起见，我们可以直接用auto来让编译器自动帮我们识别类型
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//for(auto e : v)
//{
//cout << e << " ";
//}
//cout << endl;
}
我们知道，编译器在编译代码时是从上到下进行编译的，当编译到 print_container这个函数模板时，类模板还没有实例化，如果贸然从中取到东西，就可能导致出现许多问题，就比如这里的const_iterator，所以我们规定不要在没有实例化的类模板里面取东西，这里我们明确知道了const_iterator是一个类型名，要想在语法上过的去，就必须加上typename关键字。
假设这里的const_iterator是静态成员变量，那么编译器只会认为你加了typename，是个类型，it的类型是const_iterator，这样定义语法上不会出错，别的它可就不管啦。但实际上语法虽然可以通过，但const_iterator是静态成员变量，运行时绝对会出问题的。
如果它本身就是静态成员变量，我们可以不加typename，因为静态变量我们在书写时就不会以这种方式去写vector<T>::const_iterator it。
如果不加typename，编译器就会按照静态成员变量去识别了。
10、insert()
//在pos位置前插入新元素x
void insert(iterator pos,const T& x)
{
//判断是否需要扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//end指向最后一个有效数据的位置
iterator end = _finish - 1;
while (end >= pos) //依次挪动数据
{
*(end + 1) = *end;
--end;
}
*pos = x; //pos位置上赋值
++_finish; //更新_finish
}
代码写起来很容易，那我们来测试一下：
在主函数中调用test_vector2()：
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);
print_container(v);
//在下标为0的位置上插入100
v.insert(v.begin() + 0, 100);
print_container(v);
}
运行结果：
结果没有任何问题。
在这段代码中，我们在push_back之前，容量是4，而我们插入了5个数据，所以会扩容，在扩容后，我们调用insert进行插入数据，运行结果也没有任何问题。
接下来我们修改一下测试代码：
<code>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);
print_container(v);
//在下标为0的位置上插入100
v.insert(v.begin() + 0, 100);
print_container(v);
}
我将这段代码的第5个push_back给注释了，其目的是在调用insert时再扩容，看看会发生什么情况？
运行结果：
这段代码已经崩了。
这里就出现了问题，而这个问题就是迭代器失效。
我们来分析一下，我们让insert插入时扩容，就导致了问题，画个图让大家能更好的理解：
扩容后，原先的空间就被释放了，但pos指向的还是原来空间的位置， 在insert中依次挪动数据时就会导致出现问题，这就是迭代器失效的一个例子，此时的pos就是野指针。
为了解决这个问题，我们可以在扩容之前记录一下pos与_satrt的相对位置，扩容后，再更新pos。
<code>void insert(iterator pos,const T& x)
{
if (_finish == _end_of_storage)
{
size_t len = pos - _start; //记录相对位置
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len; //更新pos
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
运行结果：
这样就解决了问题。
我们接下来再来实现一个小功能：
输入一个值，然后用查找算法看看这个值是否在vector中存在。
在主函数中调用test_vector3()：
<code>void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
int x;
cin >> x;
auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
if (p != v.end())
{
v.insert(p, 2000); //如果找到，就在该位置上插入2000
print_container(v);
}
else
{
cout << "不存在:" << x << endl;
}
}
其中，find是定义在<algorithm>这个头文件中的，它是一个函数模板，支持所有容器在一段区间中查找相应元素。它大概是这样的：
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
它是在[first,last)这个区间去找val，注意是左闭右开。
test_vector3()运行结果：
我们输入的x值为3，结果并没有任何错误。
现在，我们让查找到的pos位置上的值乘100：
<code>void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
print_container(v);
int x;
cin >> x;
auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
if (p != v.end())
{
v.insert(p, 2000); //如果找到，就在该位置上插入2000
(*p) *= 100;
print_container(v);
}
else
{
cout << "不存在:" << x << endl;
}
}
运行结果：
我们本意是让3乘以100，而不是让2000乘以100，这也是一种迭代器失效。p的意义发生了改变，它的本意是指向3，然而插入了2000，它的指向由3变为2000，这时对p指向的数据进行操作就会发生迭代器失效。虽然语法上没有报错，但它也是迭代器失效的一种情况。 这在vs2019下调用标准库中的vector会进行强制检查，若访问失效的迭代器就会报错。这种不扩容的场景，在Linux(g++)下不会报错。
那如果我将第5个push_back给注释呢？
<code>void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v.push_back(5);
print_container(v);
int x;
cin >> x;
auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
if (p != v.end())
{
v.insert(p, 2000); //如果找到，就在该位置上插入2000
(*p) *= 100;
print_container(v);
}
else
{
cout << "不存在:" << x << endl;
}
}
运行结果：
发现这时2000也没有乘100，这就奇了怪了？
我们把第5个push_back注释掉的结果是在调用insert时扩容。我们传的第一个参数p，reserve进行接收，但形参改变不会影响实参，在reserve内部，pos(形参)确实是更新了，但外部的p(实参)却不会更新，所以在一块被释放的空间上进行操作是没用的，也就是2000还是2000，它不会乘100。
有人可能就会想，insert函数的第一个参数改为引用不就行了？这是不行的，我们在调用insert时传的第一个参数是临时变量(p)，临时变量具有常性，如果insert函数的第一个参数(pos)是引用，那就是典型的权限放大，那如果再加一个const呢(const iterator& pos )？那也不行，如果insert中要更新pos，那就不能加const。
实际中，我们调用insert后，到底扩不扩容是不清楚的，所以尽量不要对p"动手脚"。
在扩容的情况下，Linux也不会报错。
总结一下：insert后p就失效了，不要访问！
当然，也可以有另外一种处理方式，就是将pos作为返回值：
<code>iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
修改测试代码：
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
int x;
cin >> x;
auto p = std::find(v.begin(), v.end(), x);
if (p != v.end())
{
//insert后p就失效，不要直接访问，要访问就要更新这个失效的迭代器的值
p = v.insert(p, 2000); //更新p
(*(p + 1)) *= 100;
print_container(v);
}
else
{
cout << "不存在:" << x << endl;
}
}
运行结果：
这样就可以解决问题了。
11、erase()
通常情况下，删除数据后，容量是不会变的。
<code>//删除pos位置上的数据
void erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
auto it = pos + 1; //记录要删除位置的下一位置
while (it != end()) //依次覆盖
{
*(it - 1) = *it;
++it;
}
--_finish; //更新_finish
}
删除pos位置上的数据后，pos的意义发生了改变，这也是迭代器失效。
我们来测试一下：
在主函数中调用test_vector4()：
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
print_container(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it; //it的意义发生了改变
}
print_container(v);
}
运行结果：
从结果上看，满足了要求。
修改一下测试代码：
<code>void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4); //多插入一个4
v.push_back(5);
print_container(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
print_container(v);
}
再看运行结果：
没删除干净？
这很容易理解，我们在删除一个偶数后，会++it，如果我们删除的偶数后面紧跟着一个偶数，在删除第一个偶数的时候，所有数据往前挪，那么第一个偶数的位置就会被第二个偶数所取代，这时++it，就会跳过对第二个偶数的判断，导致漏删。
这段代码还会出现一个问题：
如果最后一个数是偶数的话，erase在删除数据时，会--_finish，删除后，在测试代码中的while循环中还会++it，然后进行while循环条件判断，发现条件为真(这时就出问题了)，此时如果if条件为假就是死循环，如果if条件为真，调用erase就会发生断言错误。
在Linux下，运行该代码时，它会和我们产生一样的效果。如果在vs2019下，这3种情况都跑不通。
这里如果解决迭代器失效带来的问题，我们可以把删除位置的下一位置作为返回值进行返回：
<code>iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
修改测试代码：
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it); //用返回值更新it
else
++it; //加一个else，这样就能删除干净，且不会发生最后一个是偶数时程序报错的问题。
}
print_container(v);
}
运行结果：
这样就可以解决问题啦。
二、析构函数
<code>~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
三、拷贝构造
抛弃以往的写法，我们现在换一种写法：
vector(const vector<T>& v)
{
reserve(v.capacity()); //提前开好空间，就不需要频繁扩容了
for (const auto& e : v)
push_back(e);
}
这里的v有可能是自定义类型，所以我在范围for中加了一个引用，防止多次构造，我们这里只是赋值，不修改，所以又加了一个const。
我们来测试一下：
在主函数中调用test_vector5()：
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
vector<int> v2 = v1; //拷贝构造
print_container(v2);
}
运行结果：
四、赋值重载
1、传统写法
<code>vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
//方式1
clear();
reserve(v.capacity());
for (const auto& e : v)
push_back(e);
//方式2
//delete[] _start;
//_start = new T[v.capacity()];
//memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
return *this;
}
2、现代写法
void swap(vector<T>& 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) //这里不能用引用，假设v1 = v2，我们不能改变v2
{
swap(v);
return *this;
}
额外说明一点，在类中，类名可以替代类型。比如：
vector<int> 可以直接写成 vector
我们写一段代码测试一下：
在主函数中调用test_vector6()：
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
cout << v1.size() << endl;
cout << v1.capacity() << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
print_container(v3);
cout << v3.size() << endl;
cout << v3.capacity() << endl;
v1 = v3;
print_container(v1);
cout << v1.size() << endl;
cout << v1.capacity() << endl;
}
运行结果：
五、构造函数
1、默认构造
<code>vector(){}
虽然我们只写了框架，没有实质内容，但编译器依然会去走初始化列表，用缺省值进行初始化。
在C++11中，还有另外一种表示方法：
//C++11 强制生成默认构造
vector() = default;
2、迭代器区间构造(通用)
注意：类模板中还可以定义函数模板。
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
我们将它定义为函数模板的好处是，它不仅可以用vector容器类型的迭代器区间初始化，还可以用其他类型容器的迭代器区间初始化，提高了复用性。 但有一个要求是类型需要匹配，比如我这个容器是vector里面数据类型是int，你传过来的容器是list里面的数据类型是string，这是不匹配的。要保证传过来的容器中的数据类型是int，或者能隐式类型转换为int。
我们写一段代码测试一下迭代器区间初始化：
在主函数中调用test_vector7()：
void test_vector7()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
//用迭代器区间初始化，从下标为1的位置开始到下标为2的位置结束(左闭右开)
vector<int> v2(v1.begin() + 1, v1.begin() + 3);
print_container(v2);
}
运行结果：
3、用n个m初始化
<code>vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0;i < n;++i)
{
push_back(val);
}
}
我们来测试一下：
在主函数中调用test_vector8()：
void test_vector8()
{
//用n个m初始化
vector<string> v1(10, "1111111");
print_container(v1);
vector<int> v2(10);
print_container(v2);
}
运行结果：
运行结果没有任何问题。
我们修改一下测试数据：
<code>void test_vector8()
{
vector<int> v3(10, 1);
print_container(v3);
}
运行结果：
这里会报错，非法的间接寻址。 它这里是匹配到迭代器区间构造上了，将InputIterator推导为int类型，它里面中的while循环里的*first是对int类型解引用，所以会产生非法间接寻址。
原因是，编译器在处理时只会找最匹配的函数进行调用，我们传的是10和1，它们的默认类型是int，调用函数模板时推出两个InputIterator都为int，挺合适的，我传的是int类型，如果调用vector(size_t n, const T& val = T())这个函数，那么我还需要隐式转换一下(将int转换为size_t)，这没第一种舒服，所以编译器去调用了函数模板，这就导致出现了问题。
解决方法1：
<code>void test_vector8()
{
vector<int> v3(10u, 1);
print_container(v3);
}
在参数10后面添加一个u，代表无符号整形(size_t)。
解决方法2：
修改构造函数，将第一个参数指定为int类型：
vector(int n, const T& val = T()) //第一个参数指定为int类型
{
reserve(n);
for (int i = 0;i < n;++i)
{
push_back(val);
}
}
六、浅拷贝问题
我们先来看一段代码：
void test_vector9()
{
vector<string> v;
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
print_container(v);
}
在主函数中调用test_vector9()运行结果：
结果没问题，正常打印。
现在我们修改一下测试代码的内容：
<code>void test_vector9()
{
vector<string> v;
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
print_container(v);
v.push_back("11111111111111111");
print_container(v);
}
再看运行结果：
结果出现乱码了，这可不是我们期望的结果。
我们在添加第5个push_back时出现了问题，说明问题出现在扩容的地方。其实是memset这里出现了问题，我画个图来帮助大家理解：
扩容前：
扩容后：
在reserve函数中，当值复制拷贝完后，要对原来的空间(_start)进行释放，问题就出在释放身上，我们使用memcpy拷贝时，memcpy是一个字节一个字节的进行拷贝(浅拷贝)，每个string中都有一个指针，指向对应的空间，memcpy拷贝给tmp时，tmp中的每个string中的指针跟旧的空间(_start)中每个string中的指针一模一样(一个字节一个字节),所以当释放旧的空间(_start)时，tmp中的string中的指针指向的空间也被释放了，这就导致了问题所在，即打印乱码。
大致就是这样一张图(画的不太好，见谅)：
总结：
memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因memcpy是浅拷贝，可能会引起内存泄漏和程序崩溃。
如何解决这种浅拷贝带来问题呢？
当然是用深拷贝啦，请看代码：
<code>void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size(); //扩容前先记录数据个数
//扩容
T* tmp = new T[n]; //新开一段空间
//用for循环进行深拷贝
for (size_t i = 0;i < old_size;++i)
{
tmp[i] = _start[i]; //赋值重载，如果是内置类型也可以直接赋值
}
delete[] _start; //释放旧空间
_start = tmp; //获得新空间
_finish = _start + old_size; //改变_finish
_end_of_storage = _start + n; //改变_end_of_storage
}
}
七、源码
1、vector.h
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <vector>
#include <string>
using namespace std;
namespace blue
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& e : v)
push_back(e);
}
//赋值重载，方式1
//vector<T>& operator=(const vector<T>& v)
//{
//if (this != &v)
//{
////方式1
//clear();
//reserve(v.capacity());
//for (const auto& e : v)
//push_back(e);
////方式2
////delete[] _start;
////_start = new T[v.capacity()];
////memcpy(_start, v._start, sizeof(T) * v.size());
//_finish = _start + v.size();
//_end_of_storage = _start + v.capacity();
//}
//return *this;
//}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//赋值重载，方式2
//vector<T>& operator=(vector<T> v)
//在类里面可以用类名替代类型
vector& operator=(vector v)
{
swap(v);
return *this;
}
//默认构造
//vector()
//{}
//C++11 强制生成默认构造
vector() = default;
//迭代器区间构造
//类模板的成员函数还可以继续是函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//用n个m初始化构造，方式1(弃)
/*vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0;i < n;++i)
{
push_back(val);
}
}*/
//用n个m初始化构造，方式2
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0;i < n;++i)
{
push_back(val);
}
}
//返回vector容器元素个数
size_t size() const
{
return _finish - _start;
}
//返回vector容器容量大小
size_t capacity() const
{
return _end_of_storage - _start;
}
//判断容器中元素是否为空，若为空返回true，否则返回false
bool empty()
{
return _start == _finish;
}
//清空容器中的数据，容量不变
void clear()
{
_finish = _start;
}
//返回下标为i位置上的值
T& operator[](size_t i)
{
assert(i < size()); //若i>=size()，说明越界了，程序就会发生断言错误
return _start[i];
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size(); //扩容前先记录数据个数
//扩容
T* tmp = new T[n]; //新开一段空间
//memcpy(tmp, _start, sizeof(T) * old_size); //旧空间的值赋给新空间
for (size_t i = 0;i < old_size;++i)
{
tmp[i] = _start[i];
}
delete[] _start; //释放旧空间
_start = tmp; //获得新空间
_finish = _start + old_size; //改变_finish
_end_of_storage = _start + n; //改变_end_of_storage
}
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
//尾插
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
//扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
//尾删
void pop_back()
{
assert(!empty());
--_finish;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//void insert(iterator pos,const T& x)
//{
//if (_finish == _end_of_storage)
//{
//size_t len = pos - _start; //记录相对位置
//reserve(capacity() == 0 ? 4 : capacity() * 2);
//pos = _start + len; //更新pos
//}
//iterator end = _finish - 1;
//while (end >= pos)
//{
//*(end + 1) = *end;
//--end;
//}
//*pos = x;
//++_finish;
//}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
/*void erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
}*/
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
//通用的，打印容器中数据
template<class Container>
void print_container(const Container& v)
{
//规定--不能在没有实例化的类模板里面取东西，因为编译器不能区分这里的const_iterator是类型还是静态成员变量，如果加了typename编译器就知道了这是类型而不是静态成员变量，所以编译器认为语法上没问题，所以不会报错
//typename Container::const_iterator it = v.begin();
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
/*for(auto e : v)
{
cout << e << " ";
}
cout << endl;*/
}
void test_vector0()
{
vector<int> v;
v.resize(10, 1);
print_container(v);
v.reserve(20); //初始空间给20
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//1、size() < n < capacity()
v.resize(15, 2);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//2、n > capacity()
v.resize(30, 100);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << "------------------" << endl;
//3、n < size()
v.resize(5);
print_container(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
}
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);
for (size_t i = 0;i < v.size();++i)
cout << v[i] << " ";
}
//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);
//print_container(v);
////在下标为0的位置上插入100
//v.insert(v.begin() + 0, 100);
//print_container(v);
//}
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);
print_container(v);
//在下标为0的位置上插入100
v.insert(v.begin() + 0, 100);
print_container(v);
}
//void test_vector3()
//{
//vector<int> v;
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//print_container(v);
//int x;
//cin >> x;
//auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
//if (p != v.end())
//{
//v.insert(p, 2000); //如果找到，就在该位置上插入2000
//print_container(v);
//}
//else
//{
//cout << "不存在:" << x << endl;
//}
//}
//void test_vector3()
//{
//vector<int> v;
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//v.push_back(5);
//print_container(v);
//int x;
//cin >> x;
//auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
//if (p != v.end())
//{
//v.insert(p, 2000); //如果找到，就在该位置上插入2000
//(*p) *= 100;
//print_container(v);
//}
//else
//{
//cout << "不存在:" << x << endl;
//}
//}
//void test_vector3()
//{
//vector<int> v;
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
////v.push_back(5);
//print_container(v);
//int x;
//cin >> x;
//auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找
//if (p != v.end())
//{
//v.insert(p, 2000); //如果找到，就在该位置上插入2000
//(*p) *= 100;
//print_container(v);
//}
//else
//{
//cout << "不存在:" << x << endl;
//}
//}
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
int x;
cin >> x;
auto p = std::find(v.begin(), v.end(), x);
if (p != v.end())
{
//insert后p就失效，不要直接访问，要访问就要更新这个失效的迭代器的值
p = v.insert(p, 2000); //更新p
(*(p + 1)) *= 100;
print_container(v);
}
else
{
cout << "不存在:" << x << endl;
}
}
//void test_vector4()
//{
//vector<int> v;
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//v.push_back(5);
//print_container(v);
////删除所有的偶数
//auto it = v.begin();
//while (it != v.end())
//{
//if (*it % 2 == 0)
//v.erase(it);
//++it; //it的意义发生了改变
//}
//print_container(v);
//}
//void test_vector4()
//{
//vector<int> v;
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//v.push_back(4); //多插入一个4
//v.push_back(5);
//print_container(v);
////删除所有的偶数
//auto it = v.begin();
//while (it != v.end())
//{
//if (*it % 2 == 0)
//v.erase(it);
//++it;
//}
//print_container(v);
//}
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_container(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it); //用返回值更新it
else
++it; //加一个else，这样就能删除干净，且不会发生最后一个是偶数时程序报错的问题。
}
print_container(v);
}
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
vector<int> v2 = v1; //拷贝构造
print_container(v2);
}
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
cout << v1.size() << endl;
cout << v1.capacity() << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
print_container(v3);
cout << v3.size() << endl;
cout << v3.capacity() << endl;
v1 = v3;
print_container(v1);
cout << v1.size() << endl;
cout << v1.capacity() << endl;
}
void test_vector7()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
print_container(v1);
//用迭代器区间初始化，从下标为1的位置开始到下标为2的位置结束(左闭右开)
vector<int> v2(v1.begin() + 1, v1.begin() + 3);
print_container(v2);
}
//void test_vector8()
//{
////用n个m初始化
//vector<string> v1(10, "1111111");
//print_container(v1);
//vector<int> v2(10);
//print_container(v2);
//}
//void test_vector8()
//{
//vector<int> v3(10, 1);
//print_container(v3);
//}
void test_vector8()
{
vector<int> v3(10u, 1);
print_container(v3);
}
//void test_vector9()
//{
//vector<string> v;
//v.push_back("11111111111111111");
//v.push_back("11111111111111111");
//v.push_back("11111111111111111");
//v.push_back("11111111111111111");
//print_container(v);
//}
void test_vector9()
{
vector<string> v;
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
print_container(v);
v.push_back("11111111111111111");
print_container(v);
}
}
2、Test.cpp
#include "vector.h"
int main()
{//blue::test_vector0();
//blue::test_vector1();
//blue::test_vector2();
//blue::test_vector3();
//blue::test_vector4();
//blue::test_vector5();
//blue::test_vector6();
//blue::test_vector7();
//blue::test_vector8();
//blue::test_vector9();
return 0;
}
这里用了一个命名空间blue其目的是为了防止和C++标准库中的vector发生冲突，在类模板中的大型函数可以在类内声明类外定义(这里没有分开)，小型函数可以直接在类内定义。
八、结语
本篇到这里就结束了，主要讲了vector是怎么模拟实现的，希望对大家有些许帮助，祝大家天天开心！
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。