Effective STL 摘要

159 阅读 0 评论 105 点赞

我是靠谱客的博主凶狠高跟鞋，最近开发中收集的这篇文章主要介绍Effective STL 摘要，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

术语

● vector、string、deque和list被称为标准序列容器；而标准关联容器是set、multiset、map和multimap。
● 迭代器被分成五个种类。简要地说，输入迭代器是每个迭代位置只能被读一次的只读迭代器；输出迭代器是每个迭代位置只能被写一次的只写迭代器；输入和输出迭代器被塑造为读和写输入和输出流，因此并不奇怪输入和输出迭代器最通常的表现分别是istream_iterator和ostream_iterator；前向迭代器有输入和输出迭代器的能力，同时它们可以反复读或写一个位置，但它们不支持operator--，所以它们可以高效地向前移动任意次数；双向迭代器就像前向迭代器，除了它们的后退可以像前进一样容易，list和标准关联容器都提供双向迭代器；随机访问迭代器可以做双向迭代器做的一切事情，它们也提供“迭代器算术”，即有一步向前或向后跳的能力，vector、string和deque都提供随机访问迭代器。
● 重载了函数调用操作符（即 operator()）的任何类叫做仿函数类。从这样的类建立的对象称为函数对象或仿函数，并将operator()定义为const类型。STL中大部分可以使用函数对象的地方也都可以用真函数，所以我经常使用术语“函数对象”来表示C++函数和真的函数对象。
● 函数适配器针对类成员函数而设计的函数适配器：mem_fun_ref及mem_fun，被mem_fun_ref及mem_fun修饰的成员函数必须是const的；针对一般函数（即非类成员函数）而设计的函数适配器：ptr_fun。
● 仿函数适配器（函数绑定器）是指能够将仿函数和另一个仿函数（或某个值或某个函数）结合在一起的仿函数。比如：not1, not2, bind1st, bind2nd等。
● 迭代器适配器（Iterator Adapters）有三种：Insert iterators ，stream iterators ，Reverse iterators。
● 标准容器适配器有三种：栈（stack）、队列（queue）和优先队列（priority_queue）。
● string和wstring
关于string的任何东西都可以相等地应用到它的宽字符兄弟 wstring。类似地，任何时候提及string和char或char*之间的关系，对于wstring和wchar_t或wchar_t*之间的关序也是正确的。因为string和wstring都是同一个模板basic_string的实例化。

容器

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

● 标准STL序列容器：vector、string、deque和list。
● 非标准STL序列容器：slist是一个单向链表，rope本质上是一个重型字符串。
● 标准STL关联容器：set、multiset、map和multimap。
● 非标准STL关联容器：hash_set、hash_multiset、hash_map和hash_multimap。
● 几种标准非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue。
标准的连续内存容器在一个或多个（动态分配）的内存块中保存它们的元素，有vector、string和deque及rope。
基于节点的容器指在每个内存块（动态分配）中只保存一个元素，list、slist及所有的标准关联容器都是此类型。
● 你需要“可以在容器的任意位置插入一个新元素”的能力吗？如果是，则你需要序列容器。
● 你关心元素在容器中的顺序吗？如果不，散列容器就是可行的选择；否则，你要避免使用散列容器。
● 必须使用标准C++中的容器吗？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一类迭代器？如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string。
● 当插入或者删除数据时，是否非常在意容器内现有元素的移动？如果是，你就必须放弃连续内存容器。
● 容器中的数据的内存布局需要兼容C吗？如果是，你就只能用vector。
● 查找速度很重要吗？如果是，你就应该看看散列容器，排序的vector和标准的关联容器——大概是这个顺序。
● 你介意如果容器的底层使用了引用计数吗？如果是，你就得避开string，你可以考虑使用vector<char>。
● 你需要插入和删除的事务性语义吗？即你需要有可靠地回退插入和删除的能力吗？如果是，你就需要使用基于节点的容器。如果你需要多元素插入的事务性语义，你就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。
● 你要把迭代器、指针和引用的失效次数减到最少吗？如果是，你就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
● 你需要具有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效。如果你遇到这种情况，deque就是你梦想的容器。

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

不同的容器是不同的，而且它们的优点和缺点有重大不同；它们并不被设计成可互换。

STL是建立在泛化之上的。数组泛化为容器，参数化了所包含的对象的类型；函数泛化为算法，参数化了所用的迭代器的类型；指针泛化为迭代器，参数化了所指向的对象的类型。

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

容器容纳了对象，但不是你给它们的那个对象。此外，当你从容器中获取一个对象时，你所得到的对象也不是容器里的那个对象。取而代之的是，当你向容器中添加一个对象（比如通过insert或push_back等），进入容器的是你指定的对象的拷贝。拷进去，拷出来，这就是STL的工作方式。是的，STL容器使用了拷贝，但是别忘了一个事实：比起数组它们仍然是一个进步。

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

对于判断容器是否为空，你应该首选empty成员函数。而且理由很简单：对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费了线性时间。

不管发生了什么，如果你用empty()来代替检查是否size() == 0，你都不会出错。

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

