Vector類模板界面及其函數(shù)的實現(xiàn)

BUPT-BYR 2010-12-20

展開全文

Vector 界面
template<typename T>

struct Vector {                                                //T的構造函數(shù)為空,；
Vector(unsigned n = 0, T const& t = T());       //構造函數(shù)；
Vector(Vector const& me);                              //拷貝構造函數(shù),；
Vector& operator=(Vector const& rhs);           //對賦值運算符=的重載,；
virtual ~Vector(void);                                       //析構函數(shù)；
void clear(void);                                               //清空函數(shù),，將向量變?yōu)榭眨?br>bool empty(void) const;                                   //判斷向量是否為空,；
unsigned size(void) const;                               //返回向量中元素個數(shù)；
unsigned capacity(void) const;                        //返回向量容量,；
T& front(void);                                                  //返回對第一個元素的引用,；
T& back(void);                                                 //返回對最后一個元素的引用；
T& operator[ ](unsigned n);                              //返回對第n個元素的引用,；
typedef T* Iterator;                                           //定義向量的迭代子類型,；
Iterator begin(void);                                          //返回指向第一個元素的迭代子；
Iterator end(void);                                             //返回向量的右邊界,；
void pop_back(void);                                        //刪除向量的最后一個元素,；
void erase(Iterator p);                                       //刪除迭代子p指向的元素；
void push_back(T const& v);                            //在向量尾部添加元素,；
void insert(Iterator p, T const& v);                     //在迭代子p之前添加v,；
void reserve(unsigned nc);                              //保證向量容量大于等于nc；
void resize(unsigned ns);                                //將向量容量值為ns,；
T* elem_;                                                         //向量基址,；
unsigned size_;                                               //向量中實際元素個數(shù)；
unsigned cpct_;                                               //向量容量,；
protected:
bool full(void) const;                                        //判滿函數(shù),；
unsigned next_capacity(void) const;               //內存管理策略；
};
template<typename T>
void swap(Vector<T>& a, Vector<T>& b);     //交換兩個向量的內容,；

/***********************************************************/

具體函數(shù)實現(xiàn)：

構造函數(shù)：
template<typename T>
Vector<T>::Vector(unsigned n, T const& t)
: elem_(0), size_(n), cpct_(n)
{
if(n > 0) {
elem_ = (T*)::malloc(n*sizeof(T));
std::uninitialized_fill(elem_, elem_ + n, t);
}
}
std::uninitialized_fill 為標準模板庫STL中的算法,，它將未初始化的內存填充一個固定的值；

拷貝構造函數(shù)
創(chuàng)建一個內容和me相同的向量,；
template<typename T>
Vector<T>::Vector(Vector const& me)
: elem_(0), size_(me.size()), cpct_(me.size())
{
if(size_ > 0) {
elem_ = (T*)::malloc(size_*sizeof(T));
::memcpy(elem_, me.elem_, size_*sizeof(T));
}
}

重載賦值運算符,；

template<typename T>
Vector<T>& Vector<T>::operator=(Vector const& rhs)
{
reserve(size_ = rhs.size());
::memcpy(elem_, rhs.elem_, size_*sizeof(T));
return *this;
}
reserve函數(shù)保證自身至少容納一定量的元素，賦值運算符返回對自身的引用,；

析構函數(shù)：
template<typename T>
Vector<T>::~Vector(void)
{
::free(elem_);
}

清空函數(shù)：
template<typename T>
void Vector<T>::clear(void)
{
size_ = 0;
}

獲取向量的成員：
template<typename T>
T& Vector<T>::front(void)
{
return elem_[0];
}

template<typename T>
T& Vector<T>::back(void)
{
return elem_[size_ - 1];
}

template<typename T>
T& Vector<T>::operator[ ](unsigned n)
{
return elem_[n];
}

向量迭代子定義：
template<typename T>
struct Vector {
typedef T* Iterator;
};

begin,，end函數(shù)的實現(xiàn)：
template<typename T>
typename Vector<T>::Iterator Vector<T>::begin(void)
{
return elem_;
}
template<typename T>
typename Vector<T>::Iterator Vector<T>::end(void)
{
return elem_ + size_;
}
///////////////////////////////////////////////
template<typename T>
T* Vector<T>::begin(void)
{
return elem_;
}
template<typename T>
T* Vector<T>::end(void)
{
return elem_ + size_;
}

向量元素的刪除：
刪除最后元素不需移動任何元素，復雜度為θ(1)
template<typename T>
void Vector<T>::pop_back(void)
{
--size_;
}
將后面所有元素向前移動一位將其覆蓋,，復雜度為θ(n)
template<typename T>
void Vector<T>::erase(Iterator p)
{
::memmove(p, p + 1, sizeof(T)*(elem_ + --size_ - p));
}

向量內存管理策略：
reserve(n)保證向量的容量大于等于n
template<typename T>
void Vector<T>::reserve(unsigned n)
{
if(cpct_ < n) {
elem_ = (T*)::realloc(elem_, n*sizeof(T));
std::uninitialized_fill(elem_ + cpct_, elem_ + n, T());
cpct_ = n;
}
}

判滿函數(shù)：
full()
template<typename T>
bool Vector<T>::full(void) const
{
return size_ == cpct_;
}

添加函數(shù)：
在p之前添加v
template<typename T>
void Vector<T>::insert(T* p, T const& v)
{
if(full())
{
int const offset = p - elem_;
reserve(next_capacity());
p = elem_ + offset;
}
::memmove(p + 1, p, sizeof(T)*(elem_ + size_++ - p) );
*p = v;
}

resize函數(shù)：
將元素個數(shù)強制設置為n
template<typename T>
void Vector<T>::resize(unsigned ns)
{
reserve(ns);
size_ = ns;
}

交換內容函數(shù)：
template<typename T>
void swap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
交換兩向量內容：
template<typename T>
void swap(Vector<T>& a, Vector<T>& b)
{
std::swap(a.elem_, b.elem_);
std::swap(a.size_, b.size_);
std::swap(a.cpct_, b.cpct_);
}
std::swap 是TSL中的算法,；