【C++初阶】vector模拟实现
悦心无谓 2024-10-01 15:05:02 阅读 93
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
🍋vector模拟实现
🍑默认成员函数🍍构造函数🍍拷贝构造函数🍍析构函数🍍赋值重载函数
🍑迭代器🍑增删查改功能实现🍍增加数据🍍删除数据🍍查找数据🍍改变数据🍍其它程序
🍑vector模拟整体代码
🍑默认成员函数
🍍构造函数
<code>//默认构造
vector()
{ -- -->}
//带参构造
vector(size_t x, const T& val = T())
{
resize(x, val);
}
......
对于带参构造当中，第二个参数，所采用的是匿名对象作为缺省值；因为在这里T的的类型不确定，只能使用匿名对象来修饰。
匿名对象：指的是没有被显式命名（即没有标识符或变量名）的对象实例。这类对象通常在需要临时执行某些操作或作为函数参数/返回值传递时创建，而不需要将结果长期存储于某个变量中。
此处的构造只涉及到浅拷贝，对于深拷贝后面会有介绍。
🍍拷贝构造函数
//拷贝构造(普通写法)
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
//拷贝构造(实用写法)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& in : v)
{
push_back(in);
}
}
//现代写法
vector(vector<T>& v)
{
vector<T> ret(v.begin(), v.end());
swap(ret);
}
此处的拷贝构造函数就涉及到深拷贝问题，这里我提供了三种写法。
(1)第一种写法就是普通的写法，相信大家自己来模拟拷贝构造，思路大径相同；这里还用到了memmove()函数， 大家也可以采用while()循环的方式来代替，方法多种多样。
(2)第二种写法就是利用vector的插入完成，不过需要提前开满足够的空间，不然内存会泄露。
(3)第三种写法利用swap的特性。
🍍析构函数
//iterator _start = nullptr;
//iterator _finish = nullptr;
//iterator _endofstorage = nullptr;
~vector()
{
if(_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}
析构函数还是常规写法，没有什么特别之处。
_start、_finish、_endofstorage是vector的迭代器。_start是指向头；_finish是数据存储大小的尾;_endofstorage是整个空间大小的尾。
🍍赋值重载函数
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
_finish = _start + v.size();
}
return *this;
}
//优化写法
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
在进行赋值重载操作时，可以先对数据进行对比，如果相同就不用再进行此操作。
赋值重载需要注意的是优化写法中在参数中没有采用引用的写法，swap()函数是把两处的内容完全交换，而我们在这里仅仅只需要赋值，所以我在这里并对v采用引用的写法，如果对v采用引用的写法可能会把原有的v中数据破坏，未被引用的v仅仅只是原来v中数据的拷贝，虽然它俩名字相同，但作用域不同。
🍑迭代器
无论是范围for还是方括号进行遍历，底层原理都是迭代器,迭代器有两种版本，有const版本和非const版本；迭代器写法还是直接调用子函数进行实现。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
🍑增删查改功能实现
🍍增加数据
reserve()函数是扩容函数，capacity()函数是算出实际空间的大小，还额外使用了memcpy()函数进行了拷贝，这里之所以扩容在if条件下进行，是因为我们不仅仅是在插入数据的时候才用到扩容函数，比如赋值等等。
这里还有一点需要注意，需要在_start空间释放前把实际数据的长度先保存，在这实际长度的计算是采用_finish-_start的长度，当我们已经释放_start，再次使用size()函数时，_start和_finish不在同一个物理量上，程序会报错，如下图：
<code>void reserve(size_t n)
{ -- -->
if (n > capacity())
{
size_t len = size();
T* tem = new T[n];
if (_start)
{
memcpy(tem, _start, len * sizeof(T));
delete[] _start;
}
_start = tem;
_finish = _start + len;
_endofstorage = _start + n;
}
}
push_back()是尾插函数的实现，开头还是得先判断空间是否溢出再进行判断；_finish是实际数据大小的尾，_endofstorage是空间实际的大小，当这两者相等，空间就会溢出。reserve()函数是扩容函数。
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
Insert()函数是插入函数，在pos位置插入新的数据，还使用了memmove()函数进行了数据的移动，当然也可以使用while()和for()这两个也可以，看大家对那个熟悉就用那个。
首先还是要先对pos位置进行判断，防止提供的pos位置有误；再用_finish与_endofstorage进行对比来判断空间是否溢出,是否需要扩容；最后再把pos位置往后的整体数据往后移一步，把新的数据插入pos位置即可。
void Insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
*pos = x;
++_finish;
}
🍍删除数据
erase()函数是删除数据的函数。首先还是对题目提供的pos进行判断，我在这里就没有采用memmove()函数进行数据的移动，还是因为memmove()函数在删除末尾数据时有点问题，最后我还是采用while()循环来实现数据的移动。
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}
pop_back()函数是尾删数据的函数，实现方式也是直接把_finish减一个数就可以，主要还是_finish是指向该数据的尾.
void pop_back()
{
assert(size() > 0);
--_finish;
}
🍍查找数据
Find()函数是查找数据。实现方式也是利用迭代器进行遍历查找。
bool Find(T x)
{
iterator pos = _start;
while (pos <= _finish)
{
if (*pos == x) return true;
++pos;
}
return false;
}
🍍改变数据
resize()函数是利用空间的性质对数据进行扩容和删除，也就是它既具有扩容的功能，又有删除的功能，还有增加数据的功能，只不过增加的是默认值0。
参数中的T由于不确定类型所以采用的是匿名对象的缺省参数。该函数大家可以很少用到，下面是程序运行图：
<code>void resize(size_t n, T val = T())//匿名对象的缺省值
{ -- -->
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
🍍其它程序
size()函数是计算实际数据大小，capacity()函数是计算实际空间的大小，当实际数据大小等于实际空间的大小，该空间就满了，再往里插入新数据，空间就会溢出。
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
operator函数是方便该类数据可以使用方括号进行遍历，也就是数组的方式进行遍历。也是有两个版本，一个是const类，另一个是非const类。
T& operator[](const T& pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](const T& pos) const
{
assert(pos < size());
return _start[pos];
}
🍑vector模拟整体代码
#include<iostream>
#include<assert.h>
using namespace std;
namespace ciking
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
{ }
//拷贝构造(普通写法)
/*vector(const vector<T>& v)
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}*/
//拷贝构造(实用写法)
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& in : v)
{
push_back(in);
}
}
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()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t len = size();
T* tem = new T[n];
if (_start)
{
memcpy(tem, _start, len * sizeof(T));
delete[] _start;
}
_start = tem;
_finish = _start + len;
_endofstorage = _start + n;
}
}
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
void Insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
*pos = x;
++_finish;
}
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//memmove(pos, pos + 1, sizeof(T) * (_finish - pos));
//--_finish;
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}
bool Find(T x)
{
iterator pos = _start;
while (pos <= _finish)
{
if (*pos == x) return true;
++pos;
}
return false;
}
void resize(size_t n, T val = T())//匿名对象的缺省值
{
if (n > size())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
T& operator[](const T& pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](const T& pos) const
{
assert(pos < size());
return _start[pos];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void print_vector(const vector<int>& v)
{
for (auto in : v)
{
cout << in << " ";
}
cout << endl;
}
void test_vector1()
{
vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);
vv.push_back(4);
vector<int>::iterator it = vv.begin();
while (it != vv.end())
{
cout << *it << " ";
it++;
}
cout << endl;
vv.erase(vv.end());
for (auto in : vv)
{
cout << in << " ";
}
cout << endl;
for (size_t i = 0; i < vv.size(); i++)
{
cout << vv[i] << " ";
}
cout << endl;
vv.Insert(vv.begin(), 100);
print_vector(vv);
vector<int> v2;
v2.push_back(100);
v2.push_back(120);
v2.push_back(130);
v2.push_back(140);
vv = v2;
for (size_t i = 0; i < vv.size(); i++)
{
cout << vv[i] << " ";
}
cout << endl;
}
void test_vector2()
{
vector<int> v1;
v1.push_back(100);
v1.push_back(110);
v1.push_back(120);
v1.push_back(130);
v1.push_back(140);
v1.push_back(150);
v1.push_back(160);
v1.push_back(170);
v1.push_back(180);
v1.push_back(190);
v1.push_back(200);
cout << "原有数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
v1.resize(15);
cout << "resize(15)空间变大后的数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
v1.resize(8);
cout << "resize(8),空间变小的数据:";
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
}
}
int main()
{
ciking::test_vector2();
return 0;
}
关于本章知识点如果有不足或者遗漏，欢迎大家指正，谢谢！！！
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。