所谓区间成员函数是指对容器的某一段区间的元素进行操作的函数，而单元素成员函数是指只对容器的某一个元素进行操作的函数。一般来说使用区间成员函数可以输入更少的代码；同时区间成员函数使代码更清晰更直接了当。

注：几乎所有目标区间被插入迭代器指定的copy的使用，都可以调用区间成员函数来替代。

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

假设你有一个存有int型数据的文件，你想要把那些int拷贝到一个list中。这看起来像是一个合理的方式：
ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile),istream_iterator<int>()); // 警告！这完成的并不像你想象的那样
用括号包围一个实参的声明是不合法的，但用括号包围一个函数调用的观点是合法的。语句第一个参数是实参，而第二个参数是一个函数指针。所以我们可以通过为第一个实参增加一对括号，强迫编译器以我们的方式看事情：
list<int> data((istream_iterator<int>(dataFile)),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掉那些指针

下面代码直接导致一个内存泄漏：
void doSomething()
{
vector<Widget*> vwp;
for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
vwp.push_back(new Widget);
... // 使用vwp
} // Widgets在这里泄漏了！

幸运的是，我们完全可以使用智能指针避免内存泄露。如利用Boost的shared_ptr，本条款的原始例子可以重写为这样：
void doSomething()
{
typedef boost::shared_ ptr<Widget> SPW; //SPW = "shared_ptr to Widget"
vector<SPW> vwp;
for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
vwp.push_back(SPW(new Widget)); // 从一个Widget建立SPW, 然后进行一次push_back
... // 使用vwp
} // 这里没有Widget泄漏，甚至不会在上面的代码中抛出异常

● 我们需要记住的所有事情就是STL容器很智能，但它们没有智能到知道是否应该删除它们所包含的指针。当你要删除指针的容器时要避免资源泄漏，你必须用智能引用计数指针对象（比如Boost的shared_ptr）来代替那些指针，或者你必须在容器销毁前手动删除容器中的每个指针。

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

auto_ptr的容器（COAPs）是禁止的；任何试图使用它们的代码都不能编译。当你拷贝一个auto_ptr时，auto_ptr所指向对象的所有权被转移到拷贝的auto_ptr，而被拷贝的源auto_ptr被设为NULL。即：拷贝一个auto_ptr将改变它的值：
auto_ptr<Widget> pw1(new Widget); // pw1指向一个Widget
auto_ptr<Widget> pw2(pw1); // pw2指向pw1的Widget; pw1被设为NULL（Widget的所有权从pw1转移到pw2）
pw1 = pw2; // pw1现在再次指向Widget；pw2被设为NULL

条款9：在删除容器的选项时仔细选择

我们有下列结论：
● 去除一个容器中有特定值的所有对象：
如果容器是vector、string或deque，使用erase-remove惯用法（参见条款32）。
如果容器是list，使用list::remove。
如果容器是标准关联容器，使用它的erase成员函数。
● 去除一个容器中满足一个特定判定式的所有对象：
如果容器是vector、string或deque，使用erase-remove_if惯用法（用法可参考erase-remove惯用法）。
如果容器是list，使用list::remove_if。
如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。
● 在循环内做某些事情（除了删除对象之外）：
如果容器是标准序列容器，写一个循环来遍历容器元素，每当调用erase时记得都用它的返回值更新你的迭代器。
如果容器是标准关联容器，写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。

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

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

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

标准C++的世界是相当保守和陈旧的。所有可执行文件都是静态链接；不存在内存映射文件和共享内存；没有窗口系统；没有网络；没有数据库；没有其他进程。当发现标准没有提到任何关于线程的东西时你不该感到惊讶。

● 当涉及到线程安全和STL容器时，你可以确定库实现允许在一个容器上的多读取者和不同容器上的多写入者。但你不能希望库消除对手工并行控制的需要，而且你完全不能依赖于任何线程支持，即你必须自己实现线程安全。

vector和string

vector和string被设计为代替大部分数组的应用。

● 要记住c++标准程序库，basic_string<>被定义为所有字符串类型的基本模板类型，而：
1. string是针对char而预定义的特化版本：namespace std { typedef basic_string<char> string; }
2. wstring是针对wchar_t而预定义的特化版本：namespace std { typedef basic_string<wchar_> wstring; }
● string与char*不同，当不预先给string定义的对象足够的空间时，系统不会在string字符串尾部自动添加''结束符。
● 存在const char* 到char*的隐式转换，也存在const char* 到string的隐式转换；但从string 转换到const char*需要使用如c_str()之类的函数。
● 若在string的搜索函数失败，其会返回std::string::npos值（其类型是string::size_type）。
● string::size_type定义的（如 string::size_type index）是不带正负号的整数类型，而任何不带正负号整型都大于0，所以当它与带正负号的类型（如int i ）比较时，i 会被自动转换为无正负号值；于是对于表达式 i >= index 当 index 为 0 时，其结果将永远为 true ；故为了保证正确性，此时需要使用 i >= static_cast<int>(index)。

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

无论何时，当发现自己需要准备动态分配一个数组（也就是，企图写“new T[...]”）时，你应该首先考虑使用一个vector或一个string。（一般来说，当T是一个字符类型的时候使用string，但vector<char>也可能是个合理的设计选择，否则使用vector。）vector和string负责管理自己的内存。当元素添加到那些容器中时它们的内存会自动增长，而当一个vector或string被销毁时，它的析构函数会自动销毁容器中的元素，回收存放那些元素的内存。

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

成员函数reserve允许你最小化必须进行的重新分配的次数，因而可以避免真分配的开销和迭代器/指针/引用失效。

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

一个string对象的大小是多少？换句话说，sizeof(string)返回什么值？string和char*指针一样大的实现很常见，也很容易找到string是char*7倍大小的string实现。

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

如果你有一个vector对象v，而你需要得到一个指向v中数据的指针，以使得它可以被当作一个数组，这时只要使用&v[0]就可以了。对于string对象s，相应的咒语是简单的s.c_str()函数。在这两种形式下，指针都被传递为指向const的指针；vector和string的数据只能传给只读取而不修改它的API。

● vector中的元素被C++标准限定为存储在连续内存中，就像是一个数组。所以，如果我们想要传递一个vector对象v给这样的C风格的API：
void doSomething(const int* pInts, size_t numInts);
一个较安全的方法是：
if (!v.empty()) {
doSomething(&v[0], v.size());
}

● string的成员函数c_str()存在的原因是，它返回一个按C风格设计的指针，指向string的值。因此如果我们想要传递一个string对象s给这个C风格的API：
void doSomething(const char *pString);
应该像以下这样使用：
doSomething(s.c_str());

● 如果你想用C风格API所返回的元素初始化一个vector，你可以利用vector和数组潜在的内存分布兼容性，将存储在vector的元素的空间传给这个API函数：
// C API：此函数需要一个指向数组的指针，数组最多有arraySize个double
// 而且会对数组写入数据。它返回写入的double数，不会大于arraySize
size_t fillArray(double *pArray, size_t arraySize);
vector<double> vd(maxNumDoubles); // 建立一个vector，它的大小是maxNumDoubles
应该像以下这样使用：
vd.resize(fillArray(&vd[0], vd.size())); // 让fillArray把数据写入vd，然后调整vd的大小为fillArray写入的元素个数

● 如果你想用来自C风格API的数据初始化string对象，也很简单。只要让API将数据放入一个vector<char>，然后从vector中将数据拷到string即可。
// C API：此函数需要一个指向数组的指针，数组最多有arraySize个char
// 而且会对数组写入数据。它返回写入的char数，不会大于arraySize
size_t fillString(char *pArray, size_t arraySize);
vector<char> vc(maxNumChars); // 建立一个vector，它的大小是maxNumChars
应该像以下这样使用：
size_t charsWritten = fillString(&vc[0], vc.size()); // 让fillString把数据写入vc
string s(vc.begin(), vc.begin()+charsWritten); // 从vc通过范围构造函数拷贝数据到s

● 事实上，让C风格API把数据放入一个vector，然后再拷到你实际想要的STL容器中的主意总是有效的。

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

● 要避免你的容器持有它不再需要的内存，你需要有一种方法来把它从曾经最大的容量减少到它现在需要的容量。这样减少容量的方法常常被称为“收缩到合适（shrink to fit）”。方法就是使用swap成员函数。

class Contestant {...};
vector<Contestant> contestants;
... // 使contestants变大，然后删除它的一些内容
vector<Contestant>(contestants).swap(contestants); // 在contestants上进行“收缩到合适”

● 另外，交换技巧的变体可以用于清除容器和减少它的容量到你的实现所提供的最小值。你可以简单地和一个默认构造的临时vector或string做个交换：
vector<Contestant> v;
string s;
... // 使用v和s
vector<Contestant>().swap(v); // 清除v而且最小化它的容量
string().swap(s); // 清除s而且最小化它的容量

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

做为一个STL容器，vector<bool>确实有两个问题：第一，它不是一个STL容器。第二，它并不容纳bool。vector<bool>其实是一个伪容器，它并不保存真正的bool，而是打包bool以节省空间。

标准库提供了两个替代品，它们能满足几乎所有需要：
● 第一个vector<bool>的替代品是deque<bool>，它保存真正的bool值。
● 第二个vector<bool>的替代品是bitset。bitset不是一个STL容器，但它是C++标准库的一部分。

关联容器

任何一种关联容器均是使用平衡二叉树构造的，关联容器缺省情况下以 operator< 对其元素比较，自动排序；当然你也可以为其制定新的排序准则。

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

当你用find来定位区间中第一个有特定值的对象的位置，find必须可以比较两个对象，看看一个的值是否与另一个相等。同样，当你尝试向set中插入一个新元素时，set::insert必须可以判断那个元素的值是否已经在set中了。

find算法和set的insert成员函数是很多必须判断两个值是否相同的函数的代表。但它们以不同的方式完成：find对“相同”的定义是相等，基于operator== ；而set::insert对“相同”的定义是等价，通常基于operator< 。

● 如果表达式“x == y”返回true，x和y就有相等的值，否则它们没有，这很直截了当。但要牢牢记住，对于类的对象，x和y有相等的值并不意味着所有它们的成员有相等的值！

● 等价一般在每种标准关联容器（比如，set、multiset、map和multimap）的一部分 —— 排序顺序方面有意义；它是基于在一个有序区间中对象值的相对位置的。

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

假定你有一个string*指针的set，你把一些动物的名字插入进set：
set<string*> ssp; // ssp = “set of string ptrs”
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));

