STL相关知识点整理

《STL相关知识点整理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EvernoteExportSTL相关知识点整理1.STL容器分类**STL容器分为连续内存容器和基于节点的容器**-连续内存容器：也叫做基于数组的容器，在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被插入或者已存在元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来的被删除的元素所占的空间。标准的连续内存容器是：vector，string和deque（双端队列）。-基于节点的容器：在每个内存块（动态分配）中只保存一个元素。容器元素的插入或者删除只影响指

2、向节点的指针，而不是节点自己的内容。所以当有东西插入或者删除时，元素值不需要移动。表现为链表的容器，比如list和slist都是基于节点的，所有的标准关联容器(map,set)也是（典型实现时红黑树）。2.vector等底层机制对于STL容器，只要不超过它们的最大大小，它们就可以自动增长到足以容纳你放进去的数据。对于vector和string，只要需要更多的空间，就以realloc等价的思想来增长。这个类似于realloc的操作有四个部分：1.分配新的内存块，它由容器目前容量的几倍。在大部分实现中，vect

3、or和string的容量每次以2为因数增长，也就是说，当容器必须扩展时，它们的容量每次翻倍。2.把所有的元素从旧的内存拷贝到它新的内存。3.销毁旧内存中的对象。4.回收旧内存。以上这些操作都很费时间，并且意味着简单的把一个元素插入vecotr或者string的动作也会可能让迭代器/指针/引用失效。为了避免重新分配的发生，我们可以用reserve()函数强制把容器的容量修改，使其容量设置足够大，最好在容器被构造后立即执行。例如：假定想建立一个容纳1-1000值得vector。如果没有使用reserve，可以像

4、这样来做vectorv;for(inti=1;i<=1000;i++)v.push_back(i);在大多数的STL实现中，这段代码在循环过程中会导致2到10次的重新分配。（vector在重新分配发生时一般把容量翻倍）如果改为reserve。我们得到以下代码vectorv:v.reserve(1000);for(inti=1;i<=1000;i++)v.push_back(i);在这个循环中不会发生重新分配。注意：reserve函数不改变容器中现有对象的个数3.关于迭代器失效根据第1点和第2点的说明，我们了

5、解到：（1）.对于连续内存容器即序列容器（vecotr,string，deque）：插入操作可能会让所有的迭代器失效（迭代器相当于一STL相关知识点整理.html[2013/4/200:48:35]EvernoteExport个广义指针，万一旧空间不够而执行新空间分配的话，所有的迭代器均会失效。）删除造作会导致指向该元素以及该元素后面的元素的迭代器失效（2）.对于基于节点的容器即关联容器：插入操作和删除操作均会导致指向该元素的迭代器失效，其他元素的迭代器不受影响。在一个序列容器上用一个迭代器作为参数调用er

6、ase，会返回一个新迭代器指向下一个位置，但在关联容器上什么都不会返回。4.容器效率问题容器容纳了对象，当从容器中获取一个对象时，所得到的对象不是容器里的那个对象。取而代之的是向容器中添加一个对象（比如通过insert或者push_back等），进入容器的是你指定的对象的拷贝。拷进去，拷出来。这就是STL的方式。对于类可能用到拷贝构造函数和拷贝赋值操作符完成。一旦一个对象进入一个容器，以后对它的拷贝并不少见。如果从vector、string或者deque中插入或者删除了什么，先用的容器元素会移动（拷贝）。如

7、果使用了任何的排序算法，对象也会移动（拷贝）。如果用一个拷贝过程很昂贵的对象填充一个容器，那么简答的操作--把对象放进容器也会被证明是一个性能的瓶颈。容器中移动越多东西，就会在靠背上浪费越多的内存的时钟周期。一个使拷贝更高效的方式是建立指针的容器而不是对象本身的容器。5.对于STL容器的线程安全性1.多个读取者是安全的。多个线程可能同时读取一个容器的内存，这将正确的执行。当然，在读取时不能有任何写入者操作这个容器2.对于不同容器的多个写入者是安全的。多线程可以同时写不同的容器。3.其他情况没法保证线程安全（

8、比如多线程同时写一个容器的时候线程不安全）6.关于set容器以及迭代器set容器底层一般是用平衡二叉树实现的，平衡二叉树是一个二叉搜索树，有排序功能，要理解插入到set中的元素如何排序，先要高清“相等”和“等价”的区别，具体请参见EffectiveSTl的条款19一个set的迭代器begin()会返回set中最小的一个值。（如果要自定义排序需要重载）7.各种容器的特性vector头文件：vector典型的序列容器