STL相关知识点整理.pdfVIP

Evernote Export STL相关知识点整理 1. STL容器分类 ** STL容器分为连续内存容器和基于节点的容器 ** - 连续内存容器： 也叫做基于数组的容器，在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被插入或者已存在元素 被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来的被删除的元素所占的空 间。 标准的连续内存容器是：vector ， string 和deque （双端队列）。 - 基于节点的容器： 在每个内存块（动态分配）中只保存一个元素。容器元素的插入或者删除只影响指向节点的指针，而不是节点自己的内 容。所以当有东西插入或者删除时，元素值不需要移动。表现为链表的容器，比如list和slist 都是基于节点的，所有的标准 关联容器(map,set)也是（典型实现时红黑树）。 2. vector等底层机制 对于STL容器，只要不超过它们的最大大小，它们就可以自动增长到足以容纳你放进去的数据。对于vector和string ，只要 需要更多的空间，就以realloc等价的思想来增长。这个类似于realloc 的操作有四个部分： 1. 分配新的内存块，它由容器目前容量的几倍。在大部分实现中，vector 和string 的容量每次以2为因数增长，也就是说， 当容器必须扩展时，它们的容量每次翻倍。 2. 把所有的元素从旧的内存拷贝到它新的内存。 3. 销毁旧内存中的对象。 4. 回收旧内存。 以上这些操作都很费时间，并且意味着简单的把一个元素插入vecotr或者string 的动作也会可能让迭代器/指针/引用失效。 为了避免重新分配的发生，我们可以用reserve()函数强制把容器的容量修改，使其容量设置足够大，最好在容器被构造后 立即执行。 例如： 假定想建立一个容纳 1-1000值得vector 。如果没有使用reserve ，可以像这样来做 vector v; for(int i = 1; i = 1000; i++) v.push_back(i); 在大多数的STL实现中，这段代码在循环过程中会导致2到10次的重新分配。（vector在重新分配发生时一般把容量翻倍） 如果改为reserve。我们得到以下代码 vector v: v.reserve(1000); for(int i = 1; i= 1000; i++) v.push_back(i); 在这个循环中不会发生重新分配。 注意：reserve函数不改变容器中现有对象的个数 3. 关于迭代器失效 根据第 1点和第2点的说明，我们了解到： （1）. 对于连续内存容器即序列容器（vecotr,string ，deque）： 插入操作可能会让所有的迭代器失效（迭代器相当于一 STL相关知识点整理.html [2013/4/20 0:48:35] Evernote Export 个广义指针，万一旧空间不够而执行新空间分配的话，所有的迭代器均会失效。） 删除造作会导致指向该元素以及该元素 后面的元素的迭代器失效 （2）.对于基于节点的容器即关联容器： 插入操作和删除操作均会导致指向该元素的迭代器失效，其他元素的迭代器不受 影响。 在一个序列容器上用一个迭代器作为参数调用erase ，会返回一个新迭代器指向下一个位置，但在关联容器上什么都不会返 回。 4. 容器效率问题 容器容纳了对象，当从容器中获取一个对象时，所得到的对象不是容器里的那个对象。取而代之的是向容器中添加一个对 象（比如通过insert或者push_back等），进入容器的是你指定的对象的拷贝。拷进去，拷出来。这就是STL 的方式。对于 类可能用到拷贝构造函数和拷贝赋值操作符完成。一旦一个对象进入一个容器，以后对它的拷贝并不少见。如果 从vector 、string或者deque 中插入或者删除了什么，先用的容器元素会移动（拷贝）。如果使用了任何的排序算法，对象 也会移动（拷贝）。 如果用一个拷贝过程很昂贵的对象填充一个容器，那么简答的操作-- 把对象放进容器也会被证明是一 个性能的瓶颈。容器中移动越多东西，就会在靠背上浪费越多的内存的时钟周期。一个使拷贝更高效的方式是建立指针的 容器而不是对象本身的容器。 5. 对于STL容器的线程安全性 1. 多个读取者是安全的。多个线程可能同时读取一个容器的内存，这将正确