首先，你应该回忆起
set<string*> ssp;
是
set<string*, less<string*> > ssp;
的简写。为了完全准确，它其实是
set<string*, less<string*>, allocator<string*> > ssp;
的简化。

● 如果你想要string*指针以字符串值确定顺序被储存在set中，你不能使用默认比较仿函数类less<string*>；相反，你必须改为写你自己的比较仿函数类，它的对象带有string*指针并按照指向的字符串值来进行排序。就像这样：
struct StringPtrLess:
public binary_function<const string*, const string*, bool> // 使用这个基类的理由参见（条款40）
{
bool operator()(const string *ps1, const string *ps2) const
{
return *ps1 < *ps2;
}
};
然后你可以使用StringPtrLess作为ssp的比较类型，如下：
typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp; // 建立字符串的集合，按照StringPtrLess定义的顺序排序
... // 和前面一样，插入同样四个字符串
这时，string*指针就以字符串值确定顺序被储存在set中。

● 无论何时你建立指针的关联容器时，注意你也得指定容器的比较类型。大多数时候，你的比较类型只是解引用指针并比较所指向的对象（就像上面的StringPtrLess做的那样）。鉴于这种情况，你手头最好也能有一个用于那种比较的仿函数模板，像这样：
struct DereferenceLess {
template <typename PtrType>
bool operator()(PtrType pT1, PtrType pT2) const // 参数是值传递的，因为我们希望它们是（或行为像）指针
{
return *pT1 < *pT2;
}
};
这样的模板消除了写像StringPtrLess那样的类的需要，因为我们可以改为使用DereferenceLess：
set<string*, DereferenceLess> ssp; // 行为就像 set<string*, StringPtrLess>

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

