详解C++ STL模拟实现vector

namespace qgw { template  class vector { typedef T* iterator; typedef const T* const_iterator; typedef T& reference; public: // 默认成员函数 vector();										// 默认构造函数 vector(size_t n, const T& val = T());			// 构造 n 个 T 类型对象 vector(InputIterator first, InputIterator last);// 用一段区间构造 vector(const vector& v);						// 拷贝构造函数 vector& operator=(const vector& v);		// 复制赋值函数 ~vector(); // 迭代器函数 iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; // 元素访问 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& v); private: iterator _start;			// 表示目前使用空间的头 iterator _finish;			// 表示目前使用空间的尾 iterator _end_of_storage;	// 表示已分配空间的尾 }; } 

/// @brief 默认构造函数，将指针初始化为空 vector() { _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; } 

/// @brief 构造 n 个值为 val 的对象 /// @param n 容器的大小 /// @param val 用来初始化容器元素的值 vector(size_t n, const T& val = T()) { _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; reserve(n); for (int i = 0; i 

/// @brief 用给定的迭代器区间初始化，STL 中的区间均为左闭右开形式，即 [first, last) /// @tparam InputIterator 所需最低阶的迭代器类型，具有输入功能的迭代器都可以 /// @param first 迭代器起始位置 /// @param last 迭代器终止位置 template vector(InputIterator first, InputIterator last) { _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; // 和上一个类似，先开辟空间，尾减头即为要开辟的个数 reserve(last - first); while (first != last) { push_back(*first); ++first; } } 

/// @brief 释放开辟的空间 ~vector() { if (_start != nullptr) { // 释放开辟的空间，从此处可以看出，开辟空间一定要用 new[] // 否则对于自定义类型程序将会崩溃 delete[] _start; _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; } } 

/// @brief 用给定容器初始化 /// @param v 用来初始化的容器 vector(const vector& v) { _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; vector tmp(v.begin(), v.end()); swap(tmp); } 

/// @brief 替换容器内容 /// @param v 用作数据源的另一容器 /// @return *this vector& operator=(const vector& v) { vector tmp(v); swap(tmp); // 返回值为对象的引用，为的是可以连续赋值 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 指向最后元素下一个位置的迭代器 iterator end() { return _finish; } const_iterator end() const { return _finish; } 

/// @brief 返回位于指定位置 pos 的元素的引用，不进行边界检查 /// @param pos 要返回的元素的位置 /// @return 到所需元素的引用 reference operator[](size_t pos) { return _start[pos]; } // 与上面的唯一不同就是用于 const 容器 const reference operator[](size_t pos) const { return _start[pos]; } 

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

/// @brief 返回容器中的元素数 /// @return 容器中的元素数量 size_t size() const { return _finish - _start; } 

/// @brief 返回容器当前已为之分配空间的元素数 /// @return 当前分配存储的容量 size_t capacity() const { return _end_of_storage - _start; } 

/// @brief 检查容器是否无元素 /// @return 若容器为空则为 true，否则为 false bool empty() const { return _start == _finish; } 

/// @brief 重设容器大小以容纳 cot 个元素 /// @param cnt 容器的大小 /// @param val     用以初始化新元素的值 void resize(size_t cnt, T val = T()) { if (cnt 

/// @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) { // 如果容器内之前有数据，将数据拷贝到新位置 for (int i = 0; i 

/// @brief 将 val 插入到 pos 迭代器之前 /// @param pos 	将内容插入到它前面的迭代器 /// @param val 要插入的元素值 /// @return 指向被插入 val 的迭代器 iterator insert(iterator pos, const T& val) { // 检查参数是否在合法返回，assert 只在 degug 版本下有效 assert(pos >= _start && pos <= _finish); if (_finish == _end_of_storage) { // 首先检查容量，空间不够要进行扩容 // 先记录插入位置之前元素个数 size_t len = pos - _start; // 第一次开辟空间给 10 个，后续扩容为 2 倍 size_t newCap = capacity() == 0 ? 10 : capacity() * 2; reserve(newCap); // 更新 pos 在新空间中的位置 pos = _start + len; } // 将插入位置之后的所有数据向后挪动一个位置 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) { // 直接调用 insert 即可 insert(end(), val); } 

/// @brief 从容器擦除指定位置的元素 /// @param pos 指向要移除的元素的迭代器 /// @return 移除元素之后的迭代器 iterator erase(iterator pos) { assert(pos >= _start && pos <_finish); // 在 pos 位置调用析构函数，释放资源 pos->~T(); // 将 pos 位置之后的的元素都向前移动一个位置 iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; // 此时的 pos 指向没删除前 pos 位置下一个元素 return pos; }

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

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

/// @brief 交换 this 指向的容器和 v 的内容 /// @param v 要交换内容的容器 void swap(vector& v) { // 直接交换所有指针即可 std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }