《Effective STL》学习笔记1

转载自董的博客链接地址: http://dongxicheng.org/cpp/effective-stl-part1/

本书从STL应用出发，介绍了在项目中应该怎样正确高效的使用STL。本书共有7个小节50个条款，分别为

（1） 容器：占12个条款，主要介绍了所有容器的共同指导法则

（2） vector和string：占6个条款，介绍了最常用的两种容器的一些使用经验

（3） 关联容器：占7个条款，介绍了关联容器(*map,*set)的使用经验

（4） 迭代器：占12个条款，介绍了迭代器的一些使用技巧

（5） 算法：占8个条款，介绍STL算法的正确使用方法和提高效率的技巧

（6） 仿函数、仿函数类、函数等：占5个条款，介绍仿函数的使用经验

（7） 使用STL编程：占8个条款，介绍怎样在程序中使用由容器、迭代器、算法和函数对象组成的STL

在这些条款中，有的是一些编程经验，即告诉你，如果想避免错误，应该这样编写程序，应该使用这个函数而不是另一个，还有一些是告诉你怎样选择最高效的函数以提高你程序的效率，总结如下：

{1} 介绍编程经验：

条款1：仔细选择你的容器

条款2：小心对“容器无关代码”的幻想

条款6：警惕C++最令人恼怒的解析

条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针

条款8：永不建立auto_ptr的容器

条款9：在删除选项中仔细选择

条款12：对STL容器线程安全性的期待现实一些

条款13：尽量使用vector和string来代替动态分配的数组

条款16: 如何将vector和string的数据传给遗留的API

条款17：使用“交换技巧”来修整过剩容量

条款18：避免使用vector<bool>

条款19：了解相等和等价的区别

条款20：为指针的关联容器指定比较类型

条款21: 永远让比较函数对“相等的值”返回false

条款22：避免原地修改set和multiset的键

条款26：尽量用iterator代替const_iterator，reverse_iterator和const_reverse_iterator

条款27：用distance和advance把const_iterator转化成iterator

条款28：了解如何通过reverse_iterator的base得到iterator

条款30：确保目标区间足够大

……

{2}提高程序效率：

条款3：使容器里对象的拷贝操作轻量而正确

条款4：用empty来代替检查size()是否为0

条款5：尽量使用区间成员函数代替它们的单元素兄弟

条款14：使用reserve来避免不必要的重新分配

条款15：小心string实现的多样性

条款23：考虑用有序vector代替关联容器

条款24：当关乎效率时应该在map::operator[]和map-insert之间仔细选择

条款25：熟悉非标准散列容器

条款29：需要一个一个字符输入时考虑使用istreambuf_iterator

条款31：了解你的排序选择

条款44：尽量用成员函数代替同名的算法

条款46：考虑使用函数对象代替函数作算法的参数

关于《Effective STL》学习笔记分为四部分，本文是第一部分（对应书中“容器”一节），第二、三、四部分分别为：《Effective STL》学习笔记(第二部分)（对应书中“vector和string”，“关联容器”两小节），《Effective STL》学习笔记(第三部分)（对应书中“迭代器”和“算法”两小节），《Effective STL》学习笔记(第四部分)（对应书中“仿函数、仿函数类、函数等”和“使用STL”两小节）。

1、 容器

本章关注的是可以适用于所有STL容器的指导方针。后面的章节则专注于特殊的容器类型。

条款1：仔细选择你的容器

C++提供了很多可供程序员使用的容器：

（1） 标准STL序列容器：vector，string，deque和list

（2） 标准STL关联容器：set，multiset，map和multimap

（3） 非标准序列容器slist（单链表）和rope（重型字符串）

（4） 非标准关联容器hash_set，hash_multiset，hash_map和hash_multimap

（5） vector<char>可以作为string的替代品

（6） vector作为标准关联容器的替代品

（7） 几种标准非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue

不同容器有不同的优缺点，用户需要根据实际应用的特点综合决定使用哪种容器，如：vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

条款2：小心对“容器无关代码”的幻想

本条款要告诫程序员：编写与容器无关的代码是没有必要的。

有人想编写这样的程序，刚开始时使用vector存储，之后由于需求的变化，将vector改为deque或者list，其他代码不变。实际上，这基本上是做不到的。这是因为：不同的序列容器所对应了不同的迭代器、指针和引用的失效规则，此外，不同的容器支持的操作也不相同，如：vector支持reserve()和capacity()，而deque和list不支持；即使是相同的操作，复杂度也不一样（如：insert），这会让你的系统产生意想不到的瓶颈。

此外，鼓励程序员在声明容器和迭代器的时候使用typedef进行重命名，这能够对你的程序进行封转，从而使用起来更简单，如有下面一个map容器：

