C++模拟实现STL容器vector的示例代码
蒋灵瑜的笔记本 人气:1一、vector迭代器失效问题
1、Visual Studio和g++对迭代器失效问题的表现
int main(){
std::vector<int>v{1,2,3,4};
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 2);
if(it != v.end())
{
v.erase(it);
it++;//调用erase()后，it已经失效了，运行后迭代器引发异常
}
return 0;
}在Visual Studio2022中，调用vector的insert()和erase()接口后，it迭代器（包括it之后的自定义迭代器）将会失效，如果仍操作这些已经失效的迭代器，编译器将会引发异常。
博主尝试在Linux的g++编译器（4.8.5版本）下运行相同debug版本的程序（编译时带上-g选项），发现g++中调用完insert()和erase()接口后，it迭代器并未失效，甚至可以操纵it读写_end_of_storage-_finish这部分空间，这是不安全的。
所以，后续调用完insert()和erase()接口后，我们一律认为当前迭代器失效！
2、解决迭代器失效的方法
int main(
std::vector<int> v{1,2,3,4};
std::vector<int>::iterator it = std: :find(v.begin(), v. end(),2);
if(it != v.end())
{
it=v.erase(it);//让当前迭代器接收erase的返回值，更新迭代器
it++;
}
return 0;
}使用时让当前迭代器接收insert()和erase()的返回值，更新迭代器即可。
二、模拟实现构造函数调用不明确
1、问题描述
vector(size_t n, const T& val = T())//这里的形参用size_t就会引发这两个构造函数调用问题
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
本意是想使用第一种构造方式，用3个6进行构造。编译器会根据形参调用最匹配的函数重载。
第一个构造函数的第一个形参是size_t，形参去匹配的话需要发生隐式类型转换。
但是这两个参数更匹配第二个构造函数（因为第二个模板可以为int，完全匹配），一旦走第二个构造函数，该构造函数内部是要对first进行解引用操作，所以编译器会报非法的间接寻址（解引用）错误。
2、解决调用不明确的方法
针对构造函数vector(size_t n, const T& val = T())，我们多重载一个vector(int n, const T& val = T())版本的构造函数即可解决该问题。
三、reserve中的深浅拷贝问题
1、reserve中浅拷贝发生原因
这句memcpy表面上把原来的数据全部拷贝到tmp里面了，但是，这只是按字节的拷贝，如果当前类型为vector<vector<int>>等非内置类型，将会发生浅拷贝。
2、浅拷贝发生的图解
memcpy会把vector<vector<int>>,从_start位置开始，按字节进行拷贝。如图所示，拷贝的对象是4个vector<int>,这是是一种浅拷贝！
3、解决方法
void reserve(size_t n)
{
//扩容
if (n > capacity())
{
size_t oldSize = size();//先记录下size,后续解决finish失效
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;//异地扩容后_finish失效，需重新设定_finish
_end_of_storage = _start + n;
}
}借助赋值运算符重载，完成深拷贝。
四、模拟实现vector整体代码
#pragma once
#include <iostream>
#include <assert.h>
using std::cout;
using std::cin;
using std::endl;
namespace jly
{
template <class T>
class vector
{
public:
//构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())//多重载一个int版本的构造，解决调函数不明确的问题
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first++);
}
}
//拷贝构造
void swap(vector<T>& v)//一定要加引用，不然拷贝构造函数调用swap会引发无限拷贝
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//vector(const vector<T>& v)//写法二
// : _start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{
// reserve(v.capacity());
// for (const auto& e : v)
// {
// push_back(e);
// }
//}
//赋值运算符重载
vector<T>& operator=(vector<T> v)//能解决自己给自己赋值的问题
{
swap(v);
return *this;
}
//析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
//迭代器
typedef T* iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const iterator begin()const
{
return _start;
}
const iterator end()const
{
return _finish;
}
T& operator[](size_t pos)
{
return _start[pos];
}
const T& operator[](size_t pos)const
{
return _start[pos];
}
//reserve接口
void reserve(size_t n)
{
//扩容
if (n > capacity())
{
size_t oldSize = size();//先记录下size,后续解决finish失效
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;//异地扩容后_finish失效，需重新设定_finish
_end_of_storage = _start + n;
}
}
//resize接口
void resize(size_t n, T val = T())//val给T类型的缺省值
{
if (n > capacity())//n大于capacity，要扩容
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else if (n > size())//n小于capacity但大于原size
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else//缩size的情况
{
_finish = _start + n;
}
}
//push_back/pop_back接口
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
}
*_finish = val;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
//insert和erase接口
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
//判断扩容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;//需要处理pos迭代器失效问题，记录len
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);//扩容后pos迭代器失效
pos = _start + len;//重新设定pos
}
//挪动数据
for (iterator i = _finish; i > pos; --i)
{
*i = *(i - 1);
}
//填入数据
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
for (iterator i = pos; i < _finish - 1; ++i)
{
*pos = *(pos + 1);
}
--_finish;
return pos;
}
//小接口
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
bool empty()const
{
return _start == _finish;
}
void clear()
{
_finish = _start;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
/测试部分
void test()
{
vector<int> v(1, 5);
vector<int> v1(v);
for (auto e : v1)
{
cout << e << " ";
}
}
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][vv[i].size() - 1] = 1;
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
return vv;
}
};
void test_vector()
{
vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}加载全部内容