用allocator類管理記憶體，來模拟vector

#include <iostream>

#include <memory>

#include <algorithm>

#include <cassert>

using namespace std;

/*用allocator類管理記憶體，來模拟vector

作者：blackmanba

時間：2010年10月6日

*/

#define MAX(a,b) ((a>b)? (a):(b))

/*模拟vector類*/

template <typename T>

class Vector

{

public:

Vector():elements(NULL), first_free(NULL), end(NULL){}

void push_back(const T& t);//插入元素

void reserve(const int& n);//該變向量的容量

void resize(const int& n);//改變向量所包含元素的個數

T& operator[](const int &i);//重載小标運算符

size_t size() const;//傳回元素個數

//聲明Vector的疊代器

typedef T* iterator;

iterator begin();//傳回首元素的疊代器

iterator back();//傳回最後一個元素後面的疊代器

private:

static allocator<T> alloc;//獲得原始記憶體的對象

void reallocate();//獲得更大的記憶體空間并拷貝已存在的元素

T* elements; //指向數組中第一個元素的指針

T* first_free;//指向數組中第一個實際元素之後的指針

T* end;//指向數組本身之後的那個元素

};

template <typename T>

allocator<T> Vector<T>::alloc ;

int main()

{

Vector<int> vec;

int i;

for (i=0; i<10; i++)

{

vec.push_back(i+1);

}

vec.reserve(20);

vec.resize(30);

cout<<vec.size()<<endl;

for (i=0; i<vec.size(); i++)

{

cout<<vec[i]<<" ";

}

cout<<endl;

vec.reserve(15);

vec.resize(13);

//用疊代器來通路

Vector<int>::iterator iter1 = vec.begin();

Vector<int>::iterator iter2 = vec.back();

while (iter1 != iter2)

{

cout<<*iter1++<<" ";

}

cout<<endl;

allocator<int> alloc;//建立對象

int* p = alloc.allocate(10, NULL);//配置設定記憶體

for (i=0; i<10; ++i)

{

alloc.construct(p+i, i+1);//初始元素

}

alloc.deallocate(p, 10);//删除配置設定的記憶體

}

//插入元素

template <typename T>

void Vector<T>::push_back(const T& t)

{

//判斷配置設定的空間是否已經滿了

if (first_free == end)

{

reallocate();//獲得更多的空間，并把原先的元素拷貝到新配置設定的空間

}

alloc.construct(first_free, t);//使用類型T的複制構造函數将t值複制到由first_free指向的元素

++first_free;

}

//獲得更大的記憶體空間并拷貝已存在的元素

template <typename T>

void Vector<T>::reallocate()

{

ptrdiff_t size = first_free - elements;//計算目前數組中的元素個數

ptrdiff_t newcapacity = 2 * MAX(size, 1);//每次配置設定的空間是前一次的2倍

T* newelements = alloc.allocate(newcapacity, NULL); //配置設定新的空間，并把新空間的位址賦給newelements

uninitialized_copy(elements, first_free, newelements);//複制構造每一進制素

for (T* p = first_free; p != elements; )//按逆序析構原先的元素

{

alloc.destroy(--p);//運作T類型的析構函數來釋放舊元素所用的任何資源

}

if (elements != NULL)

{

alloc.deallocate(elements, end - elements);//釋放存放舊元素的記憶體

}

//改變資料指針

elements = newelements;

first_free = elements + size;

end = elements + newcapacity;

}

//該變向量的容量

template <typename T>

void Vector<T>::reserve(const int& n)

{

ptrdiff_t capacity = end - elements;//計算目前向量的容量

ptrdiff_t size = first_free - elements;//計算目前數組中的元素個數

//如新容量大于原先的，要進行配置設定

if (n > capacity)

{

T* newelements = alloc.allocate(n, NULL); //配置設定新的空間，并把新空間的位址賦給newelements

uninitialized_copy(elements, first_free, newelements);//複制構造每一進制素

for (T* p = first_free; p != elements; )//按逆序析構原先的元素

{

alloc.destroy(--p);//運作T類型的析構函數來釋放舊元素所用的任何資源

}

if (elements != NULL)

{

alloc.deallocate(elements, end - elements);//釋放存放舊元素的記憶體

}

//改變資料指針

elements = newelements;

first_free = elements + size;

end = elements + n;

}

else //如果新容量小于原容量，不配置設定，并且要删除多餘的

{

T* newelements = alloc.allocate(n, NULL); //配置設定新的空間，并把新空間的位址賦給newelements

uninitialized_copy(elements, elements+n, newelements);//複制構造每一進制素

for (T* p = first_free; p != elements; )//按逆序析構原先的元素

{

alloc.destroy(--p);//運作T類型的析構函數來釋放舊元素所用的任何資源

}

if (elements != NULL)

{

alloc.deallocate(elements, end - elements);//釋放存放舊元素的記憶體

}

//改變資料指針

elements = newelements;

first_free = elements + size;

end = elements + n;

}

}

//重載下标運算符

template <typename T>

T& Vector<T>::operator[](const int &i)

{

int s = size();

assert(0<=i && i<s);

return *(elements + i);

}

//傳回元素個數

template <typename T>

size_t Vector<T>::size() const

{

return (first_free - elements);

}

//改變向量所包含元素的個數

template <typename T>

void Vector<T>::resize(const int& n)

{

int s = size();

//若新size小于原來的，要删除元素

if (n < s)

{

for (T* p = first_free; p != elements+n; )//按逆序析構原先的元素

{

alloc.destroy(--p);//運作T類型的析構函數來釋放舊元素所用的任何資源

}

first_free = elements + n;

}

else

{

//大于的話，隻用添加元素即可，會自動增加容量的

for (int i=0; i<n-s; i++)

{

push_back(T());

}

}

}

//傳回首元素的疊代器

template <typename T>

Vector<T>::iterator Vector<T>::begin()

{

return elements;

}

//傳回最後一個元素後面的疊代器

template <typename T>

Vector<T>::iterator Vector<T>::back()

{

return first_free;

}