模拟实现STL库

　　最近在复习STL，感觉再看的时候比刚开始学的时候通透很多。以前模拟实现了一个STL库，最近复习完又重构了一遍。代码放出来以供后面学习。如果有写的不好的地方欢迎大家批评指正。

STL_List.h

  1 #pragma once
  2 #include"STL_Iterator.h"
  3 
  4 template<class T>
  5 struct _List_Node
  6 {
  7     _List_Node* _prev;
  8     _List_Node* _next;
  9     T _data;
 10     _List_Node()
 11     {
 12 
 13     }
 14     _List_Node(const T& x)
 15         :_data(x)
 16         , _prev(NULL)
 17         , _next(NULL)
 18     {
 19 
 20     }
 21 };
 22 
 23 template<class T, class Ref, class Ptr>
 24 struct _List_Iterator
 25 {
 26     typedef BidirectionalIterator_tag IteratorCategory;
 27     typedef _List_Iterator<T, T&, T*> Iterator;
 28     typedef T ValueType;
 29     typedef T& Reference;
 30     typedef T* Pointer;
 31     typedef _List_Node<T> *LinkType;
 32     typedef _List_Iterator<T, Ref, Ptr> Self;
 33     typedef int DifferenceType;
 34     LinkType _node;
 35 
 36     _List_Iterator()
 37     {
 38 
 39     }
 40     _List_Iterator(LinkType x)
 41         :_node(x)
 42     {
 43     }
 44     Reference operator*()
 45     {
 46         return _node->_data;
 47     }
 48     Pointer operator->()
 49     {
 50         return &(_node->_data);
 51     }
 52     Iterator operator++()
 53     {
 54         _node = _node->_next;
 55         return *this;
 56     }
 57     Iterator operator++(int)
 58     {
 59         Iterator tmp;
 60         tmp = *this;
 61         _node = _node->_next;
 62         return tmp;
 63     }
 64 
 65     Iterator operator--()
 66     {
 67         _node = _node->_prev;
 68         return *this;
 69     }
 70     Iterator operator--(int)
 71     {
 72         Iterator tmp = *this;
 73         _node = _node->_prev;
 74         return tmp;
 75     }
 76 
 77     bool operator!=(const Self& x)
 78     {
 79         return _node != x._node;
 80     }
 81 
 82     bool operator==(const Self& x)
 83     {
 84         return _node == x._node;
 85     }
 86 
 87 
 88 };
 89 
 90 template<class T, class Alloc = Alloc>
 91 class List
 92 {
 93 public:
 94     typedef _List_Node<T>* LinkType;
 95     typedef _List_Iterator<T, T&, T*> Iterator;
 96     typedef SimpleAlloc<_List_Node<T>, Alloc> ListNodeAllocator;
 97 
 98     List()
 99     {
100         _node = new _List_Node<T>();
101         _node->_next = _node;
102         _node->_prev = _node;
103     }
104     ~List()
105     {
106         Destory(Begin(), End());
107         Iterator it = Begin();
108         while (it != End())
109         {
110             ListNodeAllocator::Deallocate(it._node);
111         }
112     }
113 
114 
115     Iterator Begin()
116     {
117         return _node->_next;
118     }
119 
120     Iterator End()
121     {
122         return _node;
123     }
124 
125 
126 
127 
128     Iterator Insert(Iterator pos, const T& x)
129     {
130         LinkType prev = pos._node->_prev;
131         LinkType tmp = ListNodeAllocator::Allocate();
132         Construct(tmp, x);
133         //LinkType tmp = new _List_Node<T>(x);
134         prev->_next = tmp;
135         pos._node->_prev = tmp;
136         tmp->_next = pos._node;
137         tmp->_prev = prev;
138         return tmp;
139     }
140 
141 
142     void PushBack(const T& x)
143     {
144         Insert(End(), x);
145     }
146 
147 
148     void PushFront(const T& x)
149     {
150         Insert(Begin, x);
151     }
152 
153 
154     //reverse
155     //remove
156     //empty
157     //size
158     //unique
159     //merge
160 protected:
161     LinkType _node;
162 };
163 
164 
165 void TestList()
166 {
167     List<int> l;
168     l.PushBack(1);
169     l.PushBack(2);
170     l.PushBack(3);
171     l.PushBack(4);
172     l.PushBack(5);
173 
174     List<int>::Iterator it;
175     List<int>::Iterator begin = l.Begin();
176     List<int>::Iterator end = l.End();
177     for (it = l.Begin(); it != l.End(); it++)
178     {
179         cout << *it << " ";
180     }
181     cout << "Distance" << Distance(begin, end) << endl;
182 }
View Code

