C++ ─── vector的模拟实现
一码归—码 2024-06-30 15:35:02 阅读 93
知识点：
① 因为vector是模版，所以声明和定义都放在.h中，防止出现编译错误。
.h不会被编译，在预处理中.h在.cpp中展开，所以在编译时只有.cpp
而 .cpp顺序编译，只会进行向上查找，因此至少有函数的声明。
②memcpy的复习
memcpy(dest , source,大小)
③ 拷贝构造也是构造函数（拷贝构造函数我们必须写，我们写的是深拷贝）
但是有了拷贝构造函数，编译器就不会自己生成构造函数了，
因为拷贝构造也是构造函数的一种，所以要强制生成
强制编译器生成默认的构造函数,使用参数的缺省值生成默认构造函数，需要使用以下命令
vector() = default;
④拷贝构造函数和赋值重载函数的现代写法，
拷贝构造：利用直接push_back
赋值重载：利用实参传形参时的拷贝构造（vector<T> x），直接改名。
⑤扩容之后和erase后，迭代器失效问题，需要及时更新。
迭代器失效：1. 野指针 2. 越界访问
⑥find 函数在算法库，找不到就返回最后的迭代器。
目录
vector.h
test.cpp
从图中我们可以看出，vector的操作机制实际上是通过三个指针来实现的：
_startv _finish _end_of_storage
所以vector的基本成员变量为：
因为vector的本质上是顺序表容器，只是存储的数据上变的更加多元化了，所以我们可以对基本成员做一些调整，将其改成迭代器相关的，方便我们后面写类成员函数。
//命名一个命名空间，在这个命名空间中实现我们自己的vector，这样能避免受库中vector的影响
namespace bmh
{
template<class T>
class vector
{
public:
//迭代器的实现
typedef T* iterator;
typedef const T* const_iterator;
private:
private:
iterator _start = nullptr;//头
iterator _finish = nullptr;//存储内容的尾
iterator _end_of_storage = nullptr;//存储空间的尾部
};
接下来，我们就开始进入今天的正题，模拟vector的五大步骤：
1、构造和销毁
2、迭代器相关
3、容量相关
4、元素访问
5、vector的修改操作
vector.h
#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
namespace bmh
{
template<class T>
class vector
{
public:
// 2、迭代器相关
//迭代器的实现
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;
}
size_t size()const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
// 1、构造和销毁
//用迭代器区间构造函数
//vector<int> v2(v1.begin() + 1, v1.end());
//函数模板，写的不是iterator ，目的支持任意容器的迭代器 eg: list<int>的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//构造函数
//vector()
//:_start(nullptr)
//,_finish(nullptr)
//,_end_of_storage(nullptr)
//{}
// 拷贝构造也是构造函数（拷贝构造函数我们必须写，我们写的是深拷贝）
// 但是有了拷贝构造函数，编译器就不会自己生成构造函数了，
//因为拷贝构造也是构造函数的一种，所以要强制生成
// 强制编译器生成默认的构造函数,使用参数的缺省值构造
vector() = default;
//n个value的构造函数
//vector(10,10)
// C++对内置类型也补充了内置类型的构造函数,看下面的test5中j=0
// std::string s1("c");
//vector(20,s1)
vector(size_t n, const T& value = T())//T()代表用默认构造函数生成的匿名对象
{
reserve(n);//提高效率
for (size_t i = 0; i < n; i++)
{
push_back(value);
}
}
//但是上面这个函数会有一个特殊情况出现
//例如对于vector<int>v4(10, 1);
//由于v中的参数是(int，int)，所以编译器容易把它与迭代器相关的函数去配对
//所以对于上面这个函数我们又写了一个vector(int n, const T& m = T())类型的来避免错误发生
//这种情况下参数一定都为int型的，所以我们可以按顺序表的方式来写这个函数
//解决编译器的选择问题
vector(int n, const T& value = T())
{
reserve(n);//提高效率
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
//拷贝构造函数
//vector<int> v3(v2);
vector(const vector<T>& v2)
{
reserve(v2.capacity());
for (auto e: v2)
{
push_back(e);
}
}
//赋值重载函数（利用形参时的拷贝构造生成的临时对象）
//v3= v2;
vector<T>& operator=( vector<T> v)//v是v2的临时拷贝，只需要将v3变成v即可（现代写法）
{
swap(v);
return *this;
}
//析构函数
~vector()
{
if (_start)
{
delete[]_start;
_start = _finish = _end_of_storage = nullptr;
}
}
//3、容量相关
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
if (_start)//不为空，拷贝原数据
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
_finish = tmp + old_size;//更新_finish
_end_of_storage = tmp + n;
}
}
void resize(size_t n, const T& value = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
if (capacity() < n)
{
reserve(n);
}
while (size() < n)
{
push_back(value);
}
}
}
//4、元素访问
T& operator[](size_t i)
{
assert(i < size());
assert(i >= 0);
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
assert(i >= 0);
return _start[i];
}
//5、vector的修改操作
void push_back(const T& x)
{
if (capacity() == size())
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
_start[size()] = x;//*_finish =x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//在pos位置之前插入X
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);//不要忘了断言
assert(pos <= _finish);
if (_finish == _end_of_storage)//扩容会导致迭代器失效，要去更新pos
{
size_t length = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + length;
}
iterator it1 = _finish;
while (it1 != pos)//挪动数据
{
*(it1) = *(it1 - 1);
--it1;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)//返回擦出后的下一个
{
assert(pos >= _start);
assert(pos < _finish);
size_t len = pos - _start;
iterator it2 = pos;
while (it2 < _finish)
{
*(it2) = *(it2 + 1);
++it2;
}
--_finish;
if (size() > 0)
{
return _start + len;
}
else
{
return nullptr;
}
}
private:
iterator _start = nullptr;//头
iterator _finish = nullptr;//存储内容的尾
iterator _end_of_storage = nullptr;//存储空间的尾部
};
void test1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
v1.push_back(7);
v1.push_back(8);
v1.push_back(9);
for (auto e: v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity()<< std::endl;
v1.resize(12,666);
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
v1.resize(6);
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
v1.pop_back();
v1.pop_back();
v1.pop_back();
v1.pop_back();
v1.pop_back();
v1.pop_back();
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
/*v1.pop_back();*/
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
}
void test2()
{
vector<int> v1;
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
v1.insert(v1.begin(), 10);
v1.insert(v1.end(), 20);
v1.insert(v1.end(), 30);
v1.insert(v1.end(), 40);
v1.insert(v1.end(), 50);
v1.insert(v1.end(), 60);
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;
v1.erase(v1.end()-1);
v1.erase(v1.end()-1);
int* it = v1.erase(v1.begin());
std::cout << *it;
/*for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::cout << v1.size() << " " << v1.capacity() << std::endl;*/
}
void test3()
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
vector<int> v2;
v2 = v1;
for (auto e : v2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void test4()
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
vector<int> v2(v1.begin() + 1, v1.end());
for (auto e : v2)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void test5()
{
int x = 0;
int k = int();
int j(10);
std::cout << x << " " << j << " " << k << std::endl;
}
void test6()
{
std::string s1("c");
vector<std::string> v1(5);//第二个参数省略，用缺省值
vector<std::string>v2(5, s1);
vector<std::string>v3(5, "aa");
//vector<std::string>v3(5, 1);会报错，系统认为与template<class InputIterator>更匹配
//vector(InputIterator first,InputIterator last)
vector<int> v4((size_t)5, 1);//5u指的是unsigned_int
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
for (auto e : v2)
{
std::cout << e << " ";
}
std::cout << std::endl;
for (auto e : v3)
{
std::cout << e << " ";
}
std::cout << std::endl;
for (auto e : v4)
{
std::cout << e << " ";
}
std::cout << std::endl;
vector<int> v5(10, 1);
for (auto e : v5)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
}
test.cpp
#include"vector.h"
int main()
{
bit::test6();
return 0;
}
这个博客如果对你有帮助，给博主一个免费的点赞就是最大的帮助❤
欢迎各位点赞，收藏和关注哦❤
如果有疑问或有不同见解，欢迎在评论区留言哦❤
后续我会一直分享双一流211西北大学软件（C，数据结构，C++，Linux，MySQL）的学习干货以及重要代码的分享
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。