让我向你展示一些比较酷的东西。建立一个set，比较类型用less_equal，然后插入一个10：
set<int, less_equal<int> > s; // s以“<=”排序插入10
s.insert(10);
s.insert(10); //现在尝试再插入一次10

less_equal意思就是operator<=。于是，set将计算这个表达式是否为真：!(10A <= 10B) && !(10B <= 10A)，而结果当然是false(违背了我们的初衷)！因此，通过使用less_equal作为我们的比较类型，我们破坏了容器！除非你的比较函数总是为相等的值返回false，否则你将会打破所有的标准关联型容器。

● 因为相等的值绝不该一个大于另一个，所以比较函数总应该对相等的值返回false。于是，要避免掉入这个陷阱，你所要记住的就是比较函数的返回值表明的是在此函数定义的排序方式下，一个值是否大于另一个，因此你不应该参合“=”运算符进来。

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

正如所有标准关联容器一样，set和multiset保持它们的元素有序，这些容器的正确行为依赖于它们保持有序。如果你改了关联容器里的一个元素的值（例如，把10变为1000），新值可能不在正确的位置，那将破坏容器的有序性。

● set和multiset不提供用来直接存取元素的任何操作函数；而通过迭代器进行元素间接存取也有一个限制：元素值是常数，不可直接对其修改；如要修改元素只能是先erase() 后insert()。
● 要移除set和multiset中的元素，你只能使用它们提供的成员函数erase()，而不能使用remove()算法。
● 要删除某个value值对应的元素，对于set只需使用erase()；而对于multiset，你不能直接使用erase()来直接删除重复元素中的第一个元素，你应该先find()找到元素第一次出现的位置，之后再erase()。

● 在map和multimap中，你不可修改元素的key，如果你需要修改key，你必须先得用成员函数erase()移除key对应的元素，然后再insert()新元素。而元素的value值是可以直接修改的。
● 在map和multimap中，你可以使用成员函数find()来搜索拥有某个key的第一个元素所在的位置；而对于搜索拥有value值的元素，你不可使用find()，而必须修改通用算法如find_if()，或是自己写一个显示循环来实现。
● 对于map，当你需要移除“拥有某个value值”的元素时，使用这个元素对应的key，直接erase(key)即可；而对于multimap，你如果要删除重复元素中的第一个，你先得find(key)，之后使用erase(pos++)使迭代器有效，而不是erase(pos)函数。

● 在一个“key/value”对所形成的群集中，如果所有“key/value”都是独一无二的，那么我们可以将他视为一个关联式数组来使用。STL内部的map就可以，即map可是使用operator[]来操作元素。map提供的这种非常方便的方法可以用来修改元素的key值，即：先mapcoll["new_key"]=mapcoll["old_key"]; 之后mapcoll.erase["old_key"]; 而maltimap没有这个功能，必须自己实现。

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

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

如果你要更新已存在的map元素，operator[]更好；但如果你要增加一个新元素，insert则更有优势。

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

迭代器

标准STL容器提供了四种不同类型的迭代器：iterator、const_iterator、reverse_iterator和const_reverse_iterator。

任何容器都有其对应的两种类型的迭代器：container::iterator 提供“读/写”模式遍历元素；container::const_iterator 提供“只读”模式遍历元素；迭代器和指针差不多，但它不是指针；如可以使用：++operator累进，而--operator则是回退；以operator*提取所指位置的元素值等。

