vector.h

一个我的数据结构解题集合

#ifndef VECTOR_H__
#define VECTOR_H__

#include <algorithm>	// 使用std::swap
#include <sstream>		// 使用std::stringstream
#include <stdexcept>

template <typename T>
class Vector {
private:

	enum {
		INIT_SIZE = 10		// 初始大小, 必须大于0
	};

	/* 数据内部存储结构为循环存储结构
	 * data_	 指向被分配内存的首地址;
	 * begin_	 首个有效数据的下标;
	 * end_		 最后一个有效数据下标逻辑上的后一位
	 * capacity_ 已分配的空间大小
	 *
	 *	数据储存于 [begin_, end_) 区间内
	 *	以begin_ == end_作为Vector为空标志,
	 *	为data_分配的空间总比实际利用空间多至少1,
	 *	以检查Vector满的情况
	 */
	T *data_;
	int begin_;
	int end_;
	int capacity_;

	/* 检查参数index是否在合法范围内, 
	 * 若超出范围, 抛出std::out_of_range异常, 
	 * 否则返回
	 */
	void checkRange(int index) const {
		if ( 0 <= index && index < size() ) return;

		using namespace std;
		// 生成错误信息
		stringstream buf;
		buf << "Vector: Index out of range!\n"
			<< "\tSize: "	<< size()
			<< "\tIndex: "	<< index
			<< endl;

		throw out_of_range(buf.str());

	} // checkRange(int) const

	/* 返回逻辑上index的下一个位置
	 */
	int incr(int index) const {
		return (index+1) % capacity_;
	} // incr(int) const

	/* 返回逻辑上index的上一个位置
	 */
	int decr(int index) const {
		if (index == 0)
			return capacity_-1;
		else
			return index-1;
	} // decr(int) const

public:

	/* 构造函数, 初始化Vector使之为空并且有保留INIT_SIZE个T的空间
	 */
	Vector() {
		data_ = new T[INIT_SIZE];
		capacity_ = INIT_SIZE;
		begin_ = end_ = 0;
	} // Vector()

	/* 拷贝构造函数, 从that创建Vector,
	 * 使被创建的Vector所具有的元素和that相同
	 */
	Vector(const Vector& that) {
		capacity_ = that.size() + INIT_SIZE;	// 确定分配空间大小

		data_ = new T[capacity_];	// 分配空间

		// 拷贝数据
		for (int i=0, j=that.begin_; j != that.end_; ++i, j=that.incr(j)) {
			data_[i] = that.data_[j];
		}
		
		// 更新成员数据
		begin_ = 0;
		end_ = that.size();

	} // Vector(const Vector&)

	/* 析构函数, 清理所占用的资源
	 */
	~Vector() {
		delete [] data_;
	} // ~Vector()

	/* 赋值操作将当前Vector赋值为that
	 */
	Vector& operator=(const Vector& that) {
		if (this == &that) return *this;	// 自我赋值

		Vector v(that);		// 拷贝that的值
		swap(v);			// 保存到this

		return *this;
	} // operator=(const Vector&)

	/* 交换两个Vector的内容
	 */
	void swap(Vector& that) {
		if (this == &that) return;	// 自我交换

		using std::swap;
		swap(data_, that.data_);
		swap(begin_, that.begin_);
		swap(end_, that.end_);
		swap(capacity_, that.capacity_);
	} // swap(Vector&)

	/* 将元素e插入Vector的头部
	 * 若空间不足自动分配
	 */
	void pushFront(const T& e) {
		if ( size()+1 >= capacity_ )
			reserve(1 + capacity_*1.5);
		data_[decr(begin_)] = e;
		begin_ = decr(begin_);
	} // pushFront(const T&)

	/* 将元素e插入Vector的尾端
	 * 若空间不足自动分配
	 */
	void pushBack(const T& e) {
		if ( size()+1 >= capacity_ )
			reserve(1 + capacity_*1.5);
		data_[end_] = e;
		end_ = incr(end_);
	} // pushBack(const T&)

	/* 将头部元素删除
	 * 如果Vector为空, 抛出std::underflow_error异常
	 */
	void removeFront() {
		if (size() <= 0) {
			throw std::underflow_error("Vector: Underflow!\n"
									   "\tOperation: removeFront()\n");
		}
		begin_ = incr(begin_);
	} // removeFront()

	/* 将尾部元素删除
	 * 如果Vector为空, 抛出std::underflow_error异常
	 */
	void removeBack() {
		if (size() <= 0) {
			throw std::underflow_error("Vector: Underflow!\n"
									   "\tOperation: removeBack()\n");
		}
		end_ = decr(end_);
	} // removeBack()

	/* 查询头部元素
	 * 如果Vector为空, 抛出std::out_of_range异常
	 */
	const T& front() const {
		checkRange(0);
		return data_[begin_];
	} // front() const

	/* 查询尾部元素
 	 * 如果Vector为空, 抛出std::out_of_range异常
	 */
	const T& back() const {
		checkRange(size()-1);
		return data_[decr(end_)];
	} // back() const

	/* 查询位置为index的元素
	 * 如果index不满足 0 <= index && index < size(),
	 * 抛出out_of_range异常
	 * 提供const和非const两个版本
	 */
	T& operator[](int index) {
		checkRange(index);
		return data_[(begin_ + index) % capacity_];
	} // operator[](int)

	const T& operator[](int index) const {
		checkRange(index);
		return data_[(begin_ + index) % capacity_];
	} // operator[](int) const


	/* 预留至少capacity的空间
	 */
	void reserve(int capacity) {
		if (capacity <= capacity_) return;	// 需要的空间已经被满足

		T *new_data = new T[capacity];		// 分配新的空间

		// 拷贝数据
		int i, j;
		for (i=0, j=begin_; j != end_; ++i, j=incr(j)) {
			new_data[i] = data_[j];
		}

		delete [] data_;					// 释放旧的空间

		// 更新成员数据
		data_ = new_data;
		capacity_ = capacity;

		begin_ = 0;
		end_ = i;

	} // reserve(int)

	/* 将向量增大到sz大小
	 */
	void enlarge(int sz) {
		reserve(sz+1);
		end_ = (begin_ + sz) % capacity_;
	} // enlarge(int)

	/* 查询预留空间的大小
	 */
	int capacity() const {
		return capacity_;
	} // capacity() const

	/* 查询Vector中现存元素的数目
	 */
	int size() const {
		return (begin_ <= end_) ?
			   (end_ - begin_) :
			   (end_ + capacity_ - begin_);
	} // size() const

	/* 查询Vector是否为空
	 */
	bool isEmpty() const {
		return size() == 0;
	} // isEmpty() const

}; // Vector



#endif // VECTOR_H__