namespace qgw {
	template <class T>
	class vector {
		typedef T* iterator;
        typedef const T* const_iterator;
		typedef T& reference;
	public:
		// 默認(rèn)成員函數(shù)
		vector();										// 默認(rèn)構(gòu)造函數(shù)
		vector(size_t n, const T& val = T());			// 構(gòu)造 n 個(gè) T 類(lèi)型對(duì)象
		vector(InputIterator first, InputIterator last);// 用一段區(qū)間構(gòu)造
		vector(const vector<T>& v);						// 拷貝構(gòu)造函數(shù)
		vector<T>& operator=(const vector<T>& v);		// 復(fù)制賦值函數(shù)
		~vector();

		// 迭代器函數(shù)
		iterator begin();
        const_iterator begin() const;
		iterator end();
        const_iterator end() const;

		// 元素訪問(wèn)
		reference operator[](size_t pos);
		const reference operator[](size_t pos) const;
		reference back();
		const reference back() const;

		// 容量
		bool empty() const;
		size_t size() const;
		size_t capacity() const;
		void resize(size_t cnt, T val = T());
		void reserve(size_t cap);

		// 修改
		iterator insert(iterator pos, const T& val);
		void push_back(const T& val);
		iterator erase(iterator pos);
		iterator erase(iterator first, iterator last);
		void pop_back();
		void swap(vector<T>& v);

	private:
		iterator _start;			// 表示目前使用空間的頭
		iterator _finish;			// 表示目前使用空間的尾
		iterator _end_of_storage;	// 表示已分配空間的尾
	};
}

/// @brief 默認(rèn)構(gòu)造函數(shù)，將指針初始化為空
vector() {                
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;
}

/// @brief 構(gòu)造 n 個(gè)值為 val 的對(duì)象
/// @param n 容器的大小
/// @param val 用來(lái)初始化容器元素的值
vector(size_t n, const T& val = T()) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    reserve(n);
    for (int i = 0; i < n; ++i) {
        push_back(val);
    }
}

/// @brief 用給定的迭代器區(qū)間初始化，STL 中的區(qū)間均為左閉右開(kāi)形式，即 [first, last)
/// @tparam InputIterator 所需最低階的迭代器類(lèi)型，具有輸入功能的迭代器都可以
/// @param first 迭代器起始位置
/// @param last 迭代器終止位置
template< class InputIterator>
    vector(InputIterator first, InputIterator last) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    // 和上一個(gè)類(lèi)似，先開(kāi)辟空間，尾減頭即為要開(kāi)辟的個(gè)數(shù)
    reserve(last - first);		
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

/// @brief 釋放開(kāi)辟的空間
~vector() {
    if (_start != nullptr) {
        // 釋放開(kāi)辟的空間，從此處可以看出，開(kāi)辟空間一定要用 new[]
        // 否則對(duì)于自定義類(lèi)型程序?qū)?huì)崩潰 
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _end_of_storage = nullptr;
    }
}

/// @brief 用給定容器初始化
/// @param v 用來(lái)初始化的容器
vector(const vector<T>& v) {
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

/// @brief 替換容器內(nèi)容
/// @param v 用作數(shù)據(jù)源的另一容器
/// @return *this
vector<T>& operator=(const vector<T>& v) {
    vector<T> tmp(v);
    swap(tmp);
    // 返回值為對(duì)象的引用，為的是可以連續(xù)賦值
    return *this;
}

typedef T* iterator;
typedef const T* const_iterator;

/// @brief 返回指向 vector 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
    return _start;
}

// const 版本供 const 容器使用
const_iterator begin() const {
    return _start;
}

/// @brief 返回指向 vector 最后元素后一元素的迭代器
/// @return 指向最后元素下一個(gè)位置的迭代器
iterator end() {
    return _finish;
}

const_iterator end() const {
    return _finish;
}

/// @brief 返回位于指定位置 pos 的元素的引用，不進(jìn)行邊界檢查
/// @param pos 要返回的元素的位置
/// @return 到所需元素的引用
reference operator[](size_t pos) {
    return _start[pos];
}

// 與上面的唯一不同就是用于 const 容器
const reference operator[](size_t pos) const {
    return _start[pos];
}

/// @brief 返回到容器中最后一個(gè)元素的引用
/// @return 最后元素的引用
reference back() {
    return *(end() - 1);
}

