看侯捷老师的《STL源码剖析》有一段时间了，打算自己整理一下思路，试着实现一下。主要目的有两个：1、巩固自己对源码的理解，让自己更加深刻的体会其中各种机制的奥妙。别人的知识永远是别人的，只有自己亲自动手实践过，才能转化为自己的。2、通过实现这些优秀的算法，来提高自己的“内功”修养。

        vector其实就是动态数组。它的性质与数组基本一致。同样使用的是一片连续的内存空间。它与数组相比，其优点是灵活性较强，其空间大小可变。但是其效率没有数组高。这是因为受到了其空间配置器的影响。SGI-STL中，为了减少内存碎片，在空间配置方面有很多机制。创建一个vector时，需要分配填充内存池、填充free-list、分配内存等一系列操作。这使得它的效率稍微低了些。此外，当空间不足，需要扩充空间时，SGI-STL采用“三步走”的措施，即：分配新的空间——将原来数据拷贝过去——释放原来的空间。我们在使用时，应该尽量避免扩充vector的空间。还有一点应当注意，当写出如下代码的时候，虽然分配了10个元素的空间，当你紧接着再往容器中添加数据时，同样会扩充空间。也就是程序执行完成第2行代码时，其正在的元素个数已经变成了11，而不是原来的10。其具体原因请看源代码

vector<int> Vec(10);

Vec.push_back(10);

 

　　以下是我自己根据源代码，仿造的vector。

