实现数组的迭代器
实现内容:
1:使用C++语言实现一个长度可扩充的数组结构(要求使用class实现),不能直接使用vector等现成的数据结构。
2:要求实现为可以用于不同数据类型的数组结构(并不是说同一个对象需要存储多种类型的数据),建议使用template实现
3:为实现的数组结构添加迭代器(iterator) 接口(包括Iterator 和 ConstIterator)
代码:
#include <iostream>
#include <memory.h>
#include <assert.h>
using namespace std;
template <typename T>
class CArrayIterator;
template <typename T>
class CArrayConstIterator;
template <typename T>
class CArray
{
public:
typedef T Element;
typedef CArrayIterator<T> Iterator;
typedef CArrayConstIterator<T> ConstIterator;
public:
CArray():_size(0),_cap(0) {_buff=NULL;}
CArray(const CArray &rhs)
{
_size=rhs._size;
_cap=rhs._cap;
_buff=new Element[_cap];
for(int i=0;i<rhs._size;++i)
_buff[i]=rhs._buff[i];
}
~CArray()
{
//这里不可以加delete,否则会内存超限
/*
if(_buff != NULL)
delete[] _buff;
*/
_buff=NULL;
_size=0;
_cap=0;
}
public:
int capacity() const
{
return _cap;
}
int size() const
{
return _size;
}
void recap(int cap)
{
if (cap == _cap){return;}
Element *buff = new Element[cap];
_cap = cap;
_size = cap < _size ? cap : _size;
memcpy(buff, _buff, _size * sizeof(Element));
delete[] _buff;
_buff = buff;
}
Element &at(int index)
{
return _buff[index];
}
Element at(int index) const
{
return _buff[index];
}
void append(Element element)
{
if(_size == _cap)
recap(_cap+1);
_buff[_size++] = element;
}
void insert(int index, Element element)
{
if(_size == _cap)
recap(_cap+1);
for (int i = _size; i > index; --i)
{
_buff[i] = _buff[i - 1];
}
_buff[index] = element;
_size += 1;
}
void copy(const CArray &rhs)
{
if(_cap < rhs._cap)
recap(rhs._cap);
memcpy(_buff, rhs._buff, rhs._size * sizeof(Element));
_size = rhs._size;
}
bool compare(const CArray &rhs) const
{
if (rhs._size != _size){return false;}
return memcmp(_buff, rhs._buff, _size) == 0;
}
Iterator begin(){return Iterator(_buff);}
Iterator end(){return Iterator(_buff+_size);}
ConstIterator begin() const{return ConstIterator(_buff);}
ConstIterator end()const {return ConstIterator(_buff+_size);}
private:
void _check_capacity(int minimal)
{
if(_cap<minimal)
this->recap(minimal);
}
Element *_buff;//数据
int _size;//元素个数
int _cap;//容量
};
template <typename T>
class CArrayIterator
{
public:
CArrayIterator() {}
CArrayIterator(T *current){_current=current;}
CArrayIterator(const CArrayIterator &rhs){_current=rhs._current;}
~CArrayIterator()
{
/*
if(_current!=NULL)
delete _current;
*/
_current=NULL;
}
public:
//实现所需要的操作符重载函数
CArrayIterator operator++(){_current++;return *this;}
CArrayIterator operator++(int)
{
CArrayIterator tmp(*this);
++(*this);
return tmp;
}
bool operator!=(const CArrayIterator rhs){return this->_current!=rhs._current;}
bool operator==(const CArrayIterator rhs){return this->_current==rhs._current;}
T& operator*() const{return *_current;}
T* operator->() const{return _current;}
protected:
T *_current;
friend class CArray<T>;
};
template <class T>
class CArrayConstIterator
{
public:
CArrayConstIterator() {_current=NULL;}
CArrayConstIterator(T *current){_current=current;}
CArrayConstIterator(const CArrayConstIterator &rhs){_current=rhs._current;}
~CArrayConstIterator()
{
/*
if(_current!=NULL)
delete _current;
*/
_current=NULL;
}
public:
//实现所需要的操作符重载函数
CArrayConstIterator operator++(){_current++;return *this;}
CArrayConstIterator operator++(int)
{
CArrayConstIterator tmp(*this);
++(*this);
return tmp;
}
bool operator!=(const CArrayConstIterator rhs)const{return this->_current!=rhs._current;}
bool operator==(const CArrayConstIterator rhs)const{return this->_current==rhs._current;}
T& operator*() const{return *_current;}
T* operator->() const{return _current;}
protected:
T *_current;
friend class CArray<T>;
};
附上测试代码:
template <typename T>
class Obj
{
public:
Obj(){};
Obj(int val) : data(val){};
~Obj(){};
public:
T data;
private:
template <typename Tp>
friend std::ostream &operator<<(std::ostream &os, const Obj<Tp> &obj);
};
template <typename Tp>
std::ostream &operator<<(std::ostream &os, const Obj<Tp> &obj)
{
os << obj.data;
return os;
}
int main(int argc, char const *argv[])
{
CArray<int> array;
// 不再需要initial,但应该有正确的初始化
// array_initial(array);
array.recap(10);
assert(array.capacity() == 10);
//
for (int i = 0; i < 20; ++i)
{
array.append(i);
}
assert(array.size() == 20);
for (int i = 0; i < array.size(); ++i)
{
assert(array.at(i) == i);
}
//
CArray<int> array2, array3;
// array_initial(array2);
// array_initial(array3);
array2.copy(array);
assert(array.compare(array2) == true);
array3.copy(array);
assert(array.compare(array3) == true);
//
array2.insert(2, 3);
assert(array.compare(array2) == false);
//
array3.at(2) = 5;
assert(array.compare(array3) == false);
//
for (CArray<int>::Iterator it = array.begin(); it != array.end(); ++it)
{
std::cout << *it << " ";
(*it) = (*it) + 10;
}
std::cout << std::endl;
for (CArray<int>::Iterator it = array.begin(); it != array.end();)
{
std::cout << *(it++) << " ";
}
std::cout << std::endl;
const CArray<int> tmp(array);
for (CArray<int>::ConstIterator it = tmp.begin(); it != tmp.end(); ++it)
{
std::cout << *it << " ";
}
std::cout << std::endl;
CArray<Obj<int>> obj_arr;
for (CArray<int>::ConstIterator it = tmp.begin(); it != tmp.end();)
{
obj_arr.append(Obj<int>(*it));
std::cout << *(it++) << " ";
}
std::cout << std::endl;
for (CArray<Obj<int>>::Iterator it = obj_arr.begin(); it != obj_arr.end(); ++it)
{
std::cout << (*it) << " ";
}
std::cout << std::endl;
for (CArray<Obj<int>>::Iterator it = obj_arr.begin(); it != obj_arr.end(); ++it)
{
std::cout << it->data << " ";
}
std::cout << std::endl;
return 0;
}