向量是一维数组在抽象数据类型框架中的推广,也可以说向量是用类来表示的一维数组。在以数组为基础的向量的数据模型上，还要定义一组关于向量的运算，才能使这一数据模型成为一个抽象数据类型。
下面给出一组典型的向量运算。
（1）size（）：向量的长度
（2）Empty（）：测试向量是否为空
（3）Capacity（）：向量的容量
（4）Resize（n）：重置向量的容量
（5）=：赋值运算
（6）Front（）：向量首元素
（7）Back（）：向量尾元素
（8）Push_back（）：向量尾插入元素
（9）Pop_back（）：删除向量尾的元素
（10）Begin（）：指向向量首的迭代器
（11）End（）：指向向量尾的下一个位置的迭代器
（12）Print_vector（）：指向向量尾中的下一个位置的迭代器
在向量的数据模型上，定义了这些运算后，就定义了一个抽象数据类型向量vector。（对于c++中已经封装号的vector的基本是用，请查看之前的博文《标准库vector》）
/*
* =====================================================================================
*
* Filename: vector.cc
*
* Description: 向量vector
*
* Version: 1.0
* Created: 2014年05月19日 11时27分48秒
* Revision: none
* Compiler: gcc
*
* Author: leiyu, leiyujike1107@gmail.com
* Company: Class 1107 of Computer Science and Technology
*
* =====================================================================================
*/
#include <iostream>
using namespace std;
template <class T>
class vector
{
public:
typedef T *iterator;
typedef const T *const_iterator;
vector(int size = 0, const T& value = 0); //构造函数
vector(const vector<T>& obj); //赋值构造函数
vector(const_iterator first, const_iterator last); //构造函数
~vector() //析够函数
{
if (start)
delete []start;
}
vector& operator= (const vector<T>& rhs); //赋值运算
T& front(); //向量首元素
const T& front() const;
T& back(); //向量尾元素
const T& back() const;
void push_back(const T& item); //向量尾插入一个元素
void pop_back(); //删除向量尾的元素
int size() const
{
return sz;
}
void resize(int new_size, const T& x); //重置向量长度
bool empty() const //检测向量是否为空
{
return sz == 0;
}
int capacity() const //向量的容量
{
return maxsz;
}
void print_vector(ostream& out) const; //输出向量
void print_reverse(ostream& out) const; //反向输出向量
iterator begin() //指向向量首的迭代器
{
return start;
}
const_iterator begin() const
{
return start;
}
iterator end() //指向向量尾的下一个位置的迭代器
{
return sz+start;
}
const_iterator end() const
{
return sz+start;
}
T& operator[](int n) //随机存取运算符
{
return *(begin()+n);
}
const T& operator[] (int n) const
{
return *(begin()+n);
}
private:
iterator start; //向量内存单元起始地址
int sz; //向量中元素的个数
int maxsz; //分配给向量的可用空间
void reserve(int n, bool copy); //给向量分配内存空间
};
template <class T>
void vector<T>::reserve(int n, bool copy)
{//给向量分配内存空间
T *tmp = new T[n];
if (tmp == 0)
//throw no_mem();
return;
for (int i = 0; i < n; i++)
tmp[i] = T();
if (sz>n)
sz = n;
//当copy为true时，进行复制
if (copy)
{
for (int i = 0; i < sz; i++)
tmp[i] = start[i];
}
if (start)
delete []start;
start = tmp;
maxsz = n;
}
template <class T>
vector<T>::vector(int size, const T& value):sz(0), maxsz(0), start(0)
{//构造函数
if (size == 0)
return;
reserve(size, false); //申请内存空间
sz = size;
for (int i = 0; i < sz; i++)
start[i] = value;
}
template <class T>
vector<T>::vector(const vector<T>& obj):sz(0), maxsz(0), start(0)
{//复制构造函数
if (obj.sz == 0)
return;
reserve(obj.sz, false);
sz = obj.sz;
for (int i = 0; i < sz; i++)
start[i] = obj.start[i];
}
template <class T>
vector<T>::vector(const_iterator first, const_iterator last):maxsz(0), start(0)
{//构造函数
sz = last - first;
reserve(sz, false);
for (int i = 0; i < sz; i++)
start[i] = first[i];
}
template <class T>
void vector<T>::resize(int new_size, const T& x)
{//重置向量长度
reserve(new_size, true); //重新申请内存空间
for (int i = 0; i < new_size; i++) //值初始化
start[i] = x;
sz = new_size; //新向量长度
}
template <class T>
vector<T>& vector<T>::operator=(const vector<T>& rhs)
{//赋值运算
if (maxsz < rhs.sz)
reserve(rhs.sz, false); //申请内存空间
sz = rhs.sz; //向量长度
for (int i = 0; i < sz; i++)
start[i] = rhs.start[i]; //赋值
return *this;
}
template <class T>
T& vector<T>::front()
{//向量首元素
if (sz == 0)
// throw out_bounds();
return;
return start[0];
}
template <class T>
const T& vector<T>::front() const
{//向量首元素
if (sz == 0)
//throw out_bounds();
return;
return start[0];
}
template <class T>
T& vector<T>::back()
{//向量尾元素
if (sz == 0)
// throw out_bounds();
return;
return start[sz-1];
}
template <class T>
const T& vector<T>::back() const
{//向量尾元素
if (sz == 0)
//throw out_bounds();
return;
return start[sz-1];
}
template <class T>
void vector<T>::push_back(const T& item)
{//向量尾插入元素
if(sz == maxsz) //已经达到最大容量
{
if (maxsz == 0)
reserve(1, false);
else
reserve(2*maxsz, true); //向量容量扩大一倍
}
start[sz] = item;
sz++;
}
template <class T>
void vector<T>::pop_back()
{//删除向量尾与元素
if (sz == 0)
// throw out_bonuds();
return;
sz--;
}
template <class T>
void vector<T>::print_vector(ostream& out) const
{//向量元素送到输出流out中
const_iterator pointer;
for (pointer = begin(); pointer != end(); pointer++)
out << *pointer << " ";
}
template <class T>
void vector<T>::print_reverse(ostream& out) const
{//向量元素反向输出到out中
const_iterator pointer;
for (pointer = end(); pointer >= begin(); pointer--)
out << *pointer << " ";
out << endl;
}
//重载<<输出运算符
template <class T>
ostream& operator<<(ostream& out, const vector<T>& x)
{
x.print_vector(out);
return out;
}