C++标准库-容器类使用总结

 

List:并没有提供以operator[]直接存取元素的能力，因为lists不支持随机存取。

Multimaps：不允许我们使用subscript操作符，因为multimaps允许单一索引对应到多个不同元素，而下表操作符只能处理单一实值。

1 容器共性

?  所以容器提供的都是”value”而不是”reference”语意。容器进行元素的安插操作时，内部实施的是拷贝操作，置于容器内。因此如果容器元素不支持copy的话，则将无法利用容器。

?  赋值(Assignments)和swap()：当你对着容器赋值元素时，源容器的所有元素被拷贝到目标容器内，后者原来的所有元素全被移除。所以赋值操作代价比较高。如果拷贝后原容器不再被使用，那么我们可以使用一个简单的优化方法：swap，其性能很优异，因为它只交换容器的内部数据。

2  VECTOR

?  Vector的元素可以是任意型别T，但必须具备assignable和copyable两个性质。

?  Vector一般不能缩减空间，但是有一个间接缩减容器的方法：

{

std::vector  tmp(v);

v.swap(tmp);

}  //加一对大括号是可以让tmp退出{}的时候自动析构

上述过程简写为std::vector (v).swap(v);

触类旁通清理vector内存空间就可以写成std::vector ().swap(v);

3 Deques

?  Deque块两端都能快速安插元素和移除元素，但中段部分安插、移除元素的速度相对较慢；

?  存取元素相对于vector多一个间接过程，所以元素的存取和迭代器的动作会慢一点；

?  Deque的内存块不再被使用时，会被释放。

4 List

?  不支持随机存取

5 Sets和Multisets

?  自动排序造成sets和mulltiset的一个重要限制：你不能直接改变元素值，因为这样会打乱原本争取顺序；

?  Sets和mulitsets不提供直接存取元素的任何操作素

?  set对于性能有明确的保证：set::find和set::insert消耗时间级别都为logN

?  红黑树并非提供logN级别的搜索的唯一数据结构。很容易想到的就是在有序数集中进行binary_search，该算也提供的logN级别的时间复杂度，而且最数据结构的要求仅仅是“一个有序顺序集（该集支持某些必要操作）”,而且, 常数因子比set更小。使用set会占用更多的空间，不利于cache机制的使用，且可能造成更多的page faults。

(可以看到,由于缓存、缺页等各方面因素，二分查找和对于set的查找性能相差极大。)

?  在关联式容器中“搜寻某元素并返回后继元素”可能颇为耗时，因为这种容器的底部是以二叉树完成，所以为了效率，关联器中erase函数返回值是空的。