C++的STL库有一个容器叫vector，这个容器底层的数据结构是一个内存可以自动增长的数组，每次当数组存储满了以后，内存可以自动增加两倍，请完成vector容器、迭代器和空间配置器三个类方法的实现。
#include<iostream>
using namespace std;
//容器默认的空间配置器的实现
template<typename T>
class myallocator
{
public:
T* allocate(size_t size) //开辟内存
{
return (T*)malloc(size);
}
void deallocate(void *ptr) //释放内存
{
free(ptr);
}
void construct(T *ptr, const T &val)//构造对象
{
new(ptr)T(val);
}
void destroy(T *ptr) //析构对象
{
ptr->~T();
}
};
//容器的类模板
template<typename E, typename allocator = myallocator<E>>
class Vector
{
public:
//迭代器类型前置声明
class iterator;
//默认构造函数
Vector(int size = 5)
{
_first = _allocator.allocate(size*sizeof(E));
_end = _first + size;
_last = _first;
}
//析构函数
~Vector()
{
int size = _last - _first;
for (int i = 0; i < size; ++i)
{
_allocator.destroy(_first + i);
}
_allocator.deallocate(_first);
_first = _last = _end = NULL;
}
//拷贝构造函数
Vector(const Vector<E, allocator> &src)
{
int length = src._end - src._first;
_first = _allocator.allocate(length*sizeof(E));
int size = src._last - src._first;
for (int i = 0; i < size; ++i)
{
_allocator.construct(_first + i, src._first[i]);
}
_end = _first + size;
_last = _first + length;
}
//赋值运算符的重载函数
Vector<E, allocator>& operator=(const Vector<E, allocator> &src)
{
if (this == &src)
{
return*this;
}
int size = _last - _first;
for (int i = 0; i < size; ++i)
{
_allocator.destroy(_first + i);
}
_allocator.deallocate(_first);
_first = _last = _end = NULL;
int length = src._end - src._first;
_first = _allocator.allocate(length*sizeof(E));
int size = src._last - src._first;
for (int i = 0; i < size; ++i)
{
_allocator.construct(_first + i, src._first[i]);
}
_end = _first + size;
_last = _first + length;
}
//向容器的末尾添加新元素value，若增长内存，调用resize函数
void push_back(const E &value)
{
if (full())
{
resize();
}
_allocator.construct(_last, value);
_last++;
}
//删除容器末尾的元素
void pop_back()
{
if (empty())
{
return;
}
_last--;
_allocator.destroy(_last);
}
//向指定位置插入新元素value，若增长内存，调用resize函数
iterator insert(iterator it, const E &value)
{
if (it.mptr<_first || it.mptr>_last)
{
return _last;
}
if (_last == _end)
{
int offset = it.mptr - _first;
resize();
it.mptr = _first + offset;
}
E*p = _last;
for (; p > it.mptr; --p)
{
_allocator.construct(p, *(p - 1));
_allocator.destroy(p - 1);
}
_allocator.construct(p, value);
_last++;
return p;
}
//删除指定位置的元素
iterator erase(iterator it)
{
if (it.mptr<_first || it.mptr >= _last)
{
return _last;
}
E*p = it.mptr;
for (; p < _last - 1; ++p)
{
_allocator.destroy(p);
_allocator.construct(p, *(p + 1));
}
_allocator.destroy(p);
--_last;
return it.mptr;
}
//判断容器是否空
bool empty()const{ return _first == _last; }
//判断容器是否满
bool full()const{ return _last == _end; }
//容器的迭代器实现
class iterator
{
public:
iterator(E*ptr = NULL) :mptr(ptr){}
bool operator!=(const iterator&it)
{
return mptr != it.mptr;
}
void operator++()
{
mptr++;
}
E&operator*()
{
return*mptr;
}
E*mptr;
};
iterator begin(){ return iterator(_first); }
iterator end(){ return iterator(_last); }
private:
//内存增长函数，按原有容量的两倍增长
void resize()
{
int size = _last - _first;
E*ptmp = _allocator.allocate((size)*sizeof(E)* 2);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first[i]);
}
for (int i = 0; i < size; ++i)
{
_allocator.destroy(_first + i);
}
_allocator.deallocate(_first);
_first = ptmp;
_end = _first + size * 2;
_last = _first + size;
}
E *_first; //指向数组的起始位置
E *_end; //指向数组的末尾的后继位置
E *_last; //指向数组最后一个有效数据的后继位置
allocator _allocator; // vector容器的空间配置器
};
int main()
{
Vector<int>Vec;
Vec.push_back(20);
Vec.push_back(21);
Vec.push_back(22);
Vec.push_back(23);
Vec.push_back(24);
Vec.push_back(25);
Vec.push_back(26);
Vec.pop_back();
Vec.erase(Vec.begin());
Vec.insert(Vec.begin(),66);
Vector<int>::iterator it = Vec.begin();
for (; it != Vec.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
运行结果如下：