迭代器之适配器（Iterator Adapters）有以下三种：Insert iterators ， stream iterators ， Reverse iterators。

● Insert iterators：其可以使算法以insert的方式而非overwrite方式来运作。使用它可以解决算法的“目标空间不足”的问题，因为它会促使目标区间的大小按需求增长。
1. back_inserter，在容器尾端插入，其内部调用push_back()函数来完成插入操作。可用于：vector, deque, list三种容器。
2. front_inserter，在容器前端插入，其内部调用push_front()函数来完成插入操作。可用于：deque, list 两种容器。
3. inserter，在容器的某个位置插入，其内部调用insert()函数来完成插入操作。可用于任意的STL容器，同时也是关联容器可以使用的唯一一种Insert iterators。

● stream iterators：这是一种用来读写stream的迭代器，它们提供了必要的抽象性，使得能够获取来自键盘的输入，及将结果重定向到某个文件或是屏幕上。
1. istream_iterator：如cin
2. ostream_iterator：如cout

● Reverse iterators：逆向迭代器，其以逆向的方式对容器的元素进行操作。所有的STL容器都可以通过rbegin()和rend()函数产生Reverse iterators。

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

如果你尽量使用iterator代替const或reverse类型的迭代器，就可以使容器的使用更简单，更高效而且可以避免潜在的bug。

对于container<T>而言，iterator的作用相当于T*，而const_iterator则相当于const T*（你可能也见过T const*这样的写法：它们意思一样）。增加一个iterator或者const_iterator可以在一个从容器开头趋向尾部的遍历中让你移动到容器的下一个元素。reverse_iterator与const_reverse_iterator同样相当于对应的T*和const T*，所不同的是，增加reverse_iterator或者const_reverse_iterator会在从尾到头的遍历中让你移动到容器的下一个元素。

● 从iterator到const_iterator、从iterator到reverse_iterator和从reverse_iterator到const_reverse_iterator都可以进行隐式转换。并且，reverse_iterator可以通过调用其base成员函数转换为iterator；而const_reverse_iterator也可以类似地通过base转换成为const_iterator。

但对于一些语句，如比较表达式，若迭代器的类型不同，你的（正确的）代码可能会被（错误地）拒绝，最简单的解决方法是通过一个（安全的）映射把iterator转换为const_iterator，即使用语句：static_cast<const_iterator>(iterator)。

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

如果你得到一个const_iterator并且可以访问它所指向的容器，那么这里有一种安全的、可移植的方法来获取它所对应的iterator，下面的例子是解决思路的本质：

typedef deque<int> IntDeque; // 定义一个存放int的deque
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
IntDeque d;
ConstIter ci;
... // 让ci指向d
Iter i(d.begin()); // 初始化i为d.begin()
advance(i, distance<ConstIter>(i, ci)); // 把i移到指向ci位置；而Iter i(const_cast<Iter>(ci)); 的使用时错误的！

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

● 要实现在一个reverse_iterator ri指出的位置上插入新元素，在ri.base()指向的位置插入就行了。对于insert操作而言，ri和ri.base()是等价的，而且ri.base()真的是ri对应的iterator（即ri.base()指向ri当前位置的“下一位”）。

● 要实现在一个reverse_iterator ri指出的位置上删除元素，就应该删除ri.base()指向的前一个元素。对于删除操作而言，ri和ri.base()并不等价，而且ri.base()不是ri对应的iterator，你应该做如下类似的操作：
vector<int> v;
... // 向v插入元素
vecot<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3); // ri指向3
v.erase((++ri).base()); // 删除ri.base()指向的元素

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

● 假设我们要把一个文本文件拷贝到一个字符串对象中。一个更高效的方法是使用STL最好的秘密武器之一：istreambuf_iterators。你可以像istream_iterator一样使用istreambuf_iterator，但istream_iterator<char>对象是使用operator>>来从输入流中读取单个字符；而istreambuf_iterator<char>对象是进入流的缓冲区并直接读取下一个字符。

● 同样，你也应该考虑把ostreambuf_iterator用于相应的无格式一个一个字符输出的操作。

算法

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

STL容器在被添加时（通过insert、push_front、push_back等），其自动扩展它们自己来容纳新对象。但当程序员使用算法向容器中插入对象但并没有显式告诉STL他们所想要的行为时候，就会出现问题。故使用算法进行新对象的插入时，如下例：

在本例中，说“请把transform的结果放入叫做results容器的结尾”的方式是调用back_inserter来产生指定目标区间起点的迭代器：
vector<int> results; // 把transmogrify()函数操作应用于values中的每个对象
transform(values.begin(), values.end(), back_inserter(results),transmogrify); // 在results的结尾插入返回的values

● 在内部，back_inserter返回的迭代器会调用push_back，所以你可以在任何提供push_back的容器上使用back_inserter（也就是任何标准的序列容器：vector、string、deque和list）。
● 如果你想让一个算法在容器的前端插入东西，你可以使用front_inserter。在内部，front_inserter利用了push_front，所以front_insert只和提供那个成员函数的容器配合（也就是deque和list两个标准序列容器）。
● 有些惊人的是inserter允许你强制算法把它们的结果插入容器中的任意位置。

