首页 > 代码库 > 模拟实现STL库

模拟实现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);//óD±?òa?′£?£?
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次分配\n", 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 };//ààDíYíè??ú
 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 };//ààDíYíè??ú
 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空间配置器

模拟实现STL库