const reference back() const {
    return *(end() - 1);
}

/// @brief 返回容器中的元素?cái)?shù)
/// @return 容器中的元素?cái)?shù)量
size_t size() const {
    return _finish - _start;
}

/// @brief 返回容器當(dāng)前已為之分配空間的元素?cái)?shù)
/// @return 當(dāng)前分配存儲(chǔ)的容量
size_t capacity() const {
    return _end_of_storage - _start;
}

/// @brief 檢查容器是否無(wú)元素
/// @return 若容器為空則為 true，否則為 false
bool empty() const {
    return _start == _finish;
}

/// @brief 重設(shè)容器大小以容納 cot 個(gè)元素
/// @param cnt 容器的大小
/// @param val     用以初始化新元素的值
void resize(size_t cnt, T val = T()) {
    if (cnt < size()) {
        // 新大小小于原來(lái)的，需要將多余的部分刪除掉
        // 不能只改變 _finish 指向，要使用 erase 來(lái)刪除，以便調(diào)用析構(gòu)函數(shù)
        erase(begin() + cnt, end());
    } else {
        // 新空間更大，直接調(diào)用 insert 插入即可
        for (int i = 0; i < cnt - size(); ++i) {
            insert(end(), val);
        }
    }
}

/// @brief 增加 vector 的容量到大于或等于 cap 的值    
/// @param cap vector 的新容量
void reserve(size_t cap) {
    size_t len = size();
    if (cap > capacity()) {
        T* tmp = new T[cap];
        if (_start != nullptr) {
            // 如果容器內(nèi)之前有數(shù)據(jù)，將數(shù)據(jù)拷貝到新位置
            for (int i = 0; i < size(); ++i) {
                tmp[i] = _start[i];
            }
            delete[] _start;    // 釋放掉舊的空間
        }
        _start = tmp;
    }
    // 指向新的地址空間
    _finish = _start + len;
    _end_of_storage = _start + cap;
}

/// @brief 將 val 插入到 pos 迭代器之前
/// @param pos 	將內(nèi)容插入到它前面的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入 val 的迭代器
iterator insert(iterator pos, const T& val) {
    // 檢查參數(shù)是否在合法返回，assert 只在 degug 版本下有效
    assert(pos >= _start && pos <= _finish);

    if (_finish == _end_of_storage) {
        // 首先檢查容量，空間不夠要進(jìn)行擴(kuò)容
        // 先記錄插入位置之前元素個(gè)數(shù)
        size_t len = pos - _start;
        // 第一次開(kāi)辟空間給 10 個(gè)，后續(xù)擴(kuò)容為 2 倍
        size_t newCap = capacity() == 0 ? 10 : capacity() * 2;
        reserve(newCap);
        // 更新 pos 在新空間中的位置
        pos = _start + len;
    }

    // 將插入位置之后的所有數(shù)據(jù)向后挪動(dòng)一個(gè)位置
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end;
        --end;
    }
    *pos = val;
    ++_finish;
    return pos;
}

/// @brief 添加給定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const T& val) {
    // 直接調(diào)用 insert 即可
    insert(end(), val);
}

/// @brief 從容器擦除指定位置的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 移除元素之后的迭代器
iterator erase(iterator pos) {
    assert(pos >= _start && pos < _finish);
    // 在 pos 位置調(diào)用析構(gòu)函數(shù)，釋放資源
    pos->~T();
    // 將 pos 位置之后的的元素都向前移動(dòng)一個(gè)位置
    iterator it = pos + 1;
    while (it != _finish) {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    // 此時(shí)的 pos 指向沒(méi)刪除前 pos 位置下一個(gè)元素
    return pos;
}

/// @brief 移除一段范圍的元素
/// @param first 要移除的起始范圍
/// @param last 要移除的結(jié)束返回
/// @return 移除的最后一個(gè)元素之后的迭代器
iterator erase(iterator first, iterator last) {
    int cnt = last - first;
    while (cnt--) {
        first = erase(first);
    }
    return first;
}

/// @brief 移除容器最后一個(gè)元素
void pop_back() {
    erase(_finish - 1);
}

/// @brief 交換 this 指向的容器和 v 的內(nèi)容
/// @param v 要交換內(nèi)容的容器
void swap(vector<T>& v) {
    // 直接交換所有指針即可
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}