1 #ifndef CVECTOR_H_  2 #define CVECTOR_H_  3   4 #include "DefaultAllocTemplate.h"  5 #include "AllocatorInterface.h"  6 #include "comm.h"  7 #include 
     
        8 #include 
      
         9 #include 
       
         10 #include 
        
          11  12 template 
         
           13 class CVector { 14 /*以下是Vector的迭代器类型*/ 15 public: 16     typedef T ValueType; 17     typedef ValueType* Pointer; 18     typedef ValueType* Iterator; 19     typedef ValueType& Reference; 20     typedef size_t SizeType; 21     typedef ptrdiff_t DifferenceType; 22 protected: 23  24     /*空间配置器*/ 25     typedef AllocatorInterface
          
           DataAllocator; 26 27 /*目前正在使用的空间的头部*/ 28 Iterator m_Start; 29 30 /*目前正在使用空间的尾部*/ 31 Iterator m_Finish; 32 33 /*可用空间的尾部，它与m_Start决定了容器的最大容量*/ 34 Iterator m_EndOfStorage; 35 36 /*向Vetory中插入一个成员*/ 37 void InsertAux(Iterator Pos, const T& x); 38 39 /*销毁容器*/ 40 void Deallocate() 41 { 42 if(0 != m_Start) 43 { 44 /*调用空间配置器接口中的函数销毁销毁容器*/ 45 DataAllocator::Deallocate(m_Start, m_EndOfStorage - m_Start); 46 } 47 } 48 49 /*创建容器，并为其分配存储空间。该函数可以获取uiNum个对象的内存空间， 50 *并将内存指针保存在m_Start中。以后的构造函数中，都会调用这个函数*/ 51 void FillInitialize(SizeType uiNum, const T& Value) 52 { 53 m_Start = AllocateAndFill(uiNum, Value); 54 /*注意，这里会使得原来的你在创建vector的时候，无论你申请了多少个元素的空间，当你（即使是申请后马上） 55 *调用PushBack函数时，也会扩大原来的内存空间*/ 56 m_Finish = m_Start + uiNum; 57 m_EndOfStorage = m_Finish; 58 } 59 60 /*配置空间并填充内容*/ 61 Iterator AllocateAndFill(SizeType uiNum, const T& Value) 62 { 63 Iterator Result=DataAllocator::Allocate(uiNum); 64 //调用全局函数为对象配置内存 65 uninitialized_fill_n(Result, uiNum, Value); 66 return Result; 67 } 68 69 public: 70 /*获取容器起始位置*/ 71 Iterator Begin() 72 { 73 return m_Start; 74 } 75 76 /*获取容器中正在使用空间的尾部*/ 77 Iterator End() 78 { 79 return m_Finish; 80 } 81 82 /*返回容器中元素个数*/ 83 SizeType Size() 84 { 85 return (SizeType)(m_Finish - m_Start); 86 } 87 88 SizeType Capacity() 89 { 90 return (SizeType)(m_EndOfStorage - m_Start); 91 } 92 93 /*判断容器是否为空*/ 94 int Empty() 95 { 96 return m_Start == m_Finish; 97 } 98 99 /*重载"[]"符号，让容器可以通过下标获取元素*/100 Reference operator[](SizeType uiNum)101 {102 return *(m_Start + uiNum);103 }104 105 /*无参构造函数，创建一个空的容器*/106 CVector() : m_Start(0), m_Finish(0), m_EndOfStorage(0)107 {108 //这里面本身就不需要任何内容109 }110 111 /*以下三个构造函数功能一样，都是创建一个可以容纳uiNum个对象的容器。并且会将Value中的数据拷贝uiNum个过去。112 *只是其中的uiNum类型不一样，这里写三个是为了兼容不同的类型*/113 CVector(SizeType uiNum, const T& Value)114 {115 /*这三行是为了消除警告*/116 m_Start = 0;117 m_Finish = 0;118 m_EndOfStorage = 0;119 120 /*调用函数分配内存空间*/121 FillInitialize(uiNum, Value);122 }123 124 CVector(int uiNum, const T& Value)125 {126 /*这三行是为了消除警告*/127 m_Start = 0;128 m_Finish = 0;129 m_EndOfStorage = 0;130 131 /*调用函数分配内存空间*/132 FillInitialize(uiNum, Value);133 }134 135 CVector(long uiNum, const T& Value)136 {137 /*这三行是为了消除警告*/138 m_Start = 0;139 m_Finish = 0;140 m_EndOfStorage = 0;141 142 /*调用函数分配内存空间*/143 FillInitialize(uiNum, Value);144 }145 146 /*创建能容纳uiNum个对象的容器*/147 explicit CVector(long uiNum)148 {149 /*这三行是为了消除警告*/150 m_Start = 0;151 m_Finish = 0;152 m_EndOfStorage = 0;153 154 /*调用函数分配内存空间，其中的T()将会创建一个临时变量。但是为什么需要这样去创建呢？？155 *为了让该函数能够调用，所以创建一个临时对象*/156 FillInitialize(uiNum, T());157 }158 159 explicit CVector(int uiNum)160 {161 /*这三行是为了消除警告*/162 m_Start = 0;163 m_Finish = 0;164 m_EndOfStorage = 0;165 166 /*调用函数分配内存空间，其中的T()将会创建一个临时变量。但是为什么需要这样去创建呢？？167 *为了让该函数能够调用，所以创建一个临时对象*/168 FillInitialize(uiNum, T());169 }170 171 explicit CVector(SizeType uiNum)172 {173 /*这三行是为了消除警告*/174 m_Start = 0;175 m_Finish = 0;176 m_EndOfStorage = 0;177 178 /*调用函数分配内存空间，其中的T()将会创建一个临时变量。但是为什么需要这样去创建呢？？179 *为了让该函数能够调用，所以创建一个临时对象*/180 FillInitialize(uiNum, T());181 }182 183 ~CVector()184 {185 /*一个对象的销毁分为两步完成：186 *1、释放容器的内存空间187 *2、销毁容器*/188 destroy(m_Start, m_EndOfStorage);//释放容器占用的内存空间189 Deallocate();//调用容器中的函数，销毁容器190 }191 192 /*返回第一个元素*/193 Reference Front()194 {195 return *(m_Start);196 }197 198 /*返回最后一个元素*/199 Reference Back()200 {201 return *(m_Finish - 1);202 }203 204 /*向vector的尾部添加一个元素*/205 void PushBack(const T& Element)206 {207 /*判断容器是否已经满了，如果没有满，则直接进行插入。如果满了，则需要调用InsertAux函数，208 *为容器重新分配内存空间*/209 if(m_Finish != m_EndOfStorage)210 {211 construct(m_Finish, Element);212 ++m_Finish;213 }214 else215 {216 InsertAux(End(), Element);217 }218 }219 220 /*将容器中最后一个元素取出来*/221 void PopBack()222 {223 --m_Finish;224 destory(m_Finish);225 }226 227 /*清除指定位置的某个元素*/228 Iterator Erase(Iterator Position)229 {230 if(Position + 1 != End())231 {232 copy(Position + 1, m_Finish, Position);//将后面的数据向前移动233 }234 m_Finish--;235 destroy(m_Finish);//调用全局函数，释放多余的空间236 return Position;237 }238 239 /*清除指定某区域中的元素*/240 Iterator Erase(Iterator StartPosition, Iterator EndPosition)241 {242 if(EndPosition + 1 != End())243 {244 copy(EndPosition + 1, m_Finish, StartPosition);//将后面的数据向前移动245 }246 m_Finish -= (StartPosition - EndPosition); //调整末尾指针247 destroy(m_Finish, StartPosition - EndPosition);//调用全局函数，释放多余的空间248 return StartPosition;249 }250 251 /*重新为容器分配空间，其大小为uiNewSize，如果新的空间大于原来的空间，252 *则新增加的空间将会以InitialValue作为初值进行初始化；如果新的空间253 *小于原来的空间，将会把多余的数据清除掉*/254 void Resize(SizeType uiNewSize, const T& InitialValue)255 {256 if(uiNewSize < Size())257 {258 Erase(Begin() + uiNewSize, End());//空间过小，清除元素259 }260 else261 {262 insert(End(), uiNewSize - Size(), End());263 }264 }265 266 /*重新为容器分配空间，其大小为uiNewSize。但是用户可以不进行初始化*/267 void Resize(SizeType uiNewSize)268 {269 Resize(uiNewSize, T());270 }271 272 /*清空容器中的元素*/273 void Clear()274 {275 Erase(Begin(), End());276 }277 };278 279 template 
           
            280 void CVector
            
             ::InsertAux(Iterator Position, const T& Element)281 {282 if(m_Finish != m_EndOfStorage) //还有备用空间283 {284 construct(m_Finish, *(m_Finish - 1));//在备用空间中构造一个285 m_Finish++;//调整备用空间剩余容量286 T ElementCpoy = Element;//将要插入的节点进行拷贝287 /*调用全局函数，为要插入的节点移出一块内存空间*/288 copy_backward(Position, m_Finish - 2, m_Finish - 1);289 *Position = ElementCpoy;//将节点插入290 }291 else//没有备用空间了292 {293 const SizeType uiOldSize = Size();//计算原来空间的长度294 /*得到需要的长度，若原来大小不为零，则新开辟的大小应该为其原本大小的两倍，反之则为1*/295 const SizeType uiLen = uiOldSize != 0 ? 2 * uiOldSize : 1;296 Iterator NewStart = DataAllocator::Allocate(uiLen);//开辟内存并且将新的内存地址保存297 Iterator NewFinish = NewStart;298 try299 {300 /*将vector中的数据拷贝到新的vector内存中*/301 NewFinish = uninitialized_copy(m_Start, Position, NewStart);302 /*为新的元素设定值*/303 construct(NewFinish, Element);304 ++NewFinish;305 /*将备用空间的内容也拷贝过来，这可能没什么用！！*/306 NewFinish = uninitialized_copy(Position, m_Finish, NewFinish);307 }308 catch(...)309 {310 destroy(NewStart, NewFinish);311 DataAllocator::Deallocate(NewStart, uiLen);312 throw;313 }314 315 destroy(Begin(), End());316 Deallocate();317 318 m_Start = NewStart;319 m_Finish = NewFinish;320 m_EndOfStorage = NewStart + uiLen;321 }322 }323 324 #endif
            
           
          
         
        
       
      
     

以上代码更多的是为自己的学习做个笔记，欢迎交流讨论！