目录
一,框架设计
二,构造函数
三,析构函数
四,赋值运算符
五,容器接口的实现
1,迭代器实现
2,“ [] ”运算符的实现
3,swap交换和resize重设大小
4,insert插入和erase删除
介绍:
本文,我们重点实现vector容器的用法,这里要注意的是vector容器可以接纳任意类型,所以,在实现的时候需使用模板来控制。模拟实现vector重点还要放在构造、析构和赋值运算符重载。
一,框架设计
vector容器设置中,由于需要接纳各种类型,因此,在框架设计中需要使用模板。除此之外,要想访问未知类型数据,需要使用迭代器来访问。这里,我们设置三个迭代器,分别指向数据块开始位置、有效数据的末尾、存储容量的末尾。
template<class T>
class vector
{
public:
typedef T* iterator; //数据迭代器
typedef const T* const_iterator; //常量迭代器
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
二,构造函数
在使用构造函数之前,我们首先要考虑基础的算法设置以方便使用:reverse扩容、capacity容器容量、size容器大小、push_back增添元素、pop_back删除元素。
//获取容器大小
size_t size() const
{
return _finish - _start;
}//获取容器容量
size_t capacity() const
{
return _endOfStorage - _start;
}//容器扩容
void reserve(size_t n)
{
if (n > capacity()) //只能增容不能缩小
{
int newsize = size();
T* tem = new T[n];
memcpy(tem, _start, sizeof(T) * newsize);
if (_start)
{
delete[] _start;
}
_start = tem;
_finish = _start + newsize;
_endOfStorage = _start + n;
}
}//增添数据
void push_back(const T& x)
{
if (capacity() == size()) //这里要注意容量是否够用
{
int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
int newsize = size();
_start[newsize] = x;
_finish++;
}//删除数据
void pop_back()
{
assert(size() > 0); //这里要注意容器是否为空
_finish--;
}
普通构造函数
首先,我们先实现无任何传入值的构造函数。这种情况只需初始化容器的各种数据即可,不需要做任何增添。
vector()
{
_start = _finish = _endOfStorage = nullptr; //直接将数据设为空
}
第二种构造方式这里模拟实现构造n个数据,如:vector<int>v(5,8)初始化为5个8。
//T()表示T类型的构造函数,即上面第一种的构造函数实现
vector(int n, const T& value = T())
{
reserve(n); //这里要先进行扩容
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
第三种构造方式模拟实现迭代器的方式进行构造。因为数据类型未知,所以这里还需要使用模板。
//这里迭代器要使用模板
template<class InputIterator>
//first指向开始位置,last指向终点的下一位
vector(InputIterator first, InputIterator last)
{
int newsize = last - first;
reserve(newsize);
for (int i = 0; i < newsize; i++)
{
push_back(*(first + i));
}
}
拷贝构造函数
原理跟普通构造函数实现的机制一样,这里就不做过多说明,直接实现代码,如下:
vector(const vector<T>& v)
{
int newsize = v.capacity();
reserve(newsize);
for (int i = 0; i < newsize; i++)
{
push_back(v._start[i]);
}
}
三,析构函数
析构函数在释放空间之后要记得将数据初始化,以保证安全性。
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
四,赋值运算符
赋值运算符的实现跟拷贝构造函数实现机制相同。实现拷贝后要返回拷贝后的容器,以便实现连续赋值的情况。
vector<T>& operator= (vector<T> v)
{
int newsize = v.capacity();
reserve(newsize);
for (int i = 0; i < newsize; i++)
{
push_back(v._start[i]);
}
return *this;
}
五,容器接口的实现
1,迭代器实现
这里实现begin()、end()、cbegin()、cend()四种常用的迭代器。
//begin()和end()的实现
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}//cbegin()和cend()常量迭代器的实现
const_iterator cbegin() const
{
const_iterator p = (const_iterator)_start;
return p;
}
const_iterator cend() const
{
const_iterator p = (const_iterator)_finish;
return p;
}
2,“ [] ”运算符的实现
“ [] ” 运算符实现分为两种,一种是变量的实现,一种是常量const的实现。
//变量实现
T& operator[](size_t pos)
{
assert(pos >= 0 && pos < size());
return _start[pos];
}//常量实现
const T& operator[](size_t pos)const
{
assert(pos >= 0 && pos < size());
const T tem = (const T)_start[pos];
return tem;
}
3,swap交换和resize重设大小
swap接口实现机制是容器的全部数据实现交换。resize实现时要考虑参数大于容器大小和小于容器大小时的不同情况。
//交换算法
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}//设定大小算法
void resize(size_t n, const T& value = T())
{
assert(n >= 0); //防止错误操作
if (n < size()) //小于容器大小时的情况
{
_finish = _start + n;
}
else //大于等于容器大小时的情况
{
reserve(n);
for (int i = 0; i < n - size(); i++)
{
push_back(value);
}
}
}
4,insert插入和erase删除
这里实现insert插入要注意的是选择位置时,因为不确定数据类型,因此要在指定迭代器的位置进行插入,最后返回该位置的迭代器。
erase删除位置与insert插入位置一样,删除迭代器所指向的位置,最后返回该位置的迭代器。
//插入算法,在pos位置下插入数据x
iterator insert(iterator pos, const T& x)
{//要考虑指定插入的位置在合理范围之内
assert(pos >= _start && pos < _finish);
if (size() == capacity())
{
reserve(size() + 1);
}
for (iterator it = _finish - 1; it >= pos; it--)
{
*(it + 1) = *(it);
}
*pos = x;
return pos;
}//删除算法,删除pos位置下的数据
iterator erase(iterator pos)
{文章来源:https://www.toymoban.com/news/detail-787229.html//要考虑指定删除的位置在合理范围之内
assert(size() > 0);
assert(pos >= _start && pos < _finish);
for (iterator i = pos; i < _finish - 1; i++)
{
*(i) = *(i + 1);
}
_finish--;
return pos;
}文章来源地址https://www.toymoban.com/news/detail-787229.html
到了这里,关于【C++】vector容器的模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!