STL_Vector.h

  1 #pragma once
  2 #include<cassert>
  3 #include"STL_Iterator.h"
  4 #include"STL_Alloc.h"
  5 #include"STL_Construct.h"
  6 #include"STL_Uninittialized.h"
  7 
  8 template<class T, class Alloc = Alloc>
  9 class Vector
 10 {
 11     typedef T ValueType;
 12     typedef T& Reference;
 13     typedef T* Pointer;
 14     typedef int DifferenceType;
 15 public:
 16     typedef ValueType * Iterator;
 17     typedef RandomAccessIterator_tag IteratorCategory;
 18     typedef SimpleAlloc<T, Alloc> DataAlloc;
 19 
 20 
 21 
 22     Iterator Begin() { return Start; }
 23     Iterator End() { return Finish; }
 24 
 25     Vector()
 26         :Start(NULL)
 27         , Finish(NULL)
 28         , EndOfStorage(NULL)
 29     {
 30 
 31     }
 32     Vector(size_t n, const T& value)
 33     {
 34         Start = new T[n];
 35         Finish = Start + n;
 36         EndOfStorage = Finish;
 37     }
 38     ~Vector()
 39     {
 40         Destory(Start, Finish);
 41         DataAlloc::Deallocate(Start, Size());
 42     }
 43 
 44 
 45 
 46 
 47     /*void Insert(Iterator Position,size_t n,const ValueType& x)
 48     {
 49     if (n != 0)
 50     {
 51     if (size_t(EndOfStorage - Finish) > n)
 52     {
 53     size_t Elems_After = Finish - Position;
 54     Iterator OldFinish = Finish;
 55     if (Elems_After > n)
 56     {
 57     Finish += n;
 58     Copy_Backward(Position, OldFinish - n, OldFinish);
 59     while (n-- > 0)
 60     {
 61     *(Position++) = x;
 62     }
 63     }
 64     else
 65     {
 66     int tmp = n - Elems_After;
 67     while (tmp-- > 0)
 68     {
 69     *(Finish++) = x;
 70     }
 71     tmp = OldFinish - Position;
 72     for (int i = 0; i < tmp; ++i)
 73     {
 74     *(Finish++) = *(Position + i);
 75     }
 76     while (n-- > 0)
 77     {
 78     *(Position++) = x;
 79     }
 80     }
 81     }
 82     else
 83     {
 84     ExpandCapacity();
 85     Insert(Position, n, x);
 86     }
 87     }
 88     }*/
 89     void Push_Back(const T& x)
 90     {
 91         ExpandCapacity();
 92         Construct(Finish, x);
 93         Finish++;
 94 
 95     }
 96     void Pop_Back()
 97     {
 98         assert(Size());
 99         Destory(Finish);//ÓбØҪô£¿£¿
100         --Finish;
101     }
102     size_t Size()
103     {
104         return (Finish - Start);
105     }
106 
107     bool Empty()
108     {
109         return Beign == End;
110     }
111 
112     Iterator Erase(Iterator pos)
113     {
114         Iterator begin = pos;
115         wihle(begin + 1 != Finish)
116         {
117             *begin = *(beign + 1);
118         }
119         --Finish;
120         return pos;
121     }
122 
123 
124 
125 protected:
126 
127     void Copy_Backward(Iterator Position, Iterator first, Iterator last)
128     {
129         while (first != Position - 1)
130         {
131             *(last--) = *(first--);
132         }
133 
134     }
135     void ExpandCapacity()
136     {
137         if (Finish == EndOfStorage)
138         {
139             size_t size = Size();
140             size_t curLength = EndOfStorage - Start;
141             size_t newLength = 2 * curLength + 3;
142             T *tmp = DataAlloc::Allocate(newLength);
143             if (Start)
144             {
145                 UninitializedCopy(Start, Start + size, tmp);
146             }
147             Destory(Start, Finish);
148             DataAlloc::Deallocate(Start, EndOfStorage - Start);
149 
150             Start = tmp;
151             Finish = Start + Size();
152             EndOfStorage = Start + newLength;
153 
154             /*    Iterator newStart = new T[newLength];
155             Iterator it = Begin();
156             for (int i = 0; i < Size(); ++i)
157             {
158             newStart[i] = Start[i];
159             }
160             Destory();
161             Start = newStart;
162             Finish = Start + curLength;
163             EndOfStorage = Start + newLength;*/
164         }
165     }
166     //void Destory()
167     //{
168     //    delete[] Start;
169     //    Start = NULL;
170     //    Finish = NULL;
171     //    EndOfStorage = NULL;
172     //}
173 protected:
174     Iterator Start;
175     Iterator Finish;
176     Iterator EndOfStorage;
177 };
178 
179 
180 void TestVector()
181 {
182     Vector<int> v;
183     v.Push_Back(1);
184     v.Push_Back(2);
185     v.Push_Back(3);
186     v.Push_Back(4);
187     v.Push_Back(5);
188     Vector<int>::Iterator cur;
189     for (cur = v.Begin(); cur != v.End(); cur++)
190     {
191         cout << *cur << " ";
192     }
193 }
View Code
vector的数据安排和数组非常相似。两者的差别在于数组是静态空间，一旦配置了就不能改变，而vector是动态空间，随着元素的加入，他的内部会自行扩充空间（自行扩充不是在原有空间上 续接新空间，因为无法保证原空间之后还有可供配置的空间，所以他会重新开辟一块原大小二倍的空间，然后将原来的数据拷贝过来，然后在原内容之后构造新元素，并释放原有空间）。一旦vector旧有空间满载，内部只是扩充一个元素的空间实为不智，因为配置新空间，数据移动，释放原空间成本很高，应该加入某种未雨绸缪的考虑，在STL中就是空间扩大原来的二倍。
 
