[DS]实现Vector类
- 2.1.源码: QVector.h
- 2.2.测试 main.cpp
1.来源
本例程主要是实现vector类，来源于《数据结构与算法分析：C++描述》中。实现了题3.7和3.8中的添加索引时的边缘检测功能和添加了insert()和eraser()功能。
对于该例子中，Vector类的迭代器实际上是一个指针变量，在题3.9中要求应该定义一个迭代器类型，并且实现严格的迭代器检验，这部分在后续中实现，现在Vector类的迭代器实际上是一个Object *类型，即指向Object的指针。
typedef Object * iterator;
typedef const Object * const_iterator;//定义指向const的指针[指针指向的内容不能被修改][指针地址可以改变]2.源码
2.1.源码: QVector.h
#include <iostream>
using namespace std;
#ifndef __QVector_H_
#define __QVector_H_
template <typename Object>
class Vector
{
public:
explicit Vector(int initSize = 0)
: theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)
{
objects = new Object[theCapacity];
}
Vector(const Vector & rhs) : objects(NULL)//复制构造函数
{
operator=(rhs);
}//调用 operator= 对rhs进行复制
~Vector()//析构函数
{
delete[] objects;
}
const Vector & operator= (const Vector & rhs)
{
if (this != &rhs)//混淆检验
{
delete[] objects;//删除旧数组
theSize = rhs.size();
theCapacity = rhs.theCapacity;
objects = new Object[capacity()];//创建新数组
for (int k = 0; k < size(); k++)
objects[k] = rhs.objects[k];
}
return *this;
}
void resize(int newSize)
{
if (newSize > theCapacity)
reserve(newSize * 2 + 1);
theSize = newSize;//更新存储大小
}
void reserve(int newCapacity)
{
if (newCapacity < theSize)
return;
Object *oldArray = objects;
objects = new Object[newCapacity];
for (int k = 0; k < theSize; k++)
objects[k] = oldArray[k];//复制数据到新数组
theCapacity = newCapacity;//更新容量
delete[] oldArray;//删除旧数组
}
Object & operator[](int index)
{//加入了边缘检测
if (index >= 0 && index < size())
{
return objects[index];
}
else
{
cout << "index out of bounds\n";
return objects[0];
}
}
const Object & operator[](int index) const
{//加入了边缘检测
if (index >= 0 && index < size())
{
return objects[index];
}
else
{
cout << "index out of bounds\n";
return objects[0];
}
}
bool empty() const//Vector是否为空
{
return size() == 0;
}
int size() const
{
return theSize;
}
int capacity() const
{
return theCapacity;
}
void push_back(const Object & x)//添加元素
{
if (theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[theSize++] = x;
}
void pop_back()//删除元素
{
theSize--;
}
const Object & back() const//返回当前vector容器中末尾元素的引用
{
return objects[theSize - 1];
}
typedef Object * iterator;
typedef const Object * const_iterator;//定义指向const的指针[指针指向的内容不能被修改][指针地址可以改变]
iterator begin()
{
return &objects[0];
}//返回第一个元素的指针
const_iterator begin() const
{
return &objects[0];
}
iterator end()
{
return &objects[size()];
}
const_iterator end() const
{
return &objects[size()];
}//返回最后一个元素[下一个位置]的指针
enum { SPARE_CAPACITY = 16 };
iterator insert(iterator pos, const Object& x)
{
iterator ite = insert(pos, 1, x);
return ite;
}
iterator insert(iterator pos, int num, const Object& x)
{
Object *iter = this->begin();
Object *oldArray = objects;
theSize += num;
int i,k;
if (theCapacity < theSize)
{
theCapacity = theSize;
}
objects = new Object[theCapacity];//创建一个新的存储地址
i = 0;
while (iter != pos)
{//从起始位置到要插入位置之前，复制旧元素到新的存储空间
objects[i] = oldArray[i];
++iter;
++i;
}
//在目标位置插入新的元素
for (k = 0; k < num; k++,i++)
{
objects[i] = x;
}
//从目标位置之后，复制旧元素到新的存储空间
for ( k = i; k < theSize; k++)
{
//new数组的最大下标为[theSize-1]
//old数组的最大下标为[theSize-1-num]
objects[k] = oldArray[k - num];
}
//删除原来的存储空间
delete[] oldArray;
//返回插入最后一个元素的迭代器
return &objects[i-1];
}
iterator erase(iterator pos)
{
return erase(pos, pos);
}
iterator erase(iterator first, iterator last)
{
Object *iter1 = first;
Object *iter2 = last;
Object *oldEnd = this->end();
int delnum = 0;
//Step1.删除部分
while (iter1!=last+1)
{
if (iter2 == oldEnd)
{
//*iter1 = objects[0];
}
else
{
iter2 += 1;
*iter1 = *iter2;//last 后面的元素依次赋给删除的元素
}
iter1 += 1;//first 移动
//移动1次，删除1次
theSize--;
}
//Step2.移动后续部分
while (iter2 != oldEnd)
{
iter2 += 1;
*iter1 = *iter2;//
iter1 += 1;//first 移动
}
return iter1;
}
private:
int theSize;//存储大小
int theCapacity;//容量
Object * objects;//基本数组
};
#endif2.2.测试 main.cpp
#include "set.h"
#include "QVector.h"
template <typename Object>
void printVect1(Vector<Object> vec)
{//用迭代器调用显示
Vector<int>::iterator iter = vec.begin();
while (iter != vec.end())
{
cout << *iter << " ";
++iter;
}
cout << endl;
}
template <typename Object>
void printVect2(Vector<Object> vec)
{//按照下标调用显示
for (int i = 0; i < vec.size(); i++)
{
cout << "vec[" << i << "] = " << vec[i] << endl;
}
}
int main()
{
Vector<int> vec;
int i;
//初始化Vector
for (i = 1; i <= 10; i++)
{
vec.push_back(i);
}
printVect1(vec);
//测试erase()函数
vec.erase(vec.begin() + 1, vec.begin() + 8);
printVect1(vec);
vec.erase(vec.begin());
printVect1(vec);
vec.erase(vec.end());
cout << "size: " << vec.size() << endl;
printVect1(vec);
//初始化Vector
for (i = 1; i <= 10; i++)
{
vec.push_back(i);
}
printVect1(vec);
//测试insert函数
Vector<int>::iterator pos = vec.begin();
int data = 999;
cout << "插入: " << data << endl;
pos = vec.insert(pos, 3, data);
cout << "返回: " << *pos << endl;
printVect1(vec);
pos = vec.end();
data = 666;
cout << "插入: " << data << endl;
pos = vec.insert(pos, 1, data);
cout << "返回: " << *pos << endl;
printVect1(vec);
//测试非法调用
cout << "测试非法调用:" << endl;
cout << vec[vec.size()] << endl;
return 0;
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读