当你要插入的容器是vector或string时，你可以通过按照（条款14）的建议最小化这个代价，预先调用reserve。虽然你仍要承受每次发生插入时移动元素的开销，但至少你避免了重新分配容器的内在内存。

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

我们总结一下你的排序选择：
● 如果你需要在vector、string、deque或数组上进行完全排序，你可以使用sort或stable_sort。
● 如果你有一个vector、string、deque或数组，你只需要排序前n个元素，应该用partial_sort。
● 如果你有一个vector、string、deque或数组，你需要鉴别出第n个元素或你需要鉴别出最前的n个元素，而不用知道它们的顺序，nth_element是你应该注意和调用的。
● 如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准，你大概就要找partition或stable_partition。
● 如果你的数据是在list中，你可以直接使用partition和stable_partition，你可以使用list的sort来代替sort和stable_sort。

条款32：如果你真的想删除东西的话就在类似remove的算法后再接上erase

vector<int> v;
... //添加元素，其中包含了一个或是多个99
v.erase(remove(v.begin(), v.end(), 99), v.end()); // 的确删除了所有等于99的元素

STL中唯一名叫remove而又能从容器中除去元素的函数是list中的remove成员函数；因为在list容器中，remove和erase被整合到remove中了。

而在关联容器中类似的函数叫erase。

另外有两种“类似remove”的算法：remove_if和unique，同理，如果你真的要从容器中删除元素，你也必须成对调用unique和erase或是remove_if和erase。

条款33：提防在指针的容器上使用类似remove的算法

如果你把指针的容器替换成执行引用计数的智能指针的容器，相关的删除工作就不存在困难，因为你可以直接使用erase-remove惯用法。

如果在你的程序工具箱中碰巧没有一个引用计数智能指针模板，你应该从Boost库中获取shared_ptr模板。

条款34：注意哪个算法需要有序区间

● 搜索算法binary_search、lower_bound、upper_bound和equal_range 需要有序区间，因为它们使用二分法查找来搜索值。
● 算法set_union、set_intersection、set_difference和set_symmetric_difference 提供了线性时间设置它们名字
所提出的操作的性能，他们需要有序区间。
● merge和inplace_merge 执行了有效的单遍合并排序算法。它们读取两个有序区间，然后产生一个包含了两个源区间所有元素的新有序区间。
● 最后一个需要有序区间的算法是includes。它用来检测是否一个区间的所有对象也在另一个区间中。
● unique和unique_copy 甚至在无序区间上也提供了定义良好的行为，其从每个相等元素的连续组中去除第一个以外所有的元素。

条款35：通过mismatch或lexicographical比较实现简单的忽略大小写字符串比较

条款36：了解copy_if的正确实现

如果你只是简单地想要拷贝一个区间中满足某个判断式的元素，你只能自己做。以下是copy_if算法正确的实现：
template<typename InputIterator, typename OutputIterator, typename Predicate> // 一个copy_if的正确实现
OutputIterator copy_if(InputIterator begin,InputIterator end,OutputIterator destBegin,Predicate p) {
while (begin != end) {
if (p(*begin)) *destBegin++ = *begin;
++begin;
}
return destBegin;
}

函数copy_if很有用，加上新STL程序员趋向于希望无论如何它应该存在的事实，所以好的做法是把copy_if放在你局部的STL相关工具库中，而且只要合适就使用。

条款37：用accumulate或for_each来统计区间

在某些情况中，你需要统计一个区间，但你要有定义你需要统计的东西的能力。没问题，STL为你准备了那样的算法，它叫作accumulate。但它不存在于<algorithm>，取而代之的是，它和其他三个“数值算法”都在<numeric>中。（那三个其它的算法分别是inner_product、adjacent_difference和partial_sum。）

就个人来说，我更喜欢用accumulate来统计，因为我认为它最清楚地表达了正在做什么，但是for_each也可以，而且不像accumulate，副作用的问题并不跟随for_each。两个算法都能用来统计区间，如何使用看你的爱好。

仿函数、仿函数类、函数等

函数和类似函数的对象——仿函数——遍布STL，STL中的算法大量使用了这些东西（条款40、41、46）。

● 仿函数或着说函数对象是指这样一种东西，其行为表现为函数，一般是重载了operator()的函数或者类。
● 判定式就是指返回Boolean值的函数或者仿函数。在STL中通常被用来指定排序准则和搜索准则。
● 仿函数适配器是指能够将仿函数和另一个仿函数（或某个值或某个函数）结合在一起的仿函数。主要有：not1, not2, bind1st, bind2nd等。
● 函数适配器 mem_fun_ref及mem_fun是针对类成员函数而设计的函数适配器，被mem_fun_ref及mem_fun修饰的成员函数必须是const的；而ptr_fun是针对一般函数（即非类成员函数）而设计的函数适配器。
● 让自定义的仿函数（或仿函数类）也能够使用仿函数适配器则必须提供一些型别（type members）来反映其参数和返回值的类别，此时可以使自定义的仿函数派生于unary_function或binary_function结构；否则需要配合使用prt_fun、mem_fun_ref或是mem_fun才能使用仿函数适配器。
● STL中预定义的仿函数：negate<>, plus<>, minus<>, multiplies<>, divides<>, modulus<>, equal_to<>, not_equal_to<>, less<>, less_equal<>, greater<>, greater_equal<>, logical_and<>, logical_or<>, logical_not<>。它们都在<functional>中声明。