数组和链表的区别：
  • 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。
  • 链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。
   *C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。
　　(1) 从逻辑结构角度来看
　　   a, 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
　　   b,链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
　　(2)从内存存储角度来看
　　   a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
　　   b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

STL_Uninitialized.h

 1 #pragma once
 2 #include"STL_Iterator.h"
 3 #include"TypeTraits.h"
 4 #include"STL_Construct.h"
 5 #include"STL_Iterator.h"
 6 #include<memory.h>
 7 
 8 template <class InputIterator, class ForwardIterator>
 9 inline ForwardIterator
10 __UninitializedCopyAux(InputIterator first, InputIterator last,
11 ForwardIterator result,
12 __TrueType) {
13     return copy(first, last, result);
14 }
15 
16 
17 template <class InputIterator, class ForwardIterator>
18 ForwardIterator
19 __UninitializedCopyAux(InputIterator first, InputIterator last,
20 ForwardIterator result,
21 __FalseType) {
22     ForwardIterator cur = result;
23 
24     for (; first != last; ++first, ++cur)
25         Construct(&*cur, *first);
26     return cur;
27 }
28 
29 template <class InputIterator, class ForwardIterator, class T>
30 inline ForwardIterator __UninitializedCopy(InputIterator first, InputIterator last,
31     ForwardIterator result, T*)
32 {
33     typedef typename __TypeTraits<T>::IsPODType IsPOD;
34     return __UninitializedCopyAux(first, last, result, IsPOD());
35 }
36 
37 
38 template <class InputIterator, class ForwardIterator>
39 inline ForwardIterator UninitializedCopy(InputIterator first, InputIterator last,
40     ForwardIterator result) {
41     return __UninitializedCopy(first, last, result, ValueType(result));
42 }
43 
44 inline char* UninitializedCopy(const char* first, const char* last,
45     char* result) {
46     memmove(result, first, last - first);
47     return result + (last - first);
48 }
49 
50 inline wchar_t* UninitializedCopy(const wchar_t* first, const wchar_t* last,
51     wchar_t* result) {
52     memmove(result, first, sizeof(wchar_t)* (last - first));
53     return result + (last - first);
54 }
View Code

STL_Construct.h

 1 #pragma once
 2 
 3 #include"TypeTraits.h"
 4 
 5 
 6 template<class T>
 7 inline void Destory(T *pointer)
 8 {
 9     pointer->~T();
10 }
11 
12 template<class T1, class T2>
13 inline void Construct(T1 *p, const T2& value)
14 {
15     new(p)T1(value);
16 }
17 
18 
19 template<class ForwardIterator>
20 inline void __DestoryAux(ForwardIterator first, ForwardIterator last, __FalseType)
21 {
22     for (; first < last; ++first)
23     {
24         Destory(&*first);
25     }
26 }
27 
28 template<class ForwardIterator>
29 inline void __DestoryAux(ForwardIterator first, ForwardIterator last, __TrueType)
30 {}
31 
32 
33 template<class ForwardIterator, class T>
34 inline void __Destory(ForwardIterator first, ForwardIterator last, T *)
35 {
36     typedef typename __TypeTraits<T>::HasTrivialDestructor TrivialDestructor;
37     __DestoryAux(first, last, TrivialDestructor());
38 }
39 
40 template<class ForwardIterator>
41 inline void Destory(ForwardIterator first, ForwardIterator last)
42 {
43     __Destory(first, last, ValueType(first));
44 }
45 
46 
47 inline void Destory(char*, char*) {}
48 inline void Destory(wchar_t*, wchar_t*) {}
View Code

