【C++】vector及模拟实现
小羊在奋斗 2024-08-16 08:35:03 阅读 68
🚀个人主页：奋斗的小羊
🚀所属专栏：C++
很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~
目录
💥1、vector的主要函数接口💥2、vector的模拟实现💥2.1 构造和析构💥2.2 vector属性相关函数💥2.3 运算符重载💥2.3.1 赋值重载💥2.3.2 [ ] 重载
💥2.4 vector的打印💥2.5 扩容💥2.5.1 深拷贝中的浅拷贝问题
💥2.6 迭代器失效的问题💥2.6.1 插入和删除💥扩容形成野指针💥挪动数据位置意义改变
💥2.7 调整大小
💥3、vector模拟实现完整代码
💥1、vector的主要函数接口
<code>namespace yjz
{ -- -->
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默认构造
vector()
{ }
//拷贝构造
vector(const vector<T>& v)
{ }
//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{ }
//指定n个值构造
vector(size_t n, const T& val = T())
{ }
vector(int n, const T& val = T())
{ }
//析构
~vector()
{ }
//交换数据
void swap(vector<T>& tmp)
{ }
//清理数据
void clear()
{ }
传统写法
//vector<T>& operator=(const vector<T>& v)
//{}
//现代写法
vector<T>& operator=(vector<T> tmp)
{ }
size_t size() const
{ }
size_t capacity() const
{ }
//迭代器
iterator begin()
{ }
iterator end()
{ }
const_iterator begin() const
{ }
const_iterator end() const
{ }
//【】重载
T& operator[](size_t i)
{ }
const T& operator[](size_t i) const
{ }
//判空
bool empty()
{ }
//尾删
void pop_back()
{ }
//扩容
void reserve(size_t n)
{ }
//尾插
void push_back(const T& n)//可能插入类等
{ }
//插入
iterator insert(iterator pos, const T& n)
{ }
//删除
iterator erase(iterator pos)
{ }
//调整大小
void resize(size_t n, T val = T())
{ }
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template<class T>
void print_vector(const vector<T>& v)
{ }
}
💥2、vector的模拟实现
💥2.1 构造和析构
虽然vector使用编译器生成的默认构造就行，但是我们还需要写拷贝构造，有了构造函数编译器就不会生成默认构造了，所以可以在形式上写个默认构造类模版的成员函数，还可以继续是函数模版
//默认构造
vector()
{ }
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//指定n个值构造
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
💥2.2 vector属性相关函数
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
💥2.3 运算符重载
💥2.3.1 赋值重载
赋值重载可以借助swap函数，需要注意的是形参必须传值
void swap(vector<T>& tmp)
{
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}
//现代写法
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
💥2.3.2 [ ] 重载
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
💥2.4 vector的打印
为了方便打印vector中不同类型的数据，可以将迭代器遍历和范围for遍历封装成一个模版函数，有几点需要注意：
模版参数只能给当前的函数或者类使用函数采用const引用传参，避免拷贝，迭代器也要保持一致使用const_iterator没有实例化的类模版里面取东西，编译器不能区分这里的const_iterator是类型还是静态成员变量，从属名称的使用必须以typename为前缀当然最省事的还是auto
template<class T>
void print_vector(const vector<T>& v)
{
//typename vector<T>::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;
}
💥2.5 扩容
💥2.5.1 深拷贝中的浅拷贝问题
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
_start = tmp;
//_finish = _start + size();
_finish = _start + old_size;//_finish也要更新
_end_of_storage = _start + n;
}
}
上面是以前扩容的常规操作，但是在这里有些潜在的问题：
void test_vector7()
{
vector<string> v1;
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
print_vector(v1);
}
当我们在不扩容的情况下在<code>vector中插入string类，不会出现什么问题，但如果扩容的话，就会出现问题：
这里的问题在扩容的过程中<code>memcpy是按字节拷贝的（浅拷贝），而string类中还有_str指向一块空间，memcpy将string类中的所有数据都浅拷贝到tmp指向的空间中，tmp中的_str指向的还是原来的空间，释放旧空间时其中的string类会自动调用析构函数，释放掉_str指向的空间，最后tmp空间中的_str指向的就是非法空间。
要想解决这个问题也简单，用深拷贝来代替<code>memcpy的浅拷贝，可以考虑赋值重载，因为 string类的赋值重载是深拷贝：
void reserve(size_t n)
{ -- -->
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
//_finish = _start + size();
_finish = _start + old_size;//_finish也要更新
_end_of_storage = _start + n;
}
}
💥2.6 迭代器失效的问题
💥2.6.1 插入和删除
💥扩容形成野指针
在指定位置插入一个数据，首先要判断vector是否满了，如果满了调用reserve扩容。插入前还需要挪动指定位置之后的数据，最后插入数据，++_finish。
void insert(iterator pos, const T& n)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = n;
++_finish;
}
这是常规的插入方法，和string类插入一个字符一样。但是当我们插入一个数据需要扩容时，编译运行就会陷入死循环。
原因是虽然扩容后<code>_start、_finish、_end_of_storage都更新了，但是pos指向的还是原来的位置。
所以我们需要在扩容后将pos的指向也更新一下：
void insert(iterator pos, const T& n)
{ -- -->
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = n;
++_finish;
}
💥挪动数据位置意义改变
假如我们想在某个数据前面插入但是不知道具体位置，则需要先查找到这个数据的地址：
int n;
cin >> n;
auto pos = find(v.begin(), v.end(), n);
if (pos != v.end())
{
v.insert(pos, 40);
*pos += 100;
}
print_vector(v);
如果没有扩容，<code>pos原本指向的数据是我们要查找的3，但是在我们往3的前面插入一个40后，pos指向的数据就变了，这也被认为是迭代器失效；如果扩容，则就是上面讲的pos变成野指针。
和vector类似，string在插入+扩容操作+erase后，迭代器也会失效所以不管扩不扩容， insert后pos就失效，不要直接访问，要访问就要更新迭代器的值。
可以在insert函数最后返回pos的值：
iterator insert(iterator pos, const T& n)
{ -- -->
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = n;
++_finish;
return pos;
}
int n;
cin >> n;
auto pos = find(v.begin(), v.end(), n);
if (pos != v.end())
{
pos = v.insert(pos, 40);
*(p + 1) += 100;
}
print_vector(v);
同样的删除也会使迭代器失效：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
删除vector中任意位置的数据，VS都认为该位置迭代器失效
💥2.7 调整大小
为了兼容类类型给缺省值的情况，内置类型也有了构造函数的概念。
<code>void resize(size_t n, T val = T())
{ -- -->
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);//大了才扩容
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
💥3、vector模拟实现完整代码
vector.h:
#pragma once
#include <iostream>
#include <assert.h>
#include <string>
using namespace std;
namespace yjz
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默认构造
vector()
{ }
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//指定n个值构造
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
void swap(vector<T>& tmp)
{
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}
void clear()
{
_finish = _start;
}
传统写法
//vector<T>& operator=(const vector<T>& v)
//{
//if (this != &v)
//{
//clear();
//reserve(v.size());
//for (auto e : v)
//{
//push_back(e);
//}
//}
//}
//现代写法
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
bool empty() const
{
return _start == _finish;
}
void pop_back()
{
assert(!empty());
_finish--;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
//_finish = _start + size();
_finish = _start + old_size;//_finish也要更新
_end_of_storage = _start + n;
}
}
void push_back(const T& n)//可能插入类等
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = n;
++_finish;
}
iterator insert(iterator pos, const T& n)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = n;
++_finish;
return 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;
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template<class T>
void print_vector(const vector<T>& v)
{
//typename vector<T>::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;
}
}
test.cpp:
#define _CRT_SECURE_NO_WARNINGS
#include "vector.h"
namespace yjz
{
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);
print_vector(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_vector(v);
v.insert(v.begin() + 2, 10);
print_vector(v);
}
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);
int n;
cin >> n;
auto pos = find(v.begin(), v.end(), n);
if (pos != v.end())
{
pos = v.insert(pos, 40);
*(pos + 1) += 100;
}
print_vector(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);
print_vector(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
print_vector(v);
}
void test_vector5()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
print_vector(v);
v.resize(3);
print_vector(v);
v.resize(8, 1);
print_vector(v);
}
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(10, 1);
print_vector(v2);
vector<int> v3(v2.begin() + 1, v2.begin() + 5);
print_vector(v3);
}
void test_vector7()
{
vector<string> v1;
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
print_vector(v1);
}
}
int main()
{
//yjz::test_vector1();
//yjz::test_vector2();
//yjz::test_vector3();
//yjz::test_vector4();
//yjz::test_vector5();
//yjz::test_vector6();
yjz::test_vector7();
return 0;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。