/*************************************** * Description:vector实现 * Create:2019/11/22 * Author:zhangfeng * History: * 2019-11-22 搭建基本框架和实现基本功能 * 2019-11-27 添加了元素访问 * 2019-11-28 添加了容量相关 * reserve涉及到元素的拷贝复制，有性能的开销 * 2019-11-29 补齐元素修改器 * *************************************/ #include <memory> #include <iostream> #include <algorithm> #include <cstddef> template<class T, class Alloc=std::allocator<T>> class mVector { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type* iterator; typedef const value_type* const_iterator; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; public: mVector() : _start(0), _finish(0), _end_of_storage(0) {} mVector(size_type n); mVector(size_type n, const T& value); //复制构造函数 mVector( const mVector& other ); mVector& operator=(const mVector& rhs); ~mVector(); iterator begin() { return _start; } const_iterator begin() const { return _start; } iterator end() { return _finish; } const_iterator end() const { return _finish; } //容量 bool empty() const { return begin() == end(); } size_type max_size() const { return size_type(-1) / sizeof(T); } void reserve(size_type new_cap); size_type size() const { return size_type(end() - begin()); } size_type capacity() const { return size_type(_end_of_storage - begin()); } //修改器 void clear(); void push_back( const T& value ); void pop_back(); void swap(mVector & value); iterator erase(iterator pos); iterator erase(iterator first, iterator last); iterator insert( iterator pos, const T& value ); void insert( iterator pos, size_type count, const T& value ); void resize( size_type count, T value = T() ){ if(count < size()) { erase(begin() + count, end()); }else{ insert(end(), count - size(), value); } } //元素访问 reference at(size_type pos); reference operator[](size_type pos) { return *(begin() + pos); } const_reference operator[](size_type pos) const { return *(begin() + pos); } reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return *(end() - 1); } const_reference back() const { return *(end() - 1); } protected: iterator _start; //使用起始空间 iterator _finish; //使用结束空间 iterator _end_of_storage; //实际空间尾 Alloc _alloc; protected: void _insert_aux(iterator _position, const T& _x); //对象析构 void _destroy(iterator _first, iterator _last); }; template<class T, class Alloc> mVector<T, Alloc>::mVector(size_type n) : _start(0), _finish(0), _end_of_storage(0) { _start = _alloc.allocate(n); _finish = _start; _end_of_storage = _start + n; } template<class T, class Alloc> mVector<T, Alloc>::mVector(size_type n, const T& value) : _start(0), _finish(0), _end_of_storage(0) { _start = _alloc.allocate(n); std::uninitialized_fill_n(_start, n, value); _finish = _end_of_storage = _start + n; } template<class T, class Alloc> mVector<T, Alloc>::mVector( const mVector& other ) : _start(0), _finish(0), _end_of_storage(0) { std::cout << "mVector copy construct ..." << std::endl; _start = _alloc.allocate(other.size()); _finish = _end_of_storage = std::uninitialized_copy(other.begin(), other.end(), _start); } template<class T, class Alloc> mVector<T, Alloc> &mVector<T, Alloc>::operator=(const mVector& rhs) { if(&rhs != this){ std::cout << "mVector operator= ..." << std::endl; size_type _len = rhs.size(); if(_len > capacity()){ iterator _new_start = _alloc.allocate(rhs.size()); iterator _new_finish = std::uninitialized_copy(rhs.begin(), rhs.end(), _new_start); _destroy(_start, _finish); //释放内存 _alloc.deallocate(_start, _end_of_storage-_start); _start = _new_start; _end_of_storage = _new_start + _len; } else if( _len <= size()) { iterator i = std::copy(rhs.begin(), rhs.end(), begin()); _destroy(i, _finish); } else { std::copy(rhs.begin(), rhs.begin() + size(), begin()); std::uninitialized_copy(rhs.begin() + size(), rhs.end(), _finish); } _finish = _start + _len; } return *this; } template<class T, class Alloc> mVector<T, Alloc>::~mVector() { std::cout << "~mVector" << std::endl; _destroy(_start, _finish); //释放内存 _alloc.deallocate(_start, _end_of_storage-_start); _start = _finish = _end_of_storage = NULL; } template<class T, class Alloc> void mVector<T, Alloc>::_destroy(iterator _first, iterator _last) { for(; _first != _last; _first++){ _alloc.destroy(_first); } } template<class T, class Alloc> void mVector<T, Alloc>::_insert_aux(iterator _position, const T& _x) { if(_finish != _end_of_storage){ _alloc.construct(_finish, *(_finish - 1)); ++_finish; T _x_copy = _x; std::copy_backward(_position, _finish - 2, _finish -1); *_position = _x_copy; }else{ const size_type _old_size = size(); const size_type _len = _old_size != 0 ? 2 * _old_size : 1; iterator _new_start = _alloc.allocate(_len); iterator _new_finish = _new_start; try{ // 复制来自范围 [_start, _position) 的元素到始于 _new_start 的未初始化内存 _new_finish = std::uninitialized_copy(_start, _position, _new_start); _alloc.construct(_new_finish, _x); ++_new_finish; _new_finish = std::uninitialized_copy(_position, _finish, _new_finish); }catch(...){ _destroy(_new_start, _new_finish); _alloc.deallocate(_new_start, _len); } _destroy(_start, _finish); _alloc.deallocate(_start, _end_of_storage - _start); _start = _new_start; _finish = _new_finish; _end_of_storage = _new_start + _len; } } template<class T, class Alloc> void mVector<T, Alloc>::push_back( const T& value ) { if(_finish != _end_of_storage) { _alloc.construct(_finish, value); ++_finish; }else{ _insert_aux(_finish, value); } } template<class T, class Alloc> void mVector<T, Alloc>::pop_back() { if(_start != _finish) { --_finish; _alloc.destroy(_finish); } } template<class T, class Alloc> void mVector<T, Alloc>::swap(mVector & value) { std::swap(_start, value._start); std::swap(_finish, value._finish); std::swap(_end_of_storage, value._end_of_storage); } template<class T, class Alloc> typename mVector<T, Alloc>::reference mVector<T, Alloc>::at(size_type pos) { if(pos >= size() || pos < 0) throw std::range_error("vector"); return (*this)[pos]; } template<class T, class Alloc> void mVector<T, Alloc>::reserve(size_type new_cap) { if(capacity() < new_cap){ const size_type _old_size = size(); iterator _new_start = _alloc.allocate(new_cap); try { std::uninitialized_copy(_start, _finish, _new_start); }catch(...){ _alloc.deallocate(_new_start, new_cap); } _destroy(_start, _finish); _alloc.deallocate(_start, _end_of_storage - _start); _start = _new_start; _finish = _start + _old_size; _end_of_storage = _start + new_cap; } } template<class T, class Alloc> typename mVector<T, Alloc>::iterator mVector<T, Alloc>::erase(iterator pos) { if ( pos+1 != end()) { std::copy( pos+1, _finish, pos); } --_finish; _alloc.destroy(_finish); return pos; } template<class T, class Alloc> typename mVector<T, Alloc>::iterator mVector<T, Alloc>::erase(iterator first, iterator last) { iterator it = std::copy(last, _finish, first); _destroy(it, _finish); _finish = _finish - (last - first); return first; } template<class T, class Alloc> typename mVector<T, Alloc>::iterator mVector<T, Alloc>::insert( iterator pos, const T& value ) { size_type _n = pos -begin(); insert(pos, 1, value); return begin() + _n; } template<class T, class Alloc> void mVector<T, Alloc>::insert( iterator pos, size_type count, const T& value ) { if (count != 0) { //备用空间大于新增元素个数 if( size_type(_end_of_storage - _finish) >= count) { T _x_copy = value; //计算pos之后元素个数 const size_type _elems_after = _finish - pos; iterator _old_finish = _finish; if (_elems_after > count) { std::uninitialized_copy(_finish - count, _finish, _finish); _finish += count; std::copy_backward(pos, _old_finish - count, _old_finish); std::fill(pos, pos + count, _x_copy); }else{ std::uninitialized_fill_n(_finish, count-_elems_after, _x_copy); _finish += count - _elems_after; std::uninitialized_copy(pos, _old_finish, _finish); _finish += _elems_after; std::fill(pos, _old_finish, _x_copy); } }else{ //空间不足，需要申请空间 const size_type __old_size = size(); const size_type __len = __old_size + std::max(__old_size, count); iterator __new_start = _alloc.allocate(__len); iterator __new_finish = __new_start; try{ __new_finish = std::uninitialized_copy(_start, pos, __new_start); std::uninitialized_fill_n(__new_finish, count, value); __new_finish = std::uninitialized_copy(pos, _finish, __new_finish + count); }catch(...){ _destroy(__new_start, __new_finish); _alloc.deallocate(__new_start, __len); } _destroy(_start, _finish); _alloc.deallocate(_start, _end_of_storage - _start); _start = __new_start; _finish = __new_finish; _end_of_storage = _start + __len; } } }