1.vector容器机制
2.vector模拟与实现
#pragma once
#include <assert.h>namespace room
{template<class T>class vector{public:typedef T* iterator;// 指向数据不能修改，本身可以修改typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const iterator begin() const{return _start;}const iterator end() const{return _finish;}vector(){}vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}// 类模板的成员函数，也可以是一个函数模板// 这里就不知限制只有vector的迭代器初始化，string、list等迭代器都可以用template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}// v(10, 1.1)vector(size_t n, const T& val = T()){resize(n, val);}// 这里是为了避免使用上面的模板// 所以搞出来两份// v(10, 1)vector(int n, const T& val = T()){resize(n, val);}// 拷贝构造// v2(v1)//vector(const vector& v)vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}// 传统写法// v1 = v3//vector& operator=(const vector& v)//vector<T>& operator=(const vector<T>& v)//{// if (this != &v)// {// delete[] _start;// _start = _finish = _end_of_storage = nullptr;// reserve(v.size());// for (auto& e : v)// {// push_back(e);// }// }// return *this;//}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}// v1 = v3vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];// memcpy是一个浅拷贝，会出问题// 当拷贝一个字符串时，就会出现问题//memcpy(tmp, _start, sizeof(T) * oldSize);// 深拷贝for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_end_of_storage = _start + n;}}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void push_back(const T& x){// 扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;} void pop_back(){assert(_finish > _start);--_finish;}迭代器失效//void insert(iterator pos, const T& x)//{// assert(pos >= _start);// assert(pos <= _finish);// // 满了就扩容// if (_finish == _end_of_storage)// {// reserve(capacity() == 0 ? 4 : capacity() * 2);// }// iterator it = _finish - 1;// while (it >= pos)// {// *(it + 1) = *it;// --it;// }// *pos = x;// ++_finish;//}void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);// 满了就扩容，导致pos失效，失效后不能使用，更新后才能使用if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}迭代器失效 //void erase(iterator pos)//{// assert(pos >= _start);// assert(pos < _finish);// iterator it = pos + 1;// while (it < _finish)// {// *(it - 1) = *it;// ++it;// }// --_finish;//}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos; // 下一个位置还是pos}private:iterator _start = nullptr;iterator _finish = nullptr;;iterator _end_of_storage = nullptr;;};
}完
