Vector类模板界面及其函数的实现

Vector 界面
template<typename T>

struct Vector {                                                 //T的构造函数为空；
Vector(unsigned n = 0, T const& t = T());       //构造函数；
Vector(Vector const& me);                              //拷贝构造函数；
Vector& operator=(Vector const& rhs);           //对赋值运算符=的重载；
virtual ~Vector(void);                                       //析构函数；
void clear(void);                                               //清空函数，将向量变为空；
bool empty(void) const;                                   //判断向量是否为空；
unsigned size(void) const;                               //返回向量中元素个数；
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_;                                                //向量中实际元素个数；
unsigned cpct_;                                               //向量容量；
protected:
bool full(void) const;                                        //判满函数；
unsigned next_capacity(void) const;               //内存管理策略；
};
template<typename T>                                   
void swap(Vector<T>& a, Vector<T>& b);     //交换两个向量的内容；

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

具体函数实现：

构造函数：
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中的算法，它将未初始化的内存填充一个固定的值；

 

拷贝构造函数
创建一个内容和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函数保证自身至少容纳一定量的元素，赋值运算符返回对自身的引用；

 

析构函数：
template<typename T>
Vector<T>::~Vector(void)
{
::free(elem_);
}

清空函数：
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函数的实现：
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;
}
}

判满函数：
full()
template<typename T>
bool Vector<T>::full(void) const
{
return size_ == cpct_;
}

 

添加函数：
在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函数：
将元素个数强制设置为n
template<typename T>
void Vector<T>::resize(unsigned ns)
{
reserve(ns);
size_ = ns;
}

 

交换内容函数：
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中的算法；