【C++】—— 模拟实现vector(源代码)
一、vector的介绍1、vector是表示可变大小数组的序列容器。2、就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。3、本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做...
一、vector的介绍
1、vector是表示可变大小数组的序列容器。
2、就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
3、本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
4、vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5、因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
6、与其它动态序列容器相比(deques, lists and forward_lists), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起lists和forward_lists统一的迭代器和引用更好。
二、 vector的实现
头文件,vector.h
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <string>
using namespace std;
namespace CXY
{
template <class T>
class Vector
{
public:
typedef T* iterator;//Vector迭代器的原生指针
typedef const T* const_iterator;//const迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cbegin() const
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
//构造函数
/*Vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}*/
Vector() = default;//让系统生成默认构造函数
~Vector()//析构函数
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
//拷贝构造v2(v1)实现一
//Vector( Vector<T>& v)
//{
// _start = new T[v.Capacity()];
// //memcpy(_start, v._start, sizeof(T)*v.Size());
// for (size_t i = 0; i < Size(); ++i)
// {
// _start[i] = v._start[i];
// }
// _finish = _start + v.Size();
// _endofstorage = _start + v.Capacity();
//}
//拷贝构造实现二
Vector(const Vector<int>& v)
:_start(nullptr)
,_finish(nullptr)
, _endofstorage(nullptr)
{
Reserve(v.Capacity());
iterator it = begin();
const_iterator vit = v.cbegin();
while (vit != v.cend())
{
*it++ = *vit++;
}
_finish = _start + v.Size();
_endofstorage = _start + v.Capacity();
}
//赋值运算符= v1 = v2 = v3实现一
/*Vector<T>& operator=(const Vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = new T[sizeof(T)*v.Size()];
memcpy(_start, v._start, sizeof(T)*v.Size());
_finish = _start + v.Size();
_endofstorage = _start + v.Capacity();
}
return *this;
}*/
//赋值运算符copy = v2;实现二
Vector<T>& operator=(Vector<T> v)
{
this->Swap(v);
return *this;
}
void Swap(Vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//往Vector中插入数据
void PushBack(const T& x)
{
/*if (_finish == _endofstorage)
{
size_t newcapacity = Capacity() == 0 ? 2 : Capacity() * 2;
Reserve(newcapacity);
}
*_finish = x;
++_finish;*/
Insert(end(), x);
}
//在Vector后插入数据
void PopBack()
{
assert(Size() > 0);
--_finish;
//Erase(--end());
}
//在Vector中任意位置前插入一个数
void Insert(iterator pos, const T& x)
{
assert(pos <= _finish);
size_t posindex = pos - _start;
if (_finish == _endofstorage)
{
size_t newcapacity = Capacity() == 0 ? 2 : Capacity() * 2;
Reserve(newcapacity);
pos = _start + posindex;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
--end;
}
*pos = x;
++_finish;
}
//删除Vector任意位置中的数,并返回下一个位置
//返回下一个位置是为了防止出现迭代器失效的问题
iterator Erase(iterator pos)
{
iterator begin = pos;
while (pos != _finish)
{
*pos = *(pos + 1);
++pos;
}
--_finish;
return begin;
}
//增容Capacity
void Reserve(size_t n)
{
if (n > Capacity())
{
size_t size = Size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*size);
for (size_t i = 0; i < size; ++i)
{
tmp[i] = _start[i];
}
}
_start = tmp;
_finish = _start + size;
_endofstorage = _start + n;
}
}
//增加Size
void Resize(size_t n, const T& value = T())
//T()调用默认构造函数,给value赋缺省值
//因为容器Vector内可以存放任意类型的数据,当类型将T替换时,就会调用对应类型的构造函数
//C++中内置类型也有对应的构造函数(int() char())
{
//当n小于当前size时,将数据个数缩小到n
if (n <= Size())
{
_finish = _start + n;
}
else
{
//当容量不够时增容
if (n > Capacity())
Reserve(n)
while (_finish != _start + n)
{
*_finish = value;
++_finish;
}
}
}
//访问Vector
T& operator [](size_t pos)
{
assert(pos < Size());
return _start[pos];
}
/*const T& operator[](size_t pos) const
{
assert(pos < Size());
return _start[pos];
}*/
size_t Size() const
{
return _finish - _start;
}
size_t Capacity() const
{
return _endofstorage - _start;
}
private:
iterator _start = nullptr;//给每个成员都赋上缺省值
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void TestVector1()//测试构造函数,PushBack,PopBack,迭代器
{
Vector<int> v1;
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
v1.PushBack(5);
v1.PopBack();
for (size_t i = 0; i < v1.Size(); ++i)
{
cout << v1[i] << " ";
}
cout << endl;
//Vector迭代器使用
Vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for的使用
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void TestVector2()//测试拷贝构造,赋值运算符=,const迭代器
{
Vector<int> v2;
v2.PushBack(1);
v2.PushBack(2);
v2.PushBack(3);
v2.PushBack(4);
v2.PushBack(5);
//Vector<int> v3(v2);//调拷贝构造函数初始化v3
//调赋值运算符=
Vector<int> v3;
v3 = v2;
//调用const迭代器
Vector<int>::const_iterator cit = v3.cbegin();
while (cit != v3.cend())
{
cout << *cit << " ";
++cit;
}
cout << endl;
}
void TestVector3()
{
Vector<int> v3;
v3.PushBack(1);
v3.PushBack(2);
v3.PushBack(3);
v3.PushBack(4);
v3.PushBack(5);
Vector<int>::iterator pos = find(v3.begin(), v3.end(), 3);//调用算法中的find函数找pos
for (size_t i = 0; i < v3.Size(); ++i)
{
cout << v3[i] << " ";
}
cout << endl;
v3.Insert(pos, 30);//调用Insert
pos = find(v3.begin(), v3.end(), 4);
Vector<int>::iterator ret = v3.Erase(pos);//调用Erase
Vector<int>::const_iterator cit = v3.cbegin();
while (cit != v3.cend())
{
cout << *cit << " ";
++cit;
}
cout << endl;
cout << "下一个位置的值:" << *ret << endl;
}
}
主函数部分,main.cpp
#define _CRT_SECURE_NO_WARNINGS
#include "Vector.h"
int main()
{
//CXY::TestVector1();
//CXY::TestVector2();
CXY::TestVector3();
return 0;
}
注:1、这里我将vector封装在以自己名字命名的命名空间中,防止与库中vector冲突。
2、在vector类后,我写了3个测试函数,对vector的功能进行了测试。
更多推荐
所有评论(0)