map<string,vectorWidget>::iterator,CIStringCompare>;

如要用const_iterator遍历这个map，你需不止一次地写下：

map<string, vectorWidget>::iterator, CIStringCompare>::const_iterator

如果使用typedef，会快速方便很多。

条款3：使容器里对象的拷贝操作轻量而正确

容器容纳了对象，但不是你给它们的那个对象。当你向容器中插入一个对象时，你插入的是该对象的拷贝而不是它本身；当你从容器中获取一个对象时，你获取的是容器中对象的拷贝。

拷贝是STL的基本工作方式。当你删除或者插入某个对象时，现有容器中的元素会移动（拷贝）；当你使用了排序算法，remove、uniquer或者他们的同类，rotate或者reverse，对象会移动（拷贝）。

一个使拷贝更高效、正确的方式是建立指针的容器而不是对象的容器，即保存对象的指针而不是对象，然而，指针的容器有它们自己STL相关的头疼问题，改进的方法是采用智能指针。

条款4：用empty来代替检查size()是否为0

对于任意容器c，写下

if (c.size() == 0)…

本质上等价于写下

if (c.empty())…

但是为什么第一种方式比第二种优呢？理由很简单：对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费线性时间。

这什么造成list这么麻烦？为什么不能也提供一个常数时间的size？如果size是一个常数时间操作，当进行增加/删除操作时每个list成员函数必须更新list的大小，也包括了splice，这会造成splice的效率降低（现在的splice是常量级的），反之，如果splice不必修改list大小，那么它就是常量级地，而size则变为线性复杂度，因此，设计者需要权衡这两个操作的算法：一个或者另一个可以是常数时间操作。

条款5：尽量使用区间成员函数代替单元素操作

给定两个vector，v1和v2，怎样使v1的内容和v2的后半部分一样？

可行的解决方案有：

（1） 使用区间函数assign：

 v1.assign(v2.begin() + v2.size() / 2, v2.end()); 

（2） 使用单元素操作：

 vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;

ci != v2.end();

++ci)

v1.push_back(*ci); 

（3） 使用copy区间函数

 v1.clear();

copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1)); 

（4） 使用insert区间函数

 v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end()); 

最优的方案是assign方案，理由如下：

首先，使用区间函数的好处是：

● 一般来说使用区间成员函数可以输入更少的代码。

● 区间成员函数会导致代码更清晰更直接了当。

使用copy区间函数存在的问题是：

【1】 需要编写更多的代码，比如：v1.clear()，这个与insert区间函数类似

【2】 copy没有表现出循环，但是在copy中的确存在一个循环，这会降低性能

使用insert单元素版本的代码对你征收了三种不同的性能税，分别为：

【1】 没有必要的函数调用；

【2】 无效率地把v中的现有元素移动到它们最终插入后的位置的开销；

【3】 重复使用单元素插入而不是一个区间插入必须处理内存分配。

下面进行总结：

说明：参数类型iterator表示容器的迭代器类型，也就是container::iterator，参数类型InputIterator表示可以接受任何输入迭代器。

【1】 区间构造

所有标准容器都提供这种形式的构造函数：

 container::container(InputIterator begin, // 区间的起点

InputIterator end); // 区间的终点 

【2】 区间插入

所有标准序列容器都提供这种形式的insert：

void container::insert(iterator position, // 区间插入的位置

InputIterator begin, // 插入区间的起点

InputIterator end); // 插入区间的终点

关联容器使用它们的比较函数来决定元素要放在哪里，所以它们了省略position参数。

.

 void container::insert(lnputIterator begin, InputIterator end); 

【3】 区间删除

每个标准容器都提供了一个区间形式的erase，但是序列和关联容器的返回类型不同。序列容器提供了这个：

 iterator container::erase(iterator begin, iterator end); 

而关联容器提供这个：

 void container::erase(iterator begin, iterator end); 

为什么不同？解释是如果erase的关联容器版本返回一个迭代器（被删除的那个元素的下一个）会招致一个无法接受的性能下降.

【4】 区间赋值

所有标准列容器都提供了区间形式的assign：

 void container::assign(InputIterator begin, InputIterator end); 

条款6：警惕C++最令人恼怒的解析

假设你有一个int的文件，你想要把那些int拷贝到一个list中。这看起来像是一个合理的方式：

ifstream dataFile("ints.dat");

list<int> data(istream_iterator<int>(dataFile), // 警告！这完成的并不

istream_iterator<int>()); // 是像你想象的那样

这里的想法是传一对istream_iterator给list的区间构造函数（参见条款5），因此把int从文件拷贝到list中。

