开始学习 STL源码剖析
已经学习了前两章 有关内存管理 以及 迭代器
下面 先尝试自己写vector再根据源代码进行 修改 以下为代码
#ifndef _VECTOR_H #define _VECTOR_H #include "alloc.h" #define _VECTOR_OVERFLOW std::cerr<<"Vector overflow"<<std::endl; exit(1) template<class T,class Alloc = alloc> class vector { 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; protected: iterator start; iterator finish; iterator end_of_storage; simple_alloc<value_type, Alloc> data_allocater; void refill() { size_type gap = finish - start; size_type old_sz = end_of_storage - start; size_type new_sz = 2 * old_sz + 1; if (!start) start = (iterator)data_allocater.allocate(new_sz); else start = (iterator)data_allocater.reallocate(start, old_sz, new_sz); finish = start + gap; end_of_storage = start + new_sz; } public: ~vector() { if (start) data_allocater.dellocate(start, (size_t)(end_of_storage - start)); } vector() : start(0),finish(0),end_of_storage(0) {} iterator begin() { return start; } iterator end() { return finish; } size_type size() const { return (size_type)(finish - start); } size_type capacity() const { return (size_type)(end_of_storage - start); } bool empty() const { return start == finish; } reference front() { return *start; } reference back() { return *(finish - 1); } void push_back(const_reference value) { if (finish == end_of_storage) refill(); *finish++ = value; } reference operator[](size_type n) { if (start + n >= finish) { _VECTOR_OVERFLOW; } return *(start + n); } void erase(iterator i) { size_type copy_sz = finish - i - 1; memcpy(i, i + 1, copy_sz * sizeof(int)); --finish; } void erase(iterator low, iterator up) { memcpy(low, up + 1, (finish - up - 1)*sizeof(value_type)); finish -= (up - low + 1); } void insert(iterator i, const_reference value) { size_type locate = i - start; if (finish == end_of_storage) refill(); memcpy(start + locate + 1, start + locate, (finish - start - locate)*sizeof(value_type)); *(start + locate) = value; ++finish; } void insert(iterator i, size_type n, const_reference value) { size_type locate = i - start; if (finish == end_of_storage) refill(); memcpy(start + locate + n, start + locate, (finish - start - locate) * sizeof(value_type)); for(size_type t=0;t<n;++t) *(start + locate + t) = value; finish += n; } void resize(size_type new_sz, const_reference value) { if (new_sz > size()) insert(finish, new_sz-size(), value); else erase(start + new_sz, finish - 1); } void resize(size_type n) { resize(n, 0); } void clear() { if(start) data_allocater.dellocate(start, (size_t)(end_of_storage - start)); start = finish = end_of_storage = 0; } }; #endif // !_VECTOR_H
以下为 借鉴书上代码改正的 主要改了以下几点
1. 数据的 构造 与 析构 的问题
2. 扩充缓冲区大小计算的问题 由原来oldsize的两倍 改为了 2*(oldsize + needsize)
3. 坚持贯彻左闭右开 将erase改正
4. 由于没写 copy 因此 都是用的memcpy 因此 拷贝时 也没有构造析构的过程
#ifndef _WVECTOR_H #define _WVECTOR_H #include "alloc.h" #include "stl_construct.h" #define _VECTOR_OVERFLOW std::cerr<<"Vector overflow"<<std::endl; exit(1) template<class T, class Alloc = alloc> class vector { 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; protected: iterator start; iterator finish; iterator end_of_storage; simple_alloc<value_type, Alloc> data_allocater; void refill(size_type need_sz) { size_type gap = finish - start; size_type old_sz = end_of_storage - start; size_type new_sz = 2 * (old_sz + need_sz); if (!start) start = (iterator)data_allocater.allocate(new_sz); else start = (iterator)data_allocater.reallocate(start, old_sz, new_sz); finish = start + gap; end_of_storage = start + new_sz; } void dellocate() { if (start) data_allocater.dellocate(start, (size_t)(end_of_storage - start)); } public: ~vector() { destroy(start, finish); dellocate(); } vector() : start(0), finish(0), end_of_storage(0) {} iterator begin() { return start; } iterator end() { return finish; } size_type size() const { return (size_type)(finish - start); } size_type capacity() const { return (size_type)(end_of_storage - start); } bool empty() const { return start == finish; } reference front() { return *start; } reference back() { return *(finish - 1); } void push_back(const_reference value) { if (finish == end_of_storage) refill(1); construct(finish++, value); } reference operator[](size_type n) { if (start + n >= finish) { _VECTOR_OVERFLOW; } return *(start + n); } void erase(iterator i) { size_type copy_sz = finish - i - 1; if(copy_sz) memcpy(i, i + 1, copy_sz * sizeof(int)); destroy(--finish); } void erase(iterator low, iterator up) { memcpy(low, up, (finish - up) * sizeof(value_type)); destroy(finish - (up - low), finish); finish -= (up - low); } void insert(iterator i, const_reference value) { size_type locate = i - start; if (finish == end_of_storage) refill(1); memcpy(start + locate + 1, start + locate, (finish - start - locate) * sizeof(value_type)); *(start + locate) = value; ++finish; } void insert(iterator i, size_type n, const_reference value) { size_type locate = i - start; if (finish == end_of_storage) refill(n); memcpy(start + locate + n, start + locate, (finish - start - locate) * sizeof(value_type)); for (size_type t = 0; t<n; ++t) *(start + locate + t) = value; finish += n; } void resize(size_type new_sz, const_reference value) { if (new_sz > size()) insert(finish, new_sz - size(), value); else erase(start + new_sz, finish); } void resize(size_type n) { resize(n, T()); } void clear() { destroy(start, finish); finish = start; } }; #endif // !_WVECTOR_H
