vector

  1. vector与array的唯一区别在于空间的运用的灵活性，array是静态空间，一旦配置了就不能改变，vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素
  2. vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。
  3. vector维护的是一个连续线性空间，支持随机存取，因此vector提供的是随机存取的迭代器，它以两个迭代器start和finish分别指向目前使用空间的头和尾，并以迭代器end_of_storage指向目前可用空间的尾端
  4. 一个vector的容量(capacity)永远大于或等于其大小，一旦容量等于大小就是满载，下次再有新增元素，整个vector就得重新分配内存重新复制
  5. vector的动态增加大小并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此对于vector的任何操作一旦引起空间重新配置，指向原vector的所有迭代器都会失效
  6. vector的erase(first,last)操作是将last之后的元素copy覆盖到first之后的位置，然后再把copy函数返回的迭代器位置到finsh迭代器之间的所有元素destroy即可，erase(position)也是这样的实现方式
  7. vector在实现insert(pos,n,x)时，如果备用空间大于等于n的话，当pos之后的元素数量大于n时，使用uninitialized_copy函数将finish之前的n个元素后移，然后在使用copy_backward函数将pos之后剩余的元素右移，最后使用fill函数填充新元素
  8. 当pos之后的元素小于n时，先将n-(finish-pos)个元素构造于finish位置，然后将原先pos之后的元素都使用uninitialized_copy函数置于这些构造新元素之后，然后再将pos与原先finish迭代器之间的位置用x来填充
  9. 当备用空间小于n时，vector会先配置新空间，然后依次将pos之前的元素、新增的n个元素以及pos之后的元素拷贝到新的内存空间

std::sort

  1. sort函数接受两个随机存取迭代器，然后将区间内的所有元素以渐增方式由小到大重新排列，第二个版本则允许用户指定一个callable对象作为排序标准
  2. 由于sort要求参数是随机存取迭代器，因此只有vector、deque以及std::array的迭代器能作为其参数
  3. STL的sort算法，数据量大时采用快速排序，分段递归排序，一旦分段后的数据量小于某个门槛，为避免快速排序递归调用带来过大的额外开销，就改用插入排序，如果递归层次过深，还会改用堆排序
  4. 插入排序以双层循环的形式进行，外循环遍历整个序列，每次迭代决定出一个子区间；内循环遍历子区间，将子区间内的每一个“逆序对”倒转过来，一旦不存在逆序对，序列即排序完毕，算法复杂度为O(N^2)。当数据量很少时，有不错的效果，而且没有其他复杂算法有着诸如递归调用等操作带来的额外负荷
  5. STL中的插入排序在实现时，当尾元素比头元素还小时直接使用copy_backward将整个区间向右递移一个位置，然后再令头元素等于原先的尾元素即可。当尾元素不比头元素小时，循环从尾部开始遍历知道找到比尾元素小的结点，每次都把前一个值赋给下一个地址，然后再将尾元素插入。
  6. 任意一个元素都可以被选来当作划分值，但是其合适与否却会影响快排的效率，为了避免“元素当初输入时不够随机”所带来的恶化效应，最理想最稳当的方式就是取整个序列的头、尾、中央三个位置的元素，以其中值作为划分值，这种做法称为三点中值快排。为了能快速取出中央位置的元素，迭代器必须能够随机定位，因此必须是个随机存取迭代器
  7. 适度评估序列的大小，然后决定采用快排或插入排序是值得采纳的一种优化措施，序列大小的实际最佳值因设备而异
  8. IntroSort排序其行为在大部分情况下几乎与三点中值快排法完全相同，但是当分割行为有恶化为二次行为倾向时，能够自我检测，转而改用堆排序，使效率维持在堆排序的O(nlgn)
  9. STL中sort算法最终实现过程是：
    （1）判断排序数组的元素数量是否小于设定值，小于则使用插入排序，否则使用快速排序
    （2）在递归调用快排时判断此时的递归层数是否大于阈值，如果大于则使用堆排序，否则还是使用快排
    （3）递归调用完成后数组中存在若干长度小于16的相当程度排序的子数组，但尚未完全排序，此时在母函数中调用插入排序即可完成最终排序

hashtable

  1. hashtable(散列表)在插入、删除、搜寻等操作上也具有“常数平均时间”的表现，而且这种表现是以统计为基础，不需仰赖输入元素的随机性
  2. 解决哈希冲突的方法有线性探测、二次探测、开链等做法，除非使用开链法负载系数(loading factor)永远在0~1之间
  3. SGI STL就是使用的链地址法，hash table内的元素为桶子，因为表格内的每个单元涵盖的不仅是节点（元素），甚至可能是一“桶”节点。
  4. 桶(bucket)所维护的linked list，并不采用STL的list或者slist，而是自行维护上述的hash table node，而bucket聚合体则以vector完成，以便有动态扩充能力
  5. hash table迭代器必须永远维系着与整个“buckets vector”的关系，并记录目前所指的节点，其前进操作是首先尝试从目前所指的节点出发，前进一个位置（节点），由于节点被安置于list内，所以利用节点的next指针即可轻易达成前进操作，如果目前节点正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点
  6. 从上述5可看出，hash table的迭代器没有后退操作，也没有所谓的逆向迭代器

STL空间配置器allocator

  1. allocator是空间配置器而不是内存配置器是因为空间不一定是内存，空间也可以是磁盘或其他辅助存储介质，我们可以写一个allocator直接向硬盘取空间
  2. SGI STL的配置器与众不同，也与标准规范不同，其名称是alloc而非allocator，而且不接受任何参数，并且SGI STL的每一个容器都已经指定其缺省的空间配置器为alloc
  3. 为了精密分工，STL allocator将内存的分配、释放和对象的构造、析构区分开来，内存配置由alloc::allocate()负责，内存释放则于alloc::deallocate()负责，对象构造由::construct()负责，对象析构由::destroy()负责