条款38：把仿函数类设计为用于值传递

C和C++都不允许你真的把函数作为参数传递给其他函数。取而代之的是，你必须传指针给函数。而STL函数对象是在函数指针之后成型的，所以STL中的习惯是当传给函数或从函数返回时函数对象是值传递的（也就是拷贝）。

当然，值传递的情况并不是完全打不破的，可以使for_each的调用者在调用点显式指定参数类型。

C++支持继承层次和动态绑定，这些特性在设计仿函数类和其他东西候一样有用，禁止多态仿函数是不切实际的。仿函数类如果缺少继承就像C++缺少“++”。的确有办法让大的和/或多态的函数对象仍然允许它们把以值传递仿函数的方式遍布STL，即使用所谓的“Bridge模式”，也称作“Pimpl惯用法”。

条款39：用纯函数做判断式

● 判断式是返回bool（或者其他可以隐式转化为bool）的东西。
● 纯函数是返回值只依赖于参数的函数，在C++中，由纯函数引用的所有数据不是作为参数传进的就是在函数生存期内是常量。
● 一个判断式类是一个仿函数类，它的operator()函数是一个判断式，也就是，它的operator()返回true或false（或其他可以隐式转换到true或false的东西）。在任何STL想要一个判断式的地方，它都会接受一个真的判断式或一个判断式类对象。（一元判定式：一般用于检查唯一参数的某项特性；二元判定式：典型的一个用途是比较两个参数的特定属性。）
● （条款38）解释了函数对象是传值，所以你应该设计可以拷贝的函数对象。

最简单的使你自己不摔跟头而进入语言陷阱的方法是在判断式类中总是把你的operator()函数声明为const。如果你这么做了，你的编译器不会让你改变任何类数据成员。最后，不管你怎么写你的判断式，它们都应该是纯函数。

条款40：使仿函数类可适配

● 我们需要仿函数类继承自unary_function或binary_function结构。因为这些类提供了函数对象可适配所需要的typedef，所以从这些类中继承就可产生可适配的函数对象。
● 如果不这样做，那么就需要ptr_fun、mem_fun和mem_fun_ref等函数的配合才能使用如 not1, not2, bind1st, bind2nd等仿函数适配器，因为仿函数适配器都是只和可适配的函数对象合作，即都需要某些typedef。
● ptr_fun唯一做的事就是使一些typedef有效；mem_fun和mem_fun_ref产生的对象不仅允许STL组件假设所有函数都使用单一的语法调用，它们也提供重要的typedef，正如ptr_fun产生的对象一样。
● operator()带一个实参的仿函数类，要继承的结构是std::unary_function，即所谓的一元仿函数；operator()带有两个实参的仿函数类，要继承的结构是std::binary_function，即所谓的二元仿函数。不要忘记给返回值为bool型的operator() 修饰为const成员函数。
● unary_function和binary_function都是模板，所以你不能直接继承它们。取而代之的是，你必须从它们产生的类继承，而这就需要你指定一些类型实参。对于unary_function，你必须指定的是由你的仿函数类的operator()所带的参数的类型和它的返回类型；对于binary_function，你要指定三个类型：你的operator的第一个和第二个参数的类型，及operator()返回的类型。
● 把仿函数声明为class还是struct可根据是否存在状态来决定，如有则使用class，否则可使用struct。
● 用于带有或返回指针的仿函数的一般规则是传给unary_function或binary_function的类型是operator()带有或返回的类型。一般来说，传给unary_function或binary_function的非指针类型都去掉了const和引用；但当operator()的参数是指针时，传给unary_function或binary_function的类型和operator()所带的类型必须一样。
● STL内部假设每个仿函数类只有一个operator()函数，而且这个函数的参数和返回类型要被传给unary_function或binary_function。

下面是两个例子：
template<typename T>
class MeetsThreshold: public std::unary_function<Widget, bool>{
private:
const T threshold;
public:
MeetsThreshold(const T& threshold);
bool operator()(const Widget&) const;
...
};

struct WidgetNameCompare:
public std::binary_function<Widget, Widget, bool>{
bool operator()(const Widget& lhs, const Widget& rhs) const;
};

上述两种情况中，传给unary_function或binary_function的类型与传给仿函数类的operator()和从那里返回的是一样的，虽然operator的返回类型作为最后一个实参被传递给unary_function或binary_function有一点古怪。

条款41：了解使用ptr_fun、mem_fun和mem_fun_ref的原因

如果我有一个函数 f 和一个类对象 x ，我希望在 x 上调用 f ，而且我在 x 的成员函数之外。C++给了我三种不同的语法来实现这个调用：
f(x); // 语法#1：当f是一个非成员函数
x.f(); // 语法#2：当f是一个成员函数而且x是一个对象或一个对象的引用
p->f(); // 语法#3：当f是一个成员函数而且p是一个对象的指针