实际上，这段代码可以编译通过，但运行时不会产生任何结果。仔细分析后，会发现，你这段代码实际上是声明了一个data函数，它的返回值是list<int>，两个参数均为istream_iterator<int>类型。

解决办法是在数据声明中从时髦地使用匿名istream_iterator对象后退一步，仅仅给那些迭代器名字。以下代码到哪里都能工作：

ifstream dataFile("ints.dat");

istream_iterator<int> dataBegin(dataFile);

istream_iterator<int> dataEnd;

list<int> data(dataBegin, dataEnd);

条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针

条款8：永不建立auto_ptr的容器

条款9：在删除选项中仔细选择

（1）假定你有一个标准STL容器，c，容纳int，

 Container<int> c; 

而你想把c中所有值为1963的对象都去，则不同的容器类型采用的方法不同：没有一种是通用的.

[1] 如果采用连续内存容器(vector、queue和string)，最好的方法是erase-remove惯用法：

c.erase(remove(c.begin(), c.end(), 1963), // 当c是vector、string

c.end()); // 或deque时，erase-remove惯用法是去除特定值的元素的最佳方法

[2] 对于list，最有效的方法是直接使用remove函数：

 c.remove(1963); 

[3] 对于关联容器，解决问题的适当方法是调用erase：

 c.erase(1963); // 当c是标准关联容器时,erase成员函数是去除特定值的元素的最佳方法 

（2）让我们换一下问题：不是从c中除去每个有特定值的元素，而是消除下面判断式返回真的每个对象：

 bool badValue(int x); // 返回x是否是“bad” 

[1] 对于序列容器（vector、list、deque和string），只需要将remove换成remove_if即可：

c.erase(remove_if(c.begin(), c.end(), badValue), // 当c是vector、string

c.end()); // 或deque时这是去掉badValue返回真的对象的最佳方法

c.remove_if(badValue); // 当c是list时这是去掉badValue返回真的对象的最佳方法

[2] 对于关联容器，有两种方法处理该问题，一个更容易编码，另一个更高效。“更容

易但效率较低”的解决方案用remove_copy_if把我们需要的值拷贝到一个新容器中，然后把原容器的内容和新的交换：

AssocContainer<int> c; // c现在是一种标准关联容器

AssocContainer<int> goodValues; // 用于容纳不删除的值的临时容器

remove_copy_if(c.begin(), c.end(), // 从c拷贝不删除

inserter(goodValues, // 的值到

goodValues.end()), // goodValues

badValue);

c.swap(goodValues); // 交换c和goodValues的内容

“更高效”的解决方案是直接从原容器删除元素。不过，因为关联容器没有提供类似remove_if的成员函数，所以我们必须写一个循环来迭代c中的元素，和原来一样删除元素：

AssocContainer<int> c;

...

for (AssocContainer<int>::iterator i = c.begin(); // for循环的第三部分

i != c.end(); // 是空的；i现在在下面

/*nothing*/ ){ // 自增

if (badValue(*i)) c.erase(i++); // 对于坏的值，把当前的

else ++i; // i传给erase，然后

} // 作为副作用增加i；对于好的值，只增加i

（3）进一步丰富该问题：不仅删除badValue返回真的每个元素，而且每当一个元素被删掉时，我们也想把一条消息写到日志文件中。

[1] 对于关联容器，只需要对我们刚才开发的循环做一个微不足道的修改就行了：

ofstream logFile; // 要写入的日志文件

AssocContainer<int> c;

...

for (AssocContainer<int>::iterator i = c.begin(); // 循环条件和前面一样

i !=c.end();){

if (badValue(*i)){

logFile << "Erasing " << *i <<'\n'; // 写日志文件

c.erase(i++); // 删除元素

}

else ++i;

}

[2] 对于vector、string、list和deque，必须利用erase的返回值。那个返回值正是我们需要的：一旦删除完成，它就是指向紧接在被删元素之后的元素的有效迭代器。换句话说，我们这么写：

for (SeqContainer<int>::iterator i = c.begin();

i != c.end();){

if (badValue(*i)){

logFile << "Erasing " << *i << '\n';

i = c.erase(i); // 通过把erase的返回值赋给i来保持i有效

}

else

++i;

}

条款10：注意分配器的协定和约束

条款11：理解自定义分配器的正确用法

条款12：对STL容器线程安全性的期待现实一些

当涉及到线程安全和STL容器时，你可以确定库实现了“允许在一个容器上的多读者”（在读取时不能 有任何写入者操作这个容器。）和“不同容器上的多个写者”（多线程可以同时写不同的容器。）。你不能希望库消除对手工并行控制的需要，且你完全不能依赖于任何线程支持。