大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
最近仔细阅读了下侯捷老师的《STL源码剖析》的前三章内容：空间配置器、迭代器、traits技术，为了加强理解和掌握，特参照源码自实现Vector,以下对相关重点知识进行说明。
1. vector实现框架
2. 空间配置器
空间配置器方面的内容在之前的博客已进行详细说明，查看->STL空间配置器解析和实现.
3. 内存基本处理工具
（1）对象构造
（2）Destroy()函数的泛化和特化版本实现，主要体现对象T是否包含trivial construct
（3）迭代器范围赋值
（4）迭代器范围拷贝
template<class T1, class T2> void Construct(T1* p, const T2& value) { new (p) T1(value); // placement new;调用T1::T1(value) } template<class T> void Destroy(T* p) { p->~T(); p = NULL; } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last) { ForwardIterator iter = first; while (iter != last) { typedef typename TRAITS_DEFINE::iterator_traits<ForwardIterator>::value_type T; cout << typeid(T).name(); T p = (T)*iter; Destroy(&p); iter++; } } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last, TRAITS_DEFINE::__true_type) { ; } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last, TRAITS_DEFINE::__false_type) { for (; first<last; first++) { Destroy(&*first) } } template<class ForwardIterator, class T> void Destroy(ForwardIterator first, ForwardIterator last, T*) { typedef typename TRAITS_DEFINE::__type_traits<T>::has_trivial_destructor trivial_destructor; Destroy(first, last, trivial_destructor()); } template<class OutputIterator> OutputIterator uninitialized_fill_n_ex(OutputIterator iter, const size_type& nSize, const T& nValue) { for (size_t i = 0; i < nSize; i++) { *iter++ = nValue; } return iter; } void Fill_Initialize(const size_type& nSize, const T& nValue) { Iterator iter = data_allocator::Allocate(nSize); uninitialized_fill_n_ex(iter, nSize, nValue); Start = iter; Finish = Start + nSize; EndOfStorage = Finish; } template<class InputIterator, class OutputIterator> OutputIterator uninitialzed_copy_ex(InputIterator first, InputIterator last, OutputIterator dest) { for (; first != last; first++,dest++) { *dest = *first; } return dest; }
View Code
4. iterator_traites和type_traits
类型萃取实现的关键计数在于“模版特例化”，通过class template partial specialization的作用，不论是原生指针或class-type iterators,都可以让外界方便地取其相应类别
原生指针不是class type,如果不是class type就无法为它定义内嵌型别。但模板特例化解决了该问题
template<class T>
class C{…}; // 这个泛化版本允许（接受）T为任何型别
template<class T>
class C<T*>{…}; // 这个特化版本仅适用于“T为原生指针”的情况
type_traits类型萃取，判断T类型中是否含有trivial construct,这样在destroy函数的就可以根据其做相应的处理
namespace TRAITS_DEFINE { template<class T> struct iterator_traits { typedef T value_type; }; template<class T> struct iterator_traits<T *> { typedef T value_type; }; struct __true_type{}; struct __false_type{}; template<class type> struct __type_traits { typedef __true_type this_dummy_must_be_first; typedef __false_type has_trivial_default_constructor; typedef __false_type has_trivial_copy_constructor; typedef __false_type has_trivial_assignment_operator; typedef __false_type has_trivial_destructor; typedef __false_type is_POD_type; }; template<> struct __type_traits<int> { typedef __true_type this_dummy_must_be_first; typedef __true_type has_trivial_default_constructor; typedef __true_type has_trivial_copy_constructor; typedef __true_type has_trivial_assignment_operator; typedef __true_type has_trivial_destructor; typedef __true_type is_POD_type; }; }
View Code
5. vector代码实现
5.1. 构造
typedef T& Reference; typedef T* Iterator; typedef T value_type; typedef size_t size_type; typedef CSimpleAlloc<value_type> data_allocator; // 自定义空间配置器 Iterator Start; Iterator Finish; Iterator EndOfStorage;
Vector():Start(NULL), Finish(NULL),EndOfStorage(NULL){
cout << “Vector()” << endl;
}
Vector(const size_type& nSize, const T& nValue)
{
Fill_Initialize(nSize, nValue);
}
explicit Vector(const size_type& nSize)
{
Fill_Initialize(nSize, T());
}
void Fill_Initialize(const size_type& nSize, const T& nValue) { Iterator iter = data_allocator::Allocate(nSize); uninitialized_fill_n_ex(iter, nSize, nValue); Start = iter; Finish = Start + nSize; EndOfStorage = Finish; }
5.2. 析构
void Deallocate() { if (Start) { data_allocator::Deallocate(Start, EndOfStorage-Start); } }
~Vector()
{
Destroy(Start, Finish);
Deallocate();
}
5.3. Push
void Push(const T& Value) { if (Finish != EndOfStorage) { Construct(Finish, Value); // 全局函数 ++Finish; } else { // 容器已满，需扩容 Insert_Aux(End(), Value); } } void Insert_Aux(Iterator position, const T& value) { if (Finish != EndOfStorage) { // 还有备用空间可用 Construct(Finish, *(Finish - 1)); ++Finish; T x_copy = value; //copy_backward(position, Finish - 2, Finish - 1); *position = x_copy; } else { // 已无备用空间 size_type nOldSize = Size(); size_type nNewSize = (nOldSize == 0) ? 1 : 2 * nOldSize; Iterator NewStart = data_allocator::Allocate(nNewSize); Iterator NewFinish = NewStart; try { NewFinish = uninitialzed_copy_ex(Start, position, NewStart); Construct(NewFinish, value); NewFinish++; } catch (...) { Destroy(NewStart, NewFinish); data_allocator::Deallocate(NewStart, nNewSize); throw; } Destroy(Begin(),End()); data_allocator::Deallocate(Start, EndOfStorage - Start); Start = NewStart; Finish = NewFinish; EndOfStorage = Start + nNewSize; } }
5.4. Pop_Back
void Pop_Back() { if (!Empty()) { --Finish; Destroy(Finish); } }
5.5. Erase
Erase方法只能清空元素，但不能释放空间
Iterator Erase(Iterator pos) { if (pos + 1 != Finish) { copy(pos + 1, Finish, pos); } --Finish; destroy(Finish); return pos; } Iterator Erase(Iterator first, Iterator last) { Iterator iter = uninitialzed_copy_ex(last, Finish, first); Destroy(iter, Finish); Finish = Finish - (last - first); return first; }
5.6. Resize
void Resize(size_type new_size, const T& x) { //如果新空间大小 小于size 就裁去多余的 如果新空间大于size那么就将这些插入. if (new_size < Size()) Erase(Begin() + new_size, End()); else { Iterator NewStart = data_allocator::Allocate(new_size); Iterator NewFinish = NewStart; try { NewFinish = uninitialzed_copy_ex(Start, Finish, NewStart); for (size_t i = 0; i < (new_size-Size()); i++) { *NewFinish++ = x; } } catch (...) { Destroy(NewStart, NewFinish); data_allocator::Deallocate(NewStart, new_size); throw; } Destroy(Begin(), End()); data_allocator::Deallocate(Start, EndOfStorage - Start); Start = NewStart; Finish = NewFinish; EndOfStorage = Start + new_size; } }
5.7. 全部实现
#pragma once #include "simple_alloc.h" #include <iostream> #include<memory> using namespace std; /* Construct和Destroy实现 */ namespace TRAITS_DEFINE { template<class T> struct iterator_traits { typedef T value_type; }; template<class T> struct iterator_traits<T *> { typedef T value_type; }; struct __true_type{}; struct __false_type{}; template<class type> struct __type_traits { typedef __true_type this_dummy_must_be_first; typedef __false_type has_trivial_default_constructor; typedef __false_type has_trivial_copy_constructor; typedef __false_type has_trivial_assignment_operator; typedef __false_type has_trivial_destructor; typedef __false_type is_POD_type; }; template<> struct __type_traits<int> { typedef __true_type this_dummy_must_be_first; typedef __true_type has_trivial_default_constructor; typedef __true_type has_trivial_copy_constructor; typedef __true_type has_trivial_assignment_operator; typedef __true_type has_trivial_destructor; typedef __true_type is_POD_type; }; } // 内存管理工具 template<class T1, class T2> void Construct(T1* p, const T2& value) { new (p) T1(value); // placement new;调用T1::T1(value) } template<class T> void Destroy(T* p) { p->~T(); p = NULL; } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last) { ForwardIterator iter = first; while (iter != last) { typedef typename TRAITS_DEFINE::iterator_traits<ForwardIterator>::value_type T; cout << typeid(T).name(); T p = (T)*iter; Destroy(&p); iter++; } } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last, TRAITS_DEFINE::__true_type) { ; } template<class ForwardIterator> void Destroy(ForwardIterator first, ForwardIterator last, TRAITS_DEFINE::__false_type) { for (; first<last; first++) { Destroy(&*first) } } template<class ForwardIterator, class T> void Destroy(ForwardIterator first, ForwardIterator last, T*) { typedef typename TRAITS_DEFINE::__type_traits<T>::has_trivial_destructor trivial_destructor; Destroy(first, last, trivial_destructor()); } /* * 实现vector * vector基本操作：构造、resize、erase、push、pop */ template <typename T> class Vector { public: typedef T& Reference; typedef T* Iterator; typedef T value_type; typedef size_t size_type; typedef CSimpleAlloc<value_type> data_allocator; // 自定义空间配置器 Iterator Start; Iterator Finish; Iterator EndOfStorage; public: Vector():Start(NULL), Finish(NULL),EndOfStorage(NULL){ cout << "Vector()" << endl; } Vector(const size_type& nSize, const T& nValue) { Fill_Initialize(nSize, nValue); } explicit Vector(const size_type& nSize) { Fill_Initialize(nSize, T()); } ~Vector() { Destroy(Start, Finish); Deallocate(); } Iterator Begin(){return Start;} Iterator End(){return Finish;} size_type Size() const { return size_type(Finish - Start); } size_type Capacity() const { return size_type(EndOfStorage - Start); } bool Empty() { return Begin() == End(); } Reference operator[](const size_type& nIndex) { return *(start + n); } Reference Front(){ return *Start; } Reference Back(){ return *(--Finish); } void Push(const T& Value) { if (Finish != EndOfStorage) { Construct(Finish, Value); // 全局函数 ++Finish; } else { // 容器已满，需扩容 Insert_Aux(End(), Value); } } void Pop_Back() { if (!Empty()) { --Finish; Destroy(Finish); } } void Print() { cout << "打印vector所有元素： "; Iterator iter = Start; while (iter != Finish) { cout << *iter << " "; iter++; } cout << endl; } Iterator Erase(Iterator pos) { if (pos + 1 != Finish) { copy(pos + 1, Finish, pos); } --Finish; destroy(Finish); return pos; } Iterator Erase(Iterator first, Iterator last) { Iterator iter = uninitialzed_copy_ex(last, Finish, first); Destroy(iter, Finish); Finish = Finish - (last - first); return first; } void Resize(size_type new_size, const T& x) { //如果新空间大小 小于size 就裁去多余的 如果新空间大于size那么就将这些插入. if (new_size < Size()) Erase(Begin() + new_size, End()); else { Iterator NewStart = data_allocator::Allocate(new_size); Iterator NewFinish = NewStart; try { NewFinish = uninitialzed_copy_ex(Start, Finish, NewStart); for (size_t i = 0; i < (new_size-Size()); i++) { *NewFinish++ = x; } } catch (...) { Destroy(NewStart, NewFinish); data_allocator::Deallocate(NewStart, new_size); throw; } Destroy(Begin(), End()); data_allocator::Deallocate(Start, EndOfStorage - Start); Start = NewStart; Finish = NewFinish; EndOfStorage = Start + new_size; } } void Clear() { Erase(Start, Finish); } private: void Deallocate() { if (Start) { data_allocator::Deallocate(Start, EndOfStorage-Start); } } void Insert_Aux(Iterator position, const T& value) { if (Finish != EndOfStorage) { // 还有备用空间可用 Construct(Finish, *(Finish - 1)); ++Finish; T x_copy = value; //copy_backward(position, Finish - 2, Finish - 1); *position = x_copy; } else { // 已无备用空间 size_type nOldSize = Size(); size_type nNewSize = (nOldSize == 0) ? 1 : 2 * nOldSize; Iterator NewStart = data_allocator::Allocate(nNewSize); Iterator NewFinish = NewStart; try { NewFinish = uninitialzed_copy_ex(Start, position, NewStart); Construct(NewFinish, value); NewFinish++; } catch (...) { Destroy(NewStart, NewFinish); data_allocator::Deallocate(NewStart, nNewSize); throw; } Destroy(Begin(),End()); data_allocator::Deallocate(Start, EndOfStorage - Start); Start = NewStart; Finish = NewFinish; EndOfStorage = Start + nNewSize; } } // 申请并填充内存 template<class OutputIterator> OutputIterator uninitialized_fill_n_ex(OutputIterator iter, const size_type& nSize, const T& nValue) { for (size_t i = 0; i < nSize; i++) { *iter++ = nValue; } return iter; } void Fill_Initialize(const size_type& nSize, const T& nValue) { Iterator iter = data_allocator::Allocate(nSize); uninitialized_fill_n_ex(iter, nSize, nValue); Start = iter; Finish = Start + nSize; EndOfStorage = Finish; } template<class InputIterator, class OutputIterator> OutputIterator uninitialzed_copy_ex(InputIterator first, InputIterator last, OutputIterator dest) { for (; first != last; first++,dest++) { *dest = *first; } return dest; } };
vector_define.h
// 完全解析STL空间配置器 /***** 一级配置区 ****************************/ // 1. 采用mallo/relloc/free申请和释放内存 // 2. 处理内存申请失败的处理 // (1)设置set_new_handle，若为NULL抛出__THROW_BAD_ALLOC; // (2)尝试重复申请 /**********************************************/ #pragma once class CFirstLevelAlloc; class CSecondLevelAlloc; #ifdef _CHUNK_ALLOC typedef CFirstLevelAlloc SelfAlloc; #else typedef CSecondLevelAlloc SelfAlloc; #endif typedef void(*CallBackFunc)(); class CFirstLevelAlloc { public: CFirstLevelAlloc(); static CallBackFunc m_CallBackFunc; static void* Allocate(size_t nSize); static void* Allocate(void *p, size_t nSize); static void Deallocate(void *p, size_t nSize = 0); static void SetCallBackHandle(CallBackFunc cb); private: static void* ReAllocate(size_t nSize); static void* ReAllocate(void *p, size_t nSize); }; enum {ALIGN = 8}; // 小型区块的上调边界 enum {MAX_BYTES = 128}; // 小型区块的上限 enum {FREELISTNUM = MAX_BYTES/ALIGN}; // free-lists个数 // 空闲内存链表结构 union FreeList { union FreeList *pFreeList; char client_data[1]; }; class CSecondLevelAlloc { public: CSecondLevelAlloc(); static void* Allocate(size_t nSize); static void Deallocate(void *p, size_t nSize); static void SetCallBackHandle(CallBackFunc cb); private: static size_t FreeListIndex(int nBytes); // 根据区块大小得到freelist索引 static size_t Round_Up(int nBytes); // 将bytes按内存对齐上调至ALIGN的倍数 static char *ChunkAlloc(size_t nSize, int& nObjs); static void* Refill(size_t nSize); private: static FreeList *m_pFreeList[FREELISTNUM]; static char *m_pStartFree; static char *m_pEndFree; static size_t m_nHeapSize; };
alloc_define.h
#pragma once #include "alloc_define.h" template<typename T, typename Alloc = SelfAlloc> class CSimpleAlloc { public: static T* Allocate(size_t n) { if (n == 0) { return NULL; } return (T *)Alloc::Allocate(n * sizeof(T)); } static T* Allocate(void) { return (T *)Alloc::Allocate(sizeof(T)); } static void Deallocate(T *p, size_t n) { if (n != 0) { Alloc::Deallocate(p, n * sizeof(T)); } } static void Deallocate(T *p) { Alloc::Deallocate(p, sizeof(T)); } static void SetCallBackHandle(CallBackFunc cb) { Alloc::SetCallBackHandle(cb); } };
simple_alloc.h
5.8. 测试
#include "stdio.h"#include "vector_define.h"#include<vector>using namespace std;void main(){ cout << "Vector(const size_type& nSize, const T& nValue)测试:" << endl; Vector<int> vect1(4, 5); vect1.Print(); cout << "Vector()--Push()--Pop测试：" << endl; Vector<int> vect2; vect2.Push(1); vect2.Push(2); vect2.Push(3); vect2.Push(4); vect2.Print(); vect2.Pop_Back(); vect2.Print(); cout << "Iterator Erase(Iterator first, Iterator last)测试：" << endl; Vector<int>::Iterator iter1 = vect2.Begin(); Vector<int>::Iterator iter2 = vect2.End(); vect2.Erase(iter1, iter2); cout << "vect Size:" << vect2.Size() << endl; cout << "void Resize(size_type new_size, const T& x)测试：" << endl; vect2.Resize(2, 88); vect2.Print(); vect2.Resize(8, 66); vect2.Print();}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/120126.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...