Effective STL阅读笔记

,

Containers

1.慎重选择容器

除了传统地将容器分为序列式或者关联式之外,还可以根据内存分布来进行划分:

  • 连续内存.指的是容器的元素存储在一个连续的内存空间,或者是几段连续的内存空间中.当有插入,删除的元素时,往往需要将其他元素在内存空间中进行平移.例如deque,vector,string等.
  • 基于节点.每个内存块是动态分配的,一般只保存一个元素,当出现插入或者删除时,只影响到指向节点的指针,不影响内容本身.比如list,set等,前者是基于链表实现,后者基于红黑树实现.

2.不要试图编写独立于容器类型的代码

虽然STL的设计,很大程度上体现了泛型编程的思想,比如说:

  • 容器可以视为,将其包含的数据类型泛化的某种数据结构.
  • 算法可以视为,将其作用的迭代器泛化的函数.
  • 迭代器可以视为,将其所指对象类型泛化的指针.

但如果想要在进一步的泛化,比如说,设计一套能够不考虑底层所使用容器的代码,使得无论使用哪种类型的容器都可以提供出通用的接口.这种行为往往很难并且意义不大.

我们应该对于容器的选择进行慎重考虑,并且围绕着所选容器的特性来设计相关的代码.

3.确保对象的拷贝正确而高效

容器的相关操作中,会涉及到拷贝的情况很多,比如说,加入数据或者取出数据,排序,甚至是vector等连续内存分布容器中的元素移动,都会涉及到拷贝.

这对于内部对象为对象的容器来说,定义好拷贝构造和赋值重载非常重要.

在含有继承的对象中,在类型为基类的容器中,一定要防止slicing的发生.

一般情况下,建议包含指针,一是拷贝成本低,二是支持多态.比如std::vector<Widget*> vw.

4.使用empty()代替size() == 0.

前者是常数级别的复杂度,后者在一些list实现中为线性,高下立判.

5.优先使用区间成员函数

需要对容器中的某个区间进行操作时,我们可能考虑使用for循环遍历等方式,但多数时候,使用区间函数更好.

使用区间成员函数具有,代码量少,执行效率高的优点.常见的有:

  • 区间构造.
  • insert
  • erase
  • assign.

其主要特点为,以迭代器作为参数实现的.

关于在开销上的对比,首先是函数调用次数上的开销.但对于vector来说,主要还是额外的内存拷贝的开销.

vector<int>::iterator insertLoc(v.begin()); 
for (int i = 0; i < numValues; ++i) {
		insertLoc = v.insert(insertLoc, data[i]);
		++insertLoc; 
}//for循环+单元素操作
v.insert(v.begin(), data, data + numValues);//调用区间操作函数

在这里以vector为例,对于第二种方式,其中的元素,一次性地完成numValues个移动,每次移动1次拷贝,总共n次拷贝.而第一种方法,做numValues次移动,总共有n*numValues次.

如果是list等容器,虽然不会有额外的内存拷贝,但会有额外的指针赋值.

9.慎重选择删除元素的方法

一般STL中与删除有关的是erase和remove,首先要搞清楚两者的区别.

总结一下:

  • 要删除容器中有特定值的所有对象:如果容器是 vector,string 或deque,则使用 erase-remove 习惯用法,如果容器是list,则使用 list::remove,如果容器是一个标准关联容器,则使用它的 erase 成员函数.

10.了解分配器的约定和限制

11.理解并自定义分配子的合理用法

除此之外,在item 7中,提醒对于容器中含有new对应的指针的情况,不能忘记delete,或者推荐使用智能指针.在item 8指出了当使用auto_ptr会导致指针无效的问题,所以不推荐使用auto_ptr.在item 12中,提醒我们当一个容器作为多线程程序的共享数据时,需要程序员做互斥控制,比如说上锁等.

vector,string

14.使用reserve避免不必要的重新分配

reserver会因为vector的size超过容量而出发动态扩容.其过程如下:

15.小心string实现的多样性

16.将vector和string传入遗留API

17.使用swap技巧修整过剩容量

在C++ 11中,提供了shrink_to_fit().

//首先是采用swap的方法
std::vector<Contestant> contestants;
std::vector<Contestant>(contestants).swap(contestants);
//C++ 11后可以直接使用shrink_to_fit
contestants.shrink_to_fit();

需要注意的是,当发生交换之后,迭代器也被交换,原先的迭代器可以说是迁移到另一个迭代器中了.

其他

条款13建议我们尽可能使用vector和string代替动态数组,除了STL提供动态管理的便捷性,还有有一些便于使用的API(STL算法).