● 现在假设我有一个可以测试Widget的函数：
void test(Widget& w); // 测试w，如果没通过就标记为“failed”

而且我有一个Widget的容器：
vector<Widget> vw; // vw容纳Widget

如果要测试vw中的每个Widget，很显然我可以按如下使用for_each来实现：
for_each(vw.begin(), vw.end(), test); // 调用#1（可以编译）
for_each(vw.begin(), vw.end(), ptr_fun(test)); // 也可以编译，行为就像上面的调用#1

● 如果test是Widget的成员函数而不是一个非成员函数，如下：
class Widget {
public:
void test(); // 进行自我测试；如果没通过就把*this标记为“failed”
};

而且我有一个Widget*的容器：
list<Widget*> lpw; // lpw容纳Widget的指针

现在要测试vw中的每个Widget*，很显然可以这么使用for_each：
for_each(lpw.begin(), lpw.end(),mem_fun(&Widget::test)); // 调用#3（可以编译）

● 完全类似，mem_fun_ref函数适配语法#2到语法#1，并产生mem_fun_ref_t类型的适配器对象：
list<Widget> lpw; // lpw容纳Widget的指针
要测试vw中的每个Widget，很显然可以这么使用for_each：
for_each(lpw.begin(), lpw.end(),mem_fun_ref(&Widget::test)); // 调用#2（可以编译）

也许现在清楚为什么mem_fun和mem_fun_ref存在了。它们让成员函数（通常必须使用句法#2或者句法#3来调用
的）使用句法#1调用。

条款42：确定less<T>表示operator<

operator< 不仅是实现less的默认方式，它还是程序员希望less做的。让less 做除operator< 以外的事情是对程序员预期的无故破坏。一般情况下，用于关联容器的比较函数不是operator< 或less，而通常是用户自定义的判断式。

如果你使用less（明确或者隐含），那么必须保证它就是表示operator< 。如果你想要使用一些其他标准来排序对象，那么就需要自己建立一个特殊的且名称不为less的仿函数类。

这里有一个例子：
struct MaxSpeedCompare:
public binary_function<Widget, Widget, bool> {
bool operator()(const Widget& lhs, const Widget& rhs) const
{
return lhs.maxSpeed() < rhs.maxSpeed();
}
};
要创造我们的multiset，我们可以使用MaxSpeedCompare作为比较类型，因此避免了默认比较类型的使用（当然也就是less<Widget>）：
multiset<Widget, MaxSpeedCompare> widgets;
代码确切地说出了它的意思：建立一个Widget的multiset，并按照仿函数类MaxSpeedCompare所定义方法排序。

对比这个：
multiset<Widget> widgets;
它表示widgets是一个以默认方式排序的Widget的multiset。在技术上，那表示它使用了less<Widget>，但是实际上每人都要假设那真的意味着它是按operator< 来排序。

使用STL编程

条款43：尽量用算法调用代替手写循环

每个算法接受至少一对用来指示将被操作的对象区间的迭代器。

事实上，调用库中给出的算法通常比我们自己手写的循环更优越；因为库中给出的算法其效率、正确性及可维护性都很高。

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

有些容器拥有和STL算法同名的成员函数。如关联容器提供的count、find、lower_bound、upper_bound及equal_range；list容器提供的remove、remove_if、unique、sort、merge及reverse。

大多数情况下，你应该用成员函数代替算法。这样做有两个理由：首先，成员函数更快；其次，比起算法来，它们与容器结合得更好（尤其是关联容器）。

条款45：注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别

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

把STL函数对象 —— 化装成函数的对象—— 传递给算法所产生的代码一般比传递真的函数更高效。

把函数对象作为算法的参数所带来的不仅是巨大的效率提升；而且在让你的代码可以编译方面，它们也更稳健。当然，真函数很有用，但是当涉及有效的STL编程时，函数对象经常更有用。

条款47：避免产生只写代码

写让人易于看懂、易于维护的代码，因为读代码读比写代码更经常，这是软件工程的真理。

条款48：总是#include适当的头文件

关于在每个标准STL相关的头文件中都有什么，这里有一个快速概要：
● 几乎所有的容器都在同名的头文件里，比如 vector在<vector>中声明，list在<list>中声明等。例外的是<set>和<map>：<set>声明了set和multiset，<map>声明了map和multimap。
● 除了四个算法外，所有的算法都在<algorithm>中声明。这四个例外算法是accumulate、inner_product、adjacent_difference 和partial_sum。这些算法在<numeric>中声明。
● 特殊的迭代器，包括istream_iterators和istreambuf_iterators，在<iterator>中声明。
● 标准仿函数（比如less<T>）和仿函数适配器（比如not1、bind2nd）在<functional>中声明。

条款49：学习破解有关STL的编译器诊断信息

条款50：让你自己熟悉有关STL的网站

下列网站应该要提升到几乎每个人最常使用的列表：
● SGI STL网站 http://www.sgi.com/tech/stl/
● STLport网站 http://www.stlport.org/
● Boost网站 http://www.boost.org/（如果访问不了，可以尝试 http://boost.sourceforge.net/）