【C++/STL】vector的底层刨析和模拟实现
island1314 2024-07-24 14:05:02 阅读 89
✨ 生于火焰，落俗不可避免，但浪漫至死不渝 🌏
📃个人主页：island1314
🔥个人专栏：C++学习
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
目录
vector模拟实现完整代码：
1.vector成员变量
🍵构造函数
📘默认构造
📘拷贝构造
📘迭代器区间初始化
📘n个val构造
📘initializer_list构造
📘赋值运算符重载
2、有关容量和数据个数的函数
3、扩容reserve()
4、operate[]
5、析构函数
6、尾插push_back
7、迭代器
迭代器代码测试：
8、插入insert
9、删除erase
🍋课外知识点:
🍵结语
vector模拟实现完整代码：
<code>#pragma once
#include <assert.h>
namespace qian {
template<class T>
class vector
{
public:
typedef const T* const_iterator;
typedef T* iterator;
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//类模板的成员函数,迭代器区间初始化
//函数模板 -- 目的支持任意容器迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
//reserve(last - first);
while (first != last)
{
push_back(*first);
++first;
}
}
//n个val构造
vector(size_t n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象T()
{
reserve(n);
while(n--)
{
push_back(val);
}
}
//n个val构造，第一个参数为int类型
vector(int n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象T()
{
reserve(n);
while(n--)
{
push_back(val);
}
}
//initializer_list构造
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto e : il)
{
push_back(e);
}
}
//默认构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
// v2 (v1)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v) push_back(e);
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// v1 = v3
vector<T>& operator = (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
void reserve(size_t n) //开辟空间
{
if (n > capacity())
{
size_t oldsize = size(); //保存旧空间
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < oldsize; i++) //深拷贝,转移数据
{
tmp[i] = _start[i];
}
delete[] _start; //释放旧空间
}
_start = tmp; //新空间的起点
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
// 1、如果n小于当前的size，则数据个数缩小到n
if (n <= size())
{
_finish = _start + n;
return;
}
// 2、空间不够则增容
if (n > capacity()) reserve(n);
//3、将size扩大到n
iterator it = _finish;
iterator _finish = _start + n;
while (it != _finish)
{
*it = value;
++it;
}
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity); //扩容
}
*_finish = x; //插入数据
++_finish; //尾部指针后移
//insert(end(), x);
}
void pop_back(const T& x)
{
/*assert(size() > 0);
--_finish;*/
erase(--end());
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
//防止迭代器因为后面的扩容失效，所以要提前记录pos位置
size_t len = pos - _start;
//size_t len = size();
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len; //判断扩容之后os位置，防止野指针出现使迭代器失效
}
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 + 1;
while (it != _finish) //从pos + 1开始往前移动
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr; //相当于_a
iterator _finish = nullptr; //_a+size
iterator _end_of_storage = nullptr; //_a + capacity
};
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(4);
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//int* it = v1.begin();
// 封装
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//cout << typeid(it).name() << endl;
}
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
/*for (auto e : v1)
{
cout << e << " ";
}
cout << endl;*/
v1.insert(v1.begin(), 0);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
cout << "删除第一个位置：";
v1.erase(v1.begin());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
int x;
cin >> x;
// 没有x就不插入，有x的前面插入
vector<int>::iterator it = find(v1.begin(), v1.end(), x);
if (it != v1.end())
{
// insert以后it这个实参会不会失效？
//v1.insert(it, 1000); //有点问题
it = v1.insert(it, 1000);
// 建议失效后迭代器不要访问。除非赋值更新一下这个失效的迭代器
cout << *it << endl;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
int x;
cin >> x;
vector<int>::iterator it = find(v1.begin(), v1.end(), x);
if (it != v1.end())
{
it = v1.erase(it);
if (it != v1.end())cout << *it << endl;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4() //删除
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
int x;
cin >> x;
vector<int>::iterator it = find(v1.begin(), v1.end(), x);
if (it != v1.end())
{
//v1.erase(it); //挂掉
it = v1.erase(it);
if (it != v1.end()) //不加这句话删除最后一个元素会挂掉
cout << *it << endl; //帮助我们访问循环内的错误
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
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);
vector<int> v2(v1);
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v1 = v3;
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}
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);
vector<int> v2(v1.begin() + 1, v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
string s("hello");
vector<int> v3(s.begin(), s.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
// C++内置类型进行了升序，也有构造
int i = 0;
int j(1);
int k = int();
int x = int(2);
vector<string> v1(10);
vector<string> v2(10, "xxx");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3(10,1); //若没有迭代器函数区间匹配，可以将就运行
//vector <int> v3(10u, 1); //因为调用的是unsigned那个
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
vector<int> v4(10, 1);
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
class A
{
public:
//单参数隐式类型转换
A(int a1 = 0)
:_a1(a1)
, _a2(0)
{}
A(int a1, int a2) //多参数隐式类型转换
:_a1(a1)
, _a2(a2)
{}
private:
int _a1;
int _a2;
};
void test_vector8() //删除
{
//多参数隐式类型转换
//多参数隐式类型转换
A aa1(1, 1);
//A aa2 = (1, 1);
A aa2 = { 1, 1 }; // 多参数隐式类型转换
A aa9{ 2,2 }; //不要
A aa3(1);
A aa4 = 1;
A aa5(1);
A aa6 = { 1 }; //不要
A aa7{ 1 }; //不要
const A& aa8 = { 1,1 };
auto il1 = { 1,2,3,4,5,6 };
vector<A> v3 = {1, A(1),A(2,2),A{2,2},{1},{2,2} };
}
void test_vector9()
{
vector<string>v1;
v1.push_back("111111111");
v1.push_back("111111111");
v1.push_back("111111111");
v1.push_back("111111111");
v1.push_back("111111111");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
}
1.vector成员变量
在查看STL库里面vector的实现时，我们发现它是一个类模板并且定义了三个成员变量，分别是iterator start、iterator finish、 iterator end_of_storage用来标记开始，结束，以及总容量，对于vector来说其迭代器iterator就是T*，例如我们之前学习过的顺序表插入的是int类型的数据，所以对存放int类型的vector来说T*就是int*。
假设vector中已经有6个数据，我们来看看具体图片方便对成员变量进行理解
#include<iostream>
using namespace std;
namespace qian
{
template<class T>
class vector
{
public:
typedef T* iterator; //将T*typedef成iterator
private:
iterator _start = nullptr; //这里给缺省值
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
}
};
这里有两个需要注意的地方：
✨因为还没有写构造函数，所以成员变量那里先给缺省值，方便使用
✨这里将vector的实现都放在一个头文件下，放置多个文件可能会出现链接错误；并设置自己的命名空间，比如我这设置的就是 qian
🍵构造函数
📘默认构造
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
//上下等价
//vector() = default; //强制编译器生成默认的
📘拷贝构造
// v2 (v1)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v) push_back(e);
}
代码测试：
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);
vector<int> v2(v1);
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
📘迭代器区间初始化
//类模板的成员函数,迭代器区间初始化
//函数模板 -- 目的支持任意容器迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
//reserve(last - first);
while (first != last)
{
push_back(*first);
++first;
}
}
📘n个val构造
//n个val构造
vector(size_t n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象T()
{
reserve(n);
while(n--)
{
push_back(val);
}
}
//n个val构造，第一个参数为int类型
vector(int n, const T& val = T())//缺省值不能给0，因为T可能是string，所以给匿名对象
{
reserve(n);
while(n--)
{
push_back(val);
}
}
注意：之所以用两个类似的是因为编译器在匹配函数时vector<int> v1(4, 2);4和2都是int类型恰好和vector(InputIterator first, InputIterator last)这两个函数模板的参数匹配上了，而我们写的n个val初始化vector(size_t n, const T& val=T())第一个参数类型是size_t,第二个才可以隐式类型转换为int类型，没有迭代器区间初始化的函数匹配。
缺省值不能给0，因为T可能是string，所以给匿名对象T()
这里给的缺省参数是匿名对象
T()，而不是0，因为vector除了能存储int类型外还可以存储其他类型的数据比如string等.
代码测试：
void test_vector7()
{
vector<string> v1(10);
vector<string> v2(10, "xxx");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3(10,1); //若没有迭代器函数区间匹配，可以将就运行
//vector <int> v3(10u, 1); //因为调用的是unsigned那个
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
vector<int> v4(10, 1);
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
📘initializer_list构造
initializer_list是C++新增的一个类型，方便初始化，支持将花括号括起来的值initializer_list，initializer_list对象里面有两个指针，指向花括号里面值开始和结尾的下一个，并支持迭代器，所以可以使用范围for来遍历，当然这个要编译器支持将花括号传给它
//initializer_list构造
vector(initializer_list<T> il)
{
reserve(il.size());//size表示数据个数
for (auto i : il)
{
push_back(i);
}
}
代码测试：
void test_vector8() //initializer_list构造测试
{
//隐式类型转换
vector<int> v1({ 1,2,3,4,5 });
vector<int> v2 = { 6,7,8,9,10 };
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
}
📘赋值运算符重载
// v1 = v3
vector<T>& operator = (vector<T> v)
{
swap(v);
return *this;
}
这里使用传值传参，是实参的拷贝，所以我们将它与被赋值的对象交换后返回即可完成赋值，并且交换后形参生命周期结束就会自动调用析构函数释放原来的空间。
🥳🥳swap函数
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
代码测试：
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);
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v1 = v3;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
2、有关容量和数据个数的函数
//容量
size_t capacity() const
{
return _end_of_storage - _start;
}
//数据个数
size_t size()const
{
return _finish - _start;
}
3、扩容reserve()
void reserve(size_t n) //开辟空间
{
if (n > capacity())
{
size_t oldsize = size(); //保存旧空间
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * size()); //memcpy 进行的是浅拷贝
for (size_t i = 0; i < oldsize; i++) //深拷贝,转移数据
{
tmp[i] = _start[i];
}
delete[] _start; //释放旧空间
}
_start = tmp; //新空间的起点
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
扩容时，因为我们使用的实现vector类的成员变量是指针(或者说迭代器)，所以改变空间后不仅仅_start改变，_finish指向的空间会被销毁，所以这时候如果再使用扩容后的_finish-_start来找到容量size来确定现在_finish指向的空间肯定是不对的，所以我们要提前记录好oldsize。
值得注意的是：我们避免了使用memcpy的浅拷贝，使用的是深拷贝。
这是因为我们在使用reserve()扩容时，使用的是 memcpy(tmp, _start, oldsize*sizeof(T)); 来拷贝数据，如果数据是int类型不会有什么问题，但如果是string类，memcpy进行的是一个字节一个字节拷贝，是浅拷贝，释放原来的空间后，就会存在野指针，访问已经释放的空间出现错误
🥳🥳有关resize的函数
void resize(size_t n, const T& value = T())
{
// 1、如果n小于当前的size，则数据个数缩小到n
if (n <= size())
{
_finish = _start + n;
return;
}
// 2、空间不够则增容
if (n > capacity()) reserve(n);
//3、将size扩大到n
iterator it = _finish;
iterator _finish = _start + n;
while (it != _finish)
{
*it = value;
++it;
}
}
4、operate[]
这里获得的是vector里面存储的数据
T& operator[](size_t i) // 1
{
assert(i < size());
return _start[i];
}
//const对象使用
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
5、析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
6、尾插push_back
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; //判断需要扩容空间
reserve(newcapacity); //扩容
}
*_finish = x; //插入数据
++_finish;//尾部指针后移
}
7、迭代器
//普通迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//提供给const对象使用的迭代器，指向的内容不可以被修改
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
在最开始vector成员变量那里我们将T*typedef成iterator，所以对于vector类来说其迭代器实质上就是
T*，是一个指针；但要注意不是所有的迭代器都是指针，例如list的迭代器就不是，我们后续再学习。
迭代器代码测试：
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(4);
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
//迭代器遍历
//int* it = v1.begin();
// 封装
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//cout << typeid(it).name() << endl;
//for循环遍历，实质上就是通过迭代器来实现的
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
8、插入insert
<code>iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
//防止迭代器因为后面的扩容失效，所以要提前记录pos位置
size_t len = pos - _start;
//size_t len = size();
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len; //判断扩容之后os位置，防止野指针出现使迭代器失效
}
iterator end = _finish - 1; //后移
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
这里要注意迭代器因为扩容导致pos失效的问题(野指针)，所以要提前规避，记录好pos相对位置，然后再即时更新pos迭代器，否则就会出现随机值;
此外，insert的参数pos是对实参的拷贝，形参的改变不会影响实参，所以外部的实参也会失效，但是我们也不能通过引用传参，因为其迭代器返回的是临时拷贝具有常性不能通过引用传参，所以这里我们就可以通过控制insert函数的返回值来解决，我们会返回更新后的迭代器，这样就可以访问该位置了。
🥳🥳有了插入函数之后尾插push_back()就可以使用insert()来实现啦，代码如下：
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
9、删除erase
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish) //从pos + 1开始往前移动
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
erase()之后迭代器失效问题
有可能删除之后缩容删除最后一个位置会导致越界访问
所以我们认为删除操作之后迭代器也会失效，和插入函数一样通过返回迭代器来更新迭代器使用才行
插入删除代码测试
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.insert(v1.begin(), 0);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
cout << "删除第一个位置：";
v1.erase(v1.begin());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
int x;
cin >> x;
// 没有x就不插入，有x的前面插入
vector<int>::iterator it = find(v1.begin(), v1.end(), x);
if (it != v1.end())
{
// insert以后it这个实参会不会失效？
//v1.insert(it, 1000); //有点问题
it = v1.insert(it, 1000);
// 建议失效后迭代器不要访问。除非赋值更新一下这个失效的迭代器
cout << *it << endl;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
if (it != v1.end())
{
it = v1.erase(it);
if (it != v1.end())cout << *it << endl;
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
🍋课外知识点:
💎1、vector底层是以当前类型的指针作为迭代器，对于指针而言，能够进行操作的方法都支持，如==,++,*，而>>运算符并没有重载。
💎2、在vs系列编译器中，debug模式下，关于std::vector::at 和 std::vector::operator[] :
debug模式 at() 和 operator[] 都是根据下标获取任意位置元素的，在debug模式下两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 内部的assert会触发
💎3、vector的插入操作如果导致底层空间重新开辟，则迭代器就会失效。如果空间足够，不扩容时，迭代器不一定失效，比如push_back尾插，元素插入到空间末尾，在不扩容时不会对迭代器产生影响。
💎4、vector删除，若当前元素迭代器失效，后面元素会牵扯到移动数据，因此删除元素后面的迭代器也会失效。
🍵结语
以上就是C++STL标准库中vector的模拟实现了，在实现过程中，我们使用了动态内存分配来实现vector的大小动态调整，并通过指针来管理内存。我们还实现了一些常用的成员函数，如push_back、pop_back、at等，以及一些运算符重载，如[]、=等。
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。