STL_Alloc.h

  1 #pragma once
  2 
  3 template<class T, class Alloc>
  4 class SimpleAlloc
  5 {
  6 public:
  7     static T *Allocate(size_t n)
  8     {
  9         return 0 == n ? 0 : (T*)Alloc::Allocate(n * sizeof(T));
 10     }
 11     static T *Allocate(void)
 12     {
 13         return (T*)Alloc::Allocate(sizeof(T));
 14     }
 15     static void Deallocate(T *p, size_t n)
 16     {
 17         if (0 != n) Alloc::Deallocate(p, n * sizeof(T));
 18     }
 19     static void Deallocate(T *p)
 20     {
 21         Alloc::Deallocate(p, sizeof(T));
 22     }
 23 };
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 template<int inst>
 35 class __MallocAllocTemplate//一级配置器
 36 {
 37 private:
 38     static void *OomMalloc(size_t n)
 39     {
 40         void(*MyMallocHandler)();//期待可以通过用户设置的handler解决内存不足问题（释放一部分内存）
 41         void *result;
 42 
 43         while (1)
 44         {
 45             MyMallocHandler = __MallocAllocOomHandler;
 46             if (0 == MyMallocHandler)
 47             {
 48                 cout << "别开辟了，实在没有了（此处应该抛出异常）" << endl;
 49                 exit(-1);
 50             }
 51             (*MyMallocHandler)();
 52             result = malloc(n);
 53             if (result) return(result);
 54         }
 55     }
 56     static void    *OomRealloc(void *ptr, size_t n)
 57     {
 58         void(*MyMallocHandler)();//期待可以通过用户设置的handler解决内存不足问题（释放一部分内存）
 59         void *result;
 60 
 61         while (1)
 62         {
 63             MyMallocHandler = __MallocAllocOomHandler;
 64             if (0 == MyMallocHandler)
 65             {
 66                 cout << "别开辟了，实在没有了（此处应该抛出异常）" << endl;
 67                 exit(-1);
 68             }
 69             (*MyMallocHandler)();
 70             result = realloc(p, n);
 71             if (result) return(result);
 72         }
 73     }
 74     static void(*__MallocAllocOomHandler)();//定义函数指针，其实没啥用
 75 public:
 76     static void *Allocate(size_t n)
 77     {
 78         void *result = malloc(n);
 79         if (0 == result)
 80         {
 81             result = OomMalloc(n);
 82         }
 83         return result;
 84     }
 85     static void Deallocate(void *p, size_t n)//后面的n似乎用处不大
 86     {
 87         free(p);
 88     }
 89     static void *Reallocate(void *p, size_t oldsize, size_t newsize)
 90     {
 91         void *result = realloc(p, newsize);
 92         if (0 == result)
 93         {
 94             result = OomRealloc(p, newsize);
 95         }
 96         return result;
 97     }
 98     static void(*SetMallocHandler(void(*f)()))()
 99     {
100         void(*old)() = __MallocAllocOomHandler;
101         __MallocAllocOomHandler = f;
102         return(old);//设置新的处理函数指针，返回旧的函数指针
103     }
104 
105 };
106 template <int inst>
107 void(*__MallocAllocTemplate<inst>::__MallocAllocOomHandler)() = 0;//所以说那个函数指针一般没啥用都设为NULL了
108 
109 
110 typedef __MallocAllocTemplate<0> MallocAlloc;
111 
112 # ifdef __USE_MALLOC
113 
114 typedef malloc_alloc Alloc;
115 # else
116 
117 
118 template<bool threads, int inst>
119 class __DefaultAllocTemplate//二级空间配置器含有内存池
120 {
121     enum { __ALIGN = 8 };
122     enum { __MAX_BYTES = 128 };
123     enum { __NFREELISTS = __MAX_BYTES / __ALIGN };
124 private:
125 
126     static size_t ROUND_UP(size_t bytes) {
127         return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
128     }
129     union Obj {
130         union Obj * FreeListLink;
131         char ClientData[1];    /* The client sees this.        */
132     };
133 
134 
135 
136     static Obj * volatile FreeList[__NFREELISTS];//声明自由链表
137     static char *StartFree;
138     static char *EndFree;
139     static size_t HeapSize;
140 
141 
142 
143     static  size_t FREELIST_INDEX(size_t bytes) {
144         return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
145     }
146 
147 
148 
149     static void *Refill(size_t n)
150     {
151         int nobjs = 20;
152         char *chunk = ChunkAlloc(n, nobjs);
153         Obj* volatile MyFreeList;
154         Obj* result;
155         int i;
156         if (1 == nobjs)
157         {
158             return chunk;
159         }
160         int index = FREELIST_INDEX(n);
161         MyFreeList = FreeList[index];
162         result = (Obj *)chunk;
163         MyFreeList = (Obj *)(chunk + n);//取出剩下的节点挨个儿查到对应的自由链表位置上去
164         Obj* end = (Obj *)MyFreeList;
165         for (i = 1;; i++)
166         {
167             if (nobjs - 1 == i)
168             {
169                 end->FreeListLink = 0;
170                 break;
171             }
172             else
173             {
174                 end->FreeListLink = (Obj *)(chunk + (i + 1)*n);
175             }
176         }
177         return result;
178     }
179     static char *ChunkAlloc(size_t size, int &nobjs)
180     {
181         char *result;
182         size_t totalbytes = size*nobjs;
183         size_t bytesleft = EndFree - StartFree;
184         if (bytesleft >= totalbytes)//内存池的内存完全够用
185         {
186             result = StartFree;
187             StartFree += totalbytes;
188             return result;
189         }
190         else if (bytesleft >= size)//内存池的内存虽然不够20个，但是至少够1个
191         {
192             nobjs = bytesleft / size;
193             totalbytes = nobjs*size;
194             result = StartFree;
195             StartFree += totalbytes;
196             return result;
197         }
198         else
199         {
200             size_t bytestoget = 2 * totalbytes + ROUND_UP(HeapSize >> 4);
201             if (bytesleft > 0)//还有一部分内存没有分配，需要先分配出去
202             {
203                 int index = FREELIST_INDEX(bytesleft);
204                 Obj * volatile MyFreeList = FreeList[index];
205                 Obj *tmp = (Obj *)StartFree;
206                 tmp->FreeListLink = MyFreeList;//头插
207                 MyFreeList = tmp;
208             }
209             StartFree = (char *)malloc(bytestoget);
210             if (0 == StartFree)
211             {
212                 int i;
213                 Obj *volatile MyFreeList, *p;
214                 for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
215                     int index = FREELIST_INDEX(i);
216                     MyFreeList = FreeList[index];
217                     p = MyFreeList;
218                     if (0 != p)
219                     {
220                         MyFreeList = p->FreeListLink;
221                         StartFree = (char *)p;
222                         EndFree = StartFree + i;
223                         return(ChunkAlloc(size, nobjs));
224                     }
225                 }
226                 EndFree = 0;
227                 StartFree = (char *)MallocAlloc::Allocate(bytestoget);
228 
229             }
230             HeapSize += bytestoget;
231             EndFree = StartFree + bytestoget;
232             return (ChunkAlloc(size, nobjs));
233         }
234     }
235 
236 
237 
238 
239 
240 
241 public:
242     static void *Allocate(size_t n)
243     {
244         Obj* volatile MyFreeList;
245         Obj* result;
246         if (n > (size_t)__MAX_BYTES)//大于128字节到一级配置器中去
247         {
248             return MallocAlloc::Allocate(n);
249         }
250         int index = FREELIST_INDEX(n);
251         MyFreeList = FreeList[index];
252         result = MyFreeList;
253         if (result == 0)
254         {
255             void *r = Refill(ROUND_UP(n));
256             return r;
257         }
258         MyFreeList = result->FreeListLink;
259         return result;
260     }
261 
262 
263     static void Deallocate(void *p, size_t n)
264     {
265         int index = FREELIST_INDEX(n);
266         Obj* q = (Obj *)p;
267         Obj* volatile MyFreeList;
268         if (n > (size_t)__MAX_BYTES)
269         {
270             MallocAlloc::Deallocate(p, n);
271             return;
272         }
273         MyFreeList = FreeList[index];//把内存块还给自由链表，采用头插的方式插入自由链表
274         q->FreeListLink = MyFreeList;
275         MyFreeList = q;
276 
277     }
278 
279 
280 
281 
282 };
283 template <bool threads, int inst>
284 typename __DefaultAllocTemplate<threads, inst>::Obj* volatile __DefaultAllocTemplate<threads, inst>::FreeList[__DefaultAllocTemplate<threads, inst>::__NFREELISTS];
285 
286 template <bool threads, int inst>
287 char* __DefaultAllocTemplate<threads, inst>::StartFree = 0;
288 template <bool threads, int inst>
289 char* __DefaultAllocTemplate<threads, inst>::EndFree = 0;
290 template <bool threads, int inst>
291 size_t __DefaultAllocTemplate<threads, inst>::HeapSize = 0;;
292 
293 
294 typedef __DefaultAllocTemplate<0, 0> Alloc;
295 
296 
297 #endif
298 
299 
300 
301 
302 
303 void Test1()
304 {
305     // 测试调用一级配置器分配内存
306     cout << "测试调用一级配置器分配内存" << endl;
307     char*p1 = SimpleAlloc<char, Alloc>::Allocate(129);
308     SimpleAlloc<char, Alloc>::Deallocate(p1, 129);
309 
310     // 测试调用二级配置器分配内存
311     cout << "测试调用二级配置器分配内存" << endl;
312     char*p2 = SimpleAlloc<char, Alloc>::Allocate(128);
313     char*p3 = SimpleAlloc<char, Alloc>::Allocate(128);
314     char*p4 = SimpleAlloc<char, Alloc>::Allocate(128);
315     char*p5 = SimpleAlloc<char, Alloc>::Allocate(128);
316     SimpleAlloc<char, Alloc>::Deallocate(p2, 128);
317     SimpleAlloc<char, Alloc>::Deallocate(p3, 128);
318     SimpleAlloc<char, Alloc>::Deallocate(p4, 128);
319     SimpleAlloc<char, Alloc>::Deallocate(p5, 128);
320 
321     for (int i = 0; i < 21; ++i)
322     {
323         printf("测试第%d次分配
", i + 1);
324         char*p = SimpleAlloc<char, Alloc>::Allocate(128);
325     }
326 }
View Code
空间配置器是为了解决内存碎片的问题。由于在堆中频繁申请释放内存，造成外碎片的问题，（极端情况下，就是堆中空闲的内存总量满足一个需求，但是这些内存都不连续，导致任何的一个单独块的内存都无法满足这个请求。
STL中使用两级空间配置器。当申请的内存大于128字节时，认为申请的是大内存，调用一级空间配置器来分配内存，当申请的内存小于等于128字节则认为申请的是小内存，调用二级空间配置器去内存池中申请。一级空间配置器很简单，直接封装了malloc和free来实现 。二级空间配置器是使用内存池+自由链表来实现的。
为了便于管理，二级空间配置器都是以8的倍数对齐，方便内存管理。这样的话需要维护16个自由链表，这16个自由链表管理的内存大小分别为8,16,24,32，。。128字节的空间。
二级空间配置器的逻辑步骤：
如果现在要申请那个字节的空间是否大于128,如果大于128则直接调用一级空间配置器，如果不大于将n上调至8的倍数，然后在去自由链表中响应的节点下面找，如果该节点下面挂有还未使用的内存，则摘下来直接返回这块空间的地址。否则的话我们就要调用refill函数去内存池中申请

STL_Iterator.h

  1 #pragma once
  2 
  3 
  4 struct InputIterator_tag {};
  5 struct OutputIterator_tag {};
  6 struct ForwardIterator_tag : public InputIterator_tag {};
  7 struct BidirectionalIterator_tag : public ForwardIterator_tag {};
  8 struct RandomAccessIterator_tag : public BidirectionalIterator_tag {};
  9 
 10 template <class T, class Distance> struct InputIterator {
 11     typedef InputIterator_tag IteratorCategory;
 12     typedef T                  ValueType;
 13     typedef Distance           DifferenceType;
 14     typedef T*                 Pointer;
 15     typedef T&                 Reference;
 16 };
 17 
 18 struct OutputIterator {
 19     typedef OutputIterator_tag IteratorCategory;
 20     typedef void                ValueType;
 21     typedef void                DifferenceType;
 22     typedef void                Pointer;
 23     typedef void                Reference;
 24 };
 25 
 26 template <class T, class Distance> struct ForwardIterator {
 27     typedef ForwardIterator_tag IteratorCategory;
 28     typedef T                    ValueType;
 29     typedef Distance             DifferenceType;
 30     typedef T*                   Pointer;
 31     typedef T&                   Reference;
 32 };
 33 
 34 
 35 template <class T, class Distance> struct BidirectionalIterator {
 36     typedef BidirectionalIterator_tag IteratorCategory;
 37     typedef T                          ValueType;
 38     typedef Distance                   DifferenceType;
 39     typedef T*                         Pointer;
 40     typedef T&                         Reference;
 41 };
 42 
 43 template <class T, class Distance> struct RandomAccessIterator {
 44     typedef RandomAccessIterator_tag IteratorCategory;
 45     typedef T                          ValueType;
 46     typedef Distance                   DifferenceType;
 47     typedef T*                         Pointer;
 48     typedef T&                         Reference;
 49 };
 50 
 51 
 52 
 53 template <class Category, class T, class Distance = size_t, class Pointer = T*, class Reference = T&>
 54 struct Iterator {
 55     typedef Category  IteratorCategory;
 56     typedef T         ValueType;
 57     typedef Distance  DifferenceType;
 58     typedef Pointer   Pointer;
 59     typedef Reference Reference;
 60 };
 61 
 62 
 63 template <class Iterator>
 64 struct IteratorTraits
 65 {
 66     typedef typename Iterator::IteratorCategory IteratorCategory;
 67     typedef typename Iterator::ValueType        ValueType;
 68     typedef typename Iterator::DifferenceType   DifferenceType;
 69     typedef typename Iterator::Pointer           Pointer;
 70     typedef typename Iterator::Reference         Reference;
 71 };//ÀàÐÍÝÍÈ¡»ú
 72 
 73 
 74 
 75 
 76 
 77 template <class T>
 78 struct IteratorTraits<T*>
 79 {
 80     typedef RandomAccessIterator_tag IteratorCategory;
 81     typedef T                          ValueType;
 82     typedef ptrdiff_t                  DifferenceType;
 83     typedef T*                         Pointer;
 84     typedef T&                         Reference;
 85 };
 86 
 87 
 88 
 89 
 90 
 91 
 92 
 93 
 94 
 95 
 96 template<class InputIterator>
 97 int Distance(InputIterator first, InputIterator last)
 98 {
 99     return _Distance(first, last, IteratorTraits<InputIterator>::IteratorCategory());
100 }
101 
102 
103 template<class InputIterator>
104 int _Distance(InputIterator first, InputIterator last, ForwardIterator_tag)
105 {
106     int count = 0;
107     while (first != last)
108     {
109         count++;
110         first++;
111     }
112     return count;
113 }
114 
115 
116 template<class InputIterator>
117 int _Distance(InputIterator first, InputIterator last, RandomAccessIterator_tag)
118 {
119     return last - first;
120 }
121 
122 
123 
124 //template <class Iterator>
125 //inline typename IteratorTraits<Iterator>::DifferenceType*
126 //DifferenceType(const Iterator&) {
127 //    return static_cast<typename IteratorTraits<Iterator>::DifferenceType*>(0);
128 //}
129 
130 template <class T, class Distance>
131 inline T* ValueType(const InputIterator<T, Distance>&) {
132     return (T*)(0);
133 }
134 
135 template <class T, class Distance>
136 inline T* ValueType(const ForwardIterator<T, Distance>&) {
137     return (T*)(0);
138 }
139 
140 template <class T, class Distance>
141 inline T* ValueType(const BidirectionalIterator<T, Distance>&) {
142     return (T*)(0);
143 }
144 
145 template <class T, class Distance>
146 inline T* ValueType(const RandomAccessIterator<T, Distance>&) {
147     return (T*)(0);
148 }
149 
150 template <class T>
151 inline T* ValueType(const  T*) { return (T*)(0); }
View Code
　　迭代器是一种抽象的设计概念。他提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的的内部表述方式。迭代器的行为类似指针需要对operator*和operator->进行重载
　　智能指针也算是迭代器的一种，原生指针也可以说是迭代器。但是他们不能直接用作迭代器，因为无法获得智能指针所指向的类型，我们使用迭代器的时候很可能会用到迭代器的相应型别

STL_TypeTraits.h

  1 #pragma once
  2 
  3 
  4 struct InputIterator_tag {};
  5 struct OutputIterator_tag {};
  6 struct ForwardIterator_tag : public InputIterator_tag {};
  7 struct BidirectionalIterator_tag : public ForwardIterator_tag {};
  8 struct RandomAccessIterator_tag : public BidirectionalIterator_tag {};
  9 
 10 template <class T, class Distance> struct InputIterator {
 11     typedef InputIterator_tag IteratorCategory;
 12     typedef T                  ValueType;
 13     typedef Distance           DifferenceType;
 14     typedef T*                 Pointer;
 15     typedef T&                 Reference;
 16 };
 17 
 18 struct OutputIterator {
 19     typedef OutputIterator_tag IteratorCategory;
 20     typedef void                ValueType;
 21     typedef void                DifferenceType;
 22     typedef void                Pointer;
 23     typedef void                Reference;
 24 };
 25 
 26 template <class T, class Distance> struct ForwardIterator {
 27     typedef ForwardIterator_tag IteratorCategory;
 28     typedef T                    ValueType;
 29     typedef Distance             DifferenceType;
 30     typedef T*                   Pointer;
 31     typedef T&                   Reference;
 32 };
 33 
 34 
 35 template <class T, class Distance> struct BidirectionalIterator {
 36     typedef BidirectionalIterator_tag IteratorCategory;
 37     typedef T                          ValueType;
 38     typedef Distance                   DifferenceType;
 39     typedef T*                         Pointer;
 40     typedef T&                         Reference;
 41 };
 42 
 43 template <class T, class Distance> struct RandomAccessIterator {
 44     typedef RandomAccessIterator_tag IteratorCategory;
 45     typedef T                          ValueType;
 46     typedef Distance                   DifferenceType;
 47     typedef T*                         Pointer;
 48     typedef T&                         Reference;
 49 };
 50 
 51 
 52 
 53 template <class Category, class T, class Distance = size_t, class Pointer = T*, class Reference = T&>
 54 struct Iterator {
 55     typedef Category  IteratorCategory;
 56     typedef T         ValueType;
 57     typedef Distance  DifferenceType;
 58     typedef Pointer   Pointer;
 59     typedef Reference Reference;
 60 };
 61 
 62 
 63 template <class Iterator>
 64 struct IteratorTraits
 65 {
 66     typedef typename Iterator::IteratorCategory IteratorCategory;
 67     typedef typename Iterator::ValueType        ValueType;
 68     typedef typename Iterator::DifferenceType   DifferenceType;
 69     typedef typename Iterator::Pointer           Pointer;
 70     typedef typename Iterator::Reference         Reference;
 71 };//ÀàÐÍÝÍÈ¡»ú
 72 
 73 
 74 
 75 
 76 
 77 template <class T>
 78 struct IteratorTraits<T*>
 79 {
 80     typedef RandomAccessIterator_tag IteratorCategory;
 81     typedef T                          ValueType;
 82     typedef ptrdiff_t                  DifferenceType;
 83     typedef T*                         Pointer;
 84     typedef T&                         Reference;
 85 };
 86 
 87 
 88 
 89 
 90 
 91 
 92 
 93 
 94 
 95 
 96 template<class InputIterator>
 97 int Distance(InputIterator first, InputIterator last)
 98 {
 99     return _Distance(first, last, IteratorTraits<InputIterator>::IteratorCategory());
100 }
101 
102 
103 template<class InputIterator>
104 int _Distance(InputIterator first, InputIterator last, ForwardIterator_tag)
105 {
106     int count = 0;
107     while (first != last)
108     {
109         count++;
110         first++;
111     }
112     return count;
113 }
114 
115 
116 template<class InputIterator>
117 int _Distance(InputIterator first, InputIterator last, RandomAccessIterator_tag)
118 {
119     return last - first;
120 }
121 
122 
123 
124 //template <class Iterator>
125 //inline typename IteratorTraits<Iterator>::DifferenceType*
126 //DifferenceType(const Iterator&) {
127 //    return static_cast<typename IteratorTraits<Iterator>::DifferenceType*>(0);
128 //}
129 
130 template <class T, class Distance>
131 inline T* ValueType(const InputIterator<T, Distance>&) {
132     return (T*)(0);
133 }
134 
135 template <class T, class Distance>
136 inline T* ValueType(const ForwardIterator<T, Distance>&) {
137     return (T*)(0);
138 }
139 
140 template <class T, class Distance>
141 inline T* ValueType(const BidirectionalIterator<T, Distance>&) {
142     return (T*)(0);
143 }
144 
145 template <class T, class Distance>
146 inline T* ValueType(const RandomAccessIterator<T, Distance>&) {
147     return (T*)(0);
148 }
149 
150 template <class T>
151 inline T* ValueType(const  T*) { return (T*)(0); }
View Code

　　　　类型萃取分为POD类型(基本数据类型）和非POD类型，POD类型有库提供的构造函数，析构函数，拷贝构造等，而非POD类型没有，需要用户自定义这些功能。使用类型萃取是把这两种类型分开，然后对POD类型不用处理对非POD类型自定义实现功能，从而达到代码重用。

　　　　

参考：http://www.cnblogs.com/lenomirei/p/5379289.html  STL的迭代器和类型萃取

　　   http://blog.csdn.net/lf_2016/article/details/53511648  揭秘——STL空间配置器

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qingjiaowoxiaoxioashou/p/6824213.html