当前位置：首页 > news >正文

2 Studying《Effective STL》

news 2025/6/4 18:12:20

0 引言

1 容器

1. 慎重选择容器类型

3. 确保容器中的对象副本正确且高效

4. 调用empty()而不是检查size()是否为0

5. 区间成员函数优先于与之对应的单元素成员函数

7. 如果容器中包含了通过new创建的指针，切记析构前将指针delete掉

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

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

2 vector和string

13. vector和string优先于动态分配的数组

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

15. 注意string实现的多样性

16. 把vector和string数据传给旧的API

17. 使用swap除去多余的容量

18. 避免使用vector＜bool＞

3 关联容器

19. 理解相等(equality)和等价(equivalence)的区别

20. 为包含指针的关联容器指定比较类型

21. 总是让比较函数在等值情况下返回false

24. 当效率重要时，请在map::operator[]与map::insert之间做出正确选择

4 迭代器

26. iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

27. 使用distance和advance将容器的const_iterator转换为iterator

28. 正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

29. 对于逐个字符的输入请考虑使用istreambuf_iterator

5 算法

30. 确保目标区间足够大(transform+inserter)

31. 了解各种排序选择(partition,stable_partition,nth_element,partial_sort,sort,stable_sort)

32. 如果确实需要删除元素，需要在remove这一类算法之后调用erase

33. 对包含指针的容器使用remove这一类算法时要特别小心

34. 要求使用排序的区间作为参数的算法

35. 通过mismatch或lexicographical_compare实现忽略大小写的字符串比较

36. 理解copy_if算法的正确实现

37. 使用accumulate进行区间统计

6 函数子类及函数

38. 遵循按值传递的原则来设计函数子类(桥接模式)

39. 确保Predicate判别式是纯函数

40. 若一个类是函数子类，则应使它可配接

41. 理解ptr_fun、mem_fun和mem_fun_ref的来由

42. 确保less＜T＞与operator＜具有相同的语义(POLA)

7 使用STL

43. 算法调用优先于手写的循环

44. 容器的成员函数优先于同名的算法

45. 正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

46. 考虑使用函数对象而不是函数作为STL算法的参数

47. 避免产生直写型(write-only)的代码

48. 总是include正确的头文件

0 引言

本书主要包含以下内容：

1 如何选择容器类型

2 关联容器

3 迭代器

4 STL算法

5 函数对象

术语：

1 容器。

标准序列容器：vector，string，deque和list；标准关联容器：set，multiset，map和multimap。

2 迭代器5类。

输入迭代器，输出迭代器，前向迭代器，双向迭代器，随机访问迭代器

3 函数对象。

所有重载了函数调用操作符(operator())的类是一个函数子类，从这些类创建的对象被称为函数对象。

函数例子：

1 typename

需要在从属形参类型名前使用typename，这样的类型被称为从属类型。

举例如下，如下函数模板将返回容器中最后一个元素是否大于第一个元素：

template<typename C>
bool lastGreaterThanFirst(const C& container)
{if (container.empty()) {return false;}typename C::const_iterator begin(container.begin());typename C::const_iterator end(container.end());return *--end > *begin;
}

const_iterator是从属类型，需要在它前面加关键字typename。

2 lhs，rhs

lhs和rhs表示"左手边"和"右手边"

left hand side

与效率有关的条款：

4. 调用empty而不是检查size()是否为0。

5. 区间成员函数优先于与之对应的单元素成员函数。

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

15. 注意string实现的多样性。

23. 考虑用排序的vector代替关联容器。

24. 当效率重要时，在map::operator[]与map::insert之间谨慎选择。

25. 熟悉非标准的散列容器hashmap。

29. 对于逐个字符的输入，考虑使用istreambuf_iterator。

31. 了解各种与排序有关的选择。

44. 容器的同名函数优先于同名算法。

46. 调用STL算法时，考虑使用函数对象而不是函数作为其参数。

1 容器

1. 慎重选择容器类型

本章讲述适用于STL容器的准则，随后几章就特定类型的容器展开论述。

注意：auto_ptr已经弃用，可用shared_ptr或unique_ptr来替换。

C++容器分类如下：

1 标准STL序列容器

vector，string，deque和list。

频繁在序列中间插入和删除操作，应使用list。

频繁在序列头部，尾部插入和删除操作，应使用deque。

2 标准STL关联容器

set，multiset，map和multimap。

3 非标准序列容器

slist，rope。第50条

4 非标准关联容器

hash_set，hash_multiset，hash_map和hash_multimap等散列容器。第25条。

5 vector<char>作为string的替代

第13条。

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

第23条。

7 几种标准的非STL容器

数组，bitset，valarray，stack，queue和priority_queue。

第16条。第18条。

引入对STL容器的一种分类方法：

1 连续内存容器

它的元素存放在一块或多块动态分配的内存中，每块内存中存有多个元素，当有新元素插入或已有元素删除时，同一内存块的其他元素向后或向前移动。提供随机访问迭代器。

标准的连续内存容器有vector，string和deque。非标准的连续内存容器有rope。

2 基于节点的容器

每一个动态分配的内存块中只存放一个元素。容器中元素的插入或删除只影响到指向节点的指针，不影响节点本省的内容。提供双向迭代器(除了slist和散列容器)。

基于节点的容器有list，slist，标准的关联容器(实现方式平衡树)，非标准的关联容器。

总结出以下建议，用于选择容器：

1 需要在容器的任意位置插入元素

选择序列容器

2 容器中的元素是排序的

避免选择散列容器

3 插入或删除元素，避免移动容器中原来的元素

避免选择了连续内存容器

4 元素的查找速度很关键

散列容器 > 排序的vector > 标准的关联容器

5 使用了引用计数的容器

string，rope

6 使迭代器，指针和引用变为无效次数最少的容器

选择基于节点的容器，这类容器的插入和删除操作不会使迭代器，指针和引用无效，除非它指向了一个正在删除的元素。

避免选择连续内存容器，这类容器的插入和删除一般会使指向该容器的迭代器，指针和引用变为无效。

3. 确保容器中的对象副本正确且高效

当向容器加入对象时(pushback等)，存入容器的是你所指定对象的副本。当从容器中取出一个对象时(front等)，你所得到的是容器中所保存对象的副本。copy in。copy out。这就是STL的工作方式。这种复制是利用对象的复制成员函数实现的。如下：

class Widget{
public:...// 复制构造函数Widget(const Widget&);// 复制赋值操作符Widget& operator=(const Widget&);...
};

当存在继承关系的情况下，复制操作会导致剥离(slice)。如果你创建了一个存放基类对象的容器，却向其中插入了派生类的对象，那么派生类对象被复制到容器时(通过基类的复制构造函数)，它所持有的派生类部分信息将会丢失：

vector<Widget> vw;
class SpecialWidget: public Widget
{...
};
SpecialWidget sw;
vw.push_back(sw);

一个简单的办法是使容器包含指针而不是对象。也就是使用Widget*的容器，而不是使用Widget的容器。

4. 调用empty()而不是检查size()是否为0

应该使用empty()形式，理由很简单：

empty()对所有的标准容器都是常数时间操作，而size()对于list耗费的是线性时间。

介绍list的拼接操作splice：

list<int> list1;
list<int> list2;
...
// 把list2中从第一个含5的节点到最后一个含10的所有节点移动到list1的末尾
// base()见第28条
list1.splice(list1.end(), list2, find(list2.begin(), list2.end(), 5),find(list2.rbegin(), list2.rend(), 10).base());

5. 区间成员函数优先于与之对应的单元素成员函数

给定v1和v2两个vector，使v1的内容和v2的后半部分内容相同，最简单的操作是：

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

上述例子两个目的：

1 assign是一个极其方便的函数，所有的标准序列容器(vector，string，deque和list)都存在

2 揭示区间成员函数优先于与之对应的单元素成员函数

(1)如果使用单元素成员函数：

vector<Widget> v1,v2;
...
v1.clear();
for (vector<Widget::const_iterator ci = v2.begin() + v2.size()/2; ci != v2.end(); ci++) {v1.push_back(*ci);
}

(2)如果使用copy算法：

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

尽管上述代码中没有循环，copy里一定有循环。

解释下插入迭代器：

back_inserter：创建一个使用push_back的迭代器
inserter：此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。
front_inserter：创建一个使用push_front的迭代器（元素总是插入到容器第一个元素之前）

list<int> lst = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
list<int> lst2 ={10}, lst3={10},lst4={10};
copy(lst.cbegin(), lst.cend(), back_inserter(lst2));
//lst2包含10,1,2,3,4,5,6,7,8,9
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));
//lst3包含1,2,3,4,5,6,7,8,9,10
copy(lst.cbegin(), lst.cend(), front_inserter(lst4));
//lst4包含9,8,7,6,5,4,3,2,1,10

注意：几乎所有通过利用插入迭代器的方式来限定目标区间的copy调用，都应该被替换为对区间成员函数的调用。即可以改写为如下：

// 插入到v1.end()前
v1.insert(v1.end(), v2.begin() + v2.size()/2, v2.end());
// 或
v1.assign(v2.begin() + v2.size()/2, v2.end());

下面我们以vector的insert函数分析下区间成员函数优于单元素成员函数的三个方面，string，deque和list大致同理：

1 vector

先看下insert函数的声明：

// 单元素成员函数
Iterator insert( iterator loc, const TYPE &val );
// 区间成员函数
void insert( iterator loc, input_iterator start, input_iterator end );

vector v = {1， 2 ，3};

(1)不必要的函数调用

10个元素逐个插入到v中，会调用10次单元素insert；区间的话只1次。

(2)不必要的内存复制

10个元素逐个插入到v中，会调用10次拷贝；区间的话只1次。

(3)不必要的内存分配

插入num个元素最多可导致log2(num)次新的内存分配。即1000个元素插入可能导致10次新的内存分配；区间插入的话，插入前提前知道需要分配的内存，只分配1次即可。

2 string

同vector。

3 deque

(1)不必要的函数调用

(2)不必要的内存复制

4 list

(1)不必要的函数调用

(2)不必要的对list中某些节点的next和prev指针的赋值操作

区间函数一次修改next和prev即可。

最后，总结下容器中哪些函数支持区间：

1 区间创建

所有的标准容器都提供了区间构造函数：

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

2 区间插入

标准序列容器提供如下形式的insert：

void container::insert(iterator position, InputIterator begin, InputIterator end);

关联容器的insert：

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

在寻找区间形式的insert来代替单元素版本时，不要忘记单元素版本的变体。如，push_front或push_back，front_inserter或back_inserter被作为参数传递给的copy函数。

3 区间删除

标准序列容器提供如下形式的erase：

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

关联容器的erase：

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

4 区间赋值

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

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

7. 如果容器中包含了通过new创建的指针，切记析构前将指针delete掉

下面的代码会导致资源泄漏：

void doSomething()
{vector<Widget*> vwp;for (int i=0; i<NUMBER; i++) {vwp.push_back(new Widget);}...
} //Widget泄漏

你希望它们被删除：

void doSomething()
{...for (vector<Widget*>::iterator i = vwp.begin(); i!=vwp.end(); i++) {delete *i;}
}

正常情况下是能删除的，但是这段代码不是异常安全的，如果中间过程有异常抛出，同样会资源泄漏。

最简单的解决方式是用智能指针容器代替指针容器：

void doSomething
{typedef boost::shared_ptr<Widget> spw;    //指向Widget的shared_ptrvector<spw> vwp;for (int i=0; i<NUMBER; i++) {vwp.push_back(spw(new Widget));}...
} // 不会资源泄漏

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

1 删除容器中的指定元素

假定STL容器c，需要删除c中所有值为1963的元素。

Container<int> c;

注意，完成这一任务的方法随容器类型而异。

(1) 连续内存容器vector，deque或string

使用erase-remove习惯用法：

// remove移动指定区间中的元素知道所有"不删除"的元素在区间的开头
c.erase(remove(c.begin(), c.end(), 1963), c.end());

(2) list

c.remove(1963);

(3) 标准关联容器set，multiset，map或multimap

c.erase(1963);

时间复杂度对数时间。序列容器基于remove的方法，时间复杂度线性时间。

2 删除指定判别式返回true的每一个对象

判别式：

bool badValue(int x);

(1) 连续内存容器vector，deque或string

// remove移动指定区间中的元素知道所有"不删除"的元素在区间的开头
c.erase(remove_if(c.begin(), c.end(), badValue), c.end());

(2) list

c.remove_if(badValue);

(3) 标准关联容器set，multiset，map或multimap

[1] 简单但效率较低的方法

利用remove_copy_if把我们需要的值复制到一个新容器中，然后把新容器和原来容器中的内容交换：

AssocContainer<int> c;
...
// 保存不被删除的值的临时容器
AssocContainer<int> goodValues;
// 把不被删除的值从c复制到goodValues中
remove_copy_if(c.begin(), c.end(), inserter(goodValues, goodValues.end()), badValue);
// 交换c和goodValues
c.swap(goodValues);

这种方法的缺点是需要复制所有不被删除的元素。

[2] 直接从原始容器中删除元素，提高效率

因为关联容器没有提供类似remove_if的成员函数，所以我们必须写一个循环来遍历c中的元素，并在遍历过程中删除元素。

很多程序员首先想到的是：

AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); i!=c.end(); ++i) {if (badValue(*i)) {c.erase(i);}
}

上述代码有bug，会导致不确定的行为。当容器中的一个元素被删除时，指向该元素的所有迭代器都将变得无效。一旦c.erase(i)返回，i就成为无效值。

为了避免这个问题，我们要确保在调用erase之前，有一个迭代器指向c中的下一个元素。最简单的办法是，调用时对i使用后缀递增：

AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); i!= c.end(); ) {if (badValue(*i)) {c.erase(i++);} else {++i;}
}

表达式i++的值是i的旧值，作为副作用，i被递增。我们把旧的i传给erase，在erase开始执行前递增了i，i是有效的。

3 不仅要删除使badValue返回true的元素，还要在每次删除元素时向日志写一条信息

(1) 标准关联容器set，multiset，map或multimap

比较简单，仅需要对刚才的循环做简单的修改：

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，deque或string

不能再使用erase-remove用法，因为没办法用erase或remove向日志文件写信息。

不能使用类似关联容器的循环，因为对于连续内存容器，调用erase不仅会使指向被删除元素的迭代器无效，也会使被删除元素之后的所有迭代器失效。

对于连续内存容器，要利用erase的返回值，erase的返回值指向紧随被删除元素的下一个元素的有效迭代器。

for (SeqContainer<int>::iterator i = c.begin(); i != c.end();) {if (badValue(*i)) {logFile << "Erasing " << *i << "\n";// erase的返回值赋值给i,使i有效i = c.erase(i);} else {++i;}
}

(3) list

惯例是对list采取和连续内存容器相同的方式

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

allocator<T>是STL默认的内存管理器。用法举两个例子，如下：

1 在一块共享内存中存放一个或多个容器，使得多个进程可以共享这些容器

创建共享内存的堆接口：

void* mallocShared(size_t bytesNeeded);
void* freeShared(void* ptr);

我们想把STL容器的内容放到这块共享内存中。

template<typename T>
class SharedMemoryAllocator {
public:...pointer allocate(size_type numObjects, const void *localityHint = 0) {return static_cast<pointer>(mallocShared<numObjects * sizeof(T)>);}void deallocate(pointer ptrToMemory, size_type numObjects) {freeShared(ptrToMemory);}
};

标准C++，一个类型为T的对象，它的默认分配子(allocator<T>)提供了两个类型定义，分别为allocator<T>::pointer和allocator<T>::reference。

可以这样来使用SharedMemoryAllocator：

// 即vector<double>,只是自定义了分配子
typedef vector<double, SharedMemomryAllocator<double>> SharedDoubleVec;
{...SharedDoubleVec v;v.push_back(1.1);...
}

v的元素内容来自共享内存。而v只是栈对象，不会位于共享内存中。注意，vector模板类的声明如下：

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >class vector : protected _Vector_base<_Tp, _Alloc>

有两个模板参数，_Tp 是元素类型， _Alloc 负责提供 vector 需要用到的动态内存。其中 _Alloc 参数有默认值，一般的使用（如int， float等）不需要指定这个参数。但对内存有特殊需求，就需要提供自己定义的内存管理类。

为了把v的元素内容和v都放到共享内存中，需要这么做：

// 1 分配共享内存
void* pVectorMemory = mallocShared(sizeof(SharedDoubleVec));
// 2 "placement new",构造SharedDoubleVec对象
SharedDoubleVec *pv = new(pVectorMemory) SharedDoubleVec;
pv->push_back(1.1);
...
// 3 析构SharedDoubleVec对象
pv->~SharedDoubleVec();
// 4 释放共享内存
freeShared(pVectorMemory);

即四部曲：分配、构造、析构、释放(allocate/construct/destroy/deallocate)。

2 控制STL容器分配的堆内存

假设有两个堆，分别为Heap1和Heap2：

class Heap1 {
public:...static void* alloc(size_t numBytes, const void* memoryBlockToBeNear);static void dealloc(void *ptr);
};class Heap2 {...
};

我们想把STL容器的内容放在不同的堆中，需要自定义分配子：

template<typename T, typename Heap>
class SpecificHeapAllocator {
public:...pointer allocate(size_type numObjects, const void* localityHint = 0) {return static_cast<pointer>(Heap::alloc(numObjects * sizeof(T)), localityHint);}void deallocate(pointer ptrToMemory, size_type numObjects) {Heap::dealloc(ptrToMemory);}
}

使用SpecificHeapAllocator分配子的STL容器：

// v和s的元素存放在Heap1中
// 1
vector<int, SpecificHeapAllocator<int, Heap1>> v;    
// 2
set<int, SpecificHeapAllocator<int, Heap1>> s;       // l和m的元素存放在Heap2中
// 3
list<Widget, SpecificHeapAllocator<Widget, Heap2>> l;     
// 4
map<int, string, less<int>, SpecificHeapAllocator<pair<const int, string>, Heap2>> m;

set，list类模板类似vector类模板，不赘述。map类模板如下：

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compareclass Alloc = allocator<pair<const Key,T> >    // map::allocator_type> class map;

在map内部，元素总是按照其键Key进行排序的，排序时使用其内部比较对象（Compare）并遵循指定的严格弱序准则。

1,2=>不同的STL容器存放在同一个堆Heap1中；1,3=>不同的STL容器存放在不同的堆中。即，默认情况下，vector使用默认的分配子分配堆内存，我们无法控制容器在哪段内存里构建；使用了自定义分配子后，可控制堆内存了。

2 vector和string

13. vector和string优先于动态分配的数组

当你决定用new来动态分配内存时，注意以下几点：

1 确保只有会delete。

2 确保使用正确的delete形式。

单个对象delete；数组，多个对象delete[]。

3 确保只delete了一次。

vector和string能自己管理内存，当元素被加入到容器中时，它们的内存会增长；当vector或string被析构时，它们的析构函数会自动析构容器中的元素并释放包含这些元素的内存。每当要动态分配一个数组时(new T[])，应考虑使用vector和string来替换。

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

对于vector和string，每当需要更多空间时，调用与realloc类似的操作：

1 分配一块大小为当前容量的某个倍数的新内存。

2 把容器的所有元素从旧的内存复制到新的内存中。

3 析构掉旧内存中的对象。

4 释放旧内存。

每当这些步骤发生时，vector或string中的所有指针、迭代器和引用都将变得无效。reserve函数能使你把重新分配的次数减少到最低，从而避免了指针、迭代器、引用失效带来的开销。

vector和string提供了如下4个函数：

1 size()，表示容器中有多少个元素，不会告诉容器分配了多少内存。

2 capacity()，表示容器能容纳的元素总数，如果你想知道容器还有多少没有使用的内存，需要capacity()减去size()。

3 resize(Container::size_type n)，强迫容器改变到包含n个元素的状态。如果n比当前size小，则容器尾部元素会被析构；如果n比当前size大，则会通过默认构造函数创建的新元素将被添加到容器的末尾；如果n比当前capacity大，在添加元素之前，需要重新分配内存。

4 reserver(Container::size_type n)，强迫容器将它的容量变为至少是n，前提是n不小于当前size。

一般用法是容器刚被构造出来时使用reserve：

vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; i++) {v.push_back(i);
}

15. 注意string实现的多样性

sizeof(string)的返回值是多少?如果你很关心内存的使用情况，这会是一个很重要的问题。

我们需要知道一个string对象可能会存储哪些数据，以及它可能会把这些数据存储在什么地方。

几乎每个string的实现都包含如下信息：

(1) 字符串的大小size，即包含的字符数。

(2) 用于存储字符串中字符内存的容量capacity。

(3) 字符串的值value，即字符串的字符。

除此之外，string还可能包含:

(1) 分配子

(2) 对值的引用计数

这里将展示4种不同的string实现。

1 实现A

todo

图1 实现A

实现A中每个string对象包含allocator分配子，大小size，容量capacity和一个指针。该指针指向一块动态内存，其中包含了引用计数和字符串的值value。

若使用默认分配子，则string对象大小是一个指针的4倍；若使用自定义分配子，则string对象会更大一些。

2 实现B

todo

图2 实现B

string对象大小是一个指针。

string所指的对象包含字符串大小size，容量capacity，引用计数，指针（动态分配内存，内存中存放字符串的值value）和其他(多线程有关)。

3 实现C

todo

图3 实现C

string对象大小是一个指针。

string所指的对象包含字符串大小size，容量capacity，引用计数，字符串值value和其他（共享有关）。

4 实现D

todo

图4 实现D

若使用默认分配子，string对象大小是指针大小的7倍。

string对象包含分配子allocator，“值”，大小size和容量capacity。其中，“值”占16个字节（相当于4个指针大小），可以容纳15个字符。当字符数小于15时无需动态分配内存，当字符数大于15时需要动态分配内存。

对于string s("xxxxx");

在实现D中将不会动态分配内存，A和C中动态分配一次内存，B中需要动态分配两次内存。

16. 把vector和string数据传给旧的API

对于vector v，你需要得到一个指向v中数据的指针，从而可以吧v中的数据作为数组来对待，只需要&v[0]即可；对于string s，对应形式是s.c_str()。

1 STL容器元素初始化C API

(1)vector容器

vector<int> v = {1, 2, 3};void doSomething(const int* pInts, size_t numInts) {for (int i = 0;i < numInts; i++) {cout << pInts[i] << endl;}
}int main()
{if (!v.empty()) {doSomething(&v[0], v.size());}return 0;
}

(2)string容器

string str = "xxxxx";void doSomething(const char* pStr) {cout << pStr << endl;
}int main() {doSomething(str.c_str());return 0;
}

(3)其他STL容器

set<int> intSet = {1, 2, 3};
vector<int> v(intSet.begin(), intSet.end());void doSomething(const int* pInts, size_t numInts) {for (int i = 0;i < numInts; i++) {cout << pInts[i] << endl;}
}int main()
{if (!v.empty()) {doSomething(&v[0], v.size());}return 0;
}

2 C API元素初始化STL容器

(1)vector容器

size_t fillArray(double* pArray, size_t arraySize) {for (int i=0;i < arraySize; i++) {pArray[i] = 0.7;}return arraySize;
}vector<double> vd(maxNumDoubles);
// 使用fillArray向vd中写入数据，然后把vd的大小改为写入的元素个数
vd.resize(fillArray(&vd[0], vd.size()));

(2)string容器

思路是先将C API的数据写到vector<char>中，再将数据从vector<char>中复制到string中。

size_t fillString(char* pArray, size_t arraySize) {for (int i = 0;i < arraySize; i++) {pArray[i] = 'c';}return arraySize;
}vector<char> vc(maxNumChars);
size_t charsWritten = fillString(&vc[0], vc.size());
string s(vc.begin(), vc.begin() + charsWritten);

(3)其他STL容器

思路一样，先将C API的数据写到vector中，再将数据从vector中复制到STL容器中。

size_t fillArray(double* pArray, size_t arraySize) {for (int i=0;i < arraySize; i++) {pArray[i] = 0.7;}return arraySize;
}vector<double> vd(maxNumDoubles);
// 使用fillArray向vd中写入数据，然后把vd的大小改为写入的元素个数
vd.resize(fillArray(&vd[0], vd.size()));deque<double> d(vd.begin(), vd.end());
list<double> l(vd.begin(), vd.end());
set<double> s(vd.begin(), vd.end());

17. 使用swap除去多余的容量

我们需要一种方法能把容器的容量从之前的最大值缩减为当前需要的数量，这种对容量的缩减被称为"shrink to fit"。先看代码实现：

vector<int> vi;
...// 从vi中除去多余的容量
vector<int>(vi).swap(vi);

表达式vector<int>(vi)创建一个临时变量，它是vi的副本，是由vector的复制构造函数来完成的。

注意，vector的复制构造函数只为所复制的元素分配需要的内存，所以临时变量没有多余的变量。

然后把vector<int>(vi)和vi做swap操作，就达到了除去多余容量的目的。

对于string也适用：

string s;// 让s变大，然后删除它的大部分字符
......string(s).swap(s)

类似地，swap可以用来清除一个容器，使得其容量减少。只要与一个用默认构造函数创建的vector或string做swap操作就可以了：

vector<int> v;
string s;
...
// 清除v并把它的容量变为最小
vector<int>().swap(v);
// 清除s并把它的容量变为最小
string().swap(s);

18. 避免使用vector＜bool＞

vector<bool>不是STL容器，它并不存储bool。

vector<bool> v;
bool *pb = &v[0];

上面代码不能编译，vecor<bool>是一个假的容器，存储的不是bool，而是一个二进制位。

原因再介绍下，vector<bool>::operator[]返回一个对象，这个对象指向单个位的引用，即所谓的代理对象。vector<bool>看起来像这样：

template<typename Allocator>
vector<bool, Allocator> {
pubilc:class reference {...};reference operator[](size_type n);...
};

再看之前代码编译不能通过，原因是&v[0]的类型是reference*类型不是bool*类型。

那为什么还会出现vector<bool>呢?说是做了实验，想要通过代理来存取其元素，最后实验失败了...

那么替代vector<bool>的方案有什么?

1 deque<bool>

是一个STL容器，存储的是bool。注意，内存不是连续的，所以不能把deque<bool>的数据传递给C API。

2 bitset

3 关联容器

19. 理解相等(equality)和等价(equivalence)的区别

STL容器有很多函数需要确定两个值是否相同，这些函数是以不同方式来判断两个值是否相同。

find对相同的定义是相等，是以operator==为基础的。

set::insert对相同的定义是等价，是以operator<为基础的。

相等的概念是基于opetator==的，但应该记住，x和y有相等的值不一定意味着它们的所有数据成员都有相等的值。如下举例：

class Widget {
public:...
private:TimeStamp last;...
};bool operator==(const Widget& lhs, const Widget& rhs)
{// 忽略last成员的比较
}

这种情况下，两个Widget即使有不同的last成员，它们也是相同的。

等价的概念是基于operator<的，对于两个对象x和y，如果按照关联容器的排序，每个都不在另一个前面，那么称这两个对象按照关联容器的排列顺序等价。例如set的operator <:

!(w1 < w2) && !(w2 < w1)

两个值中任何一个都不在另一个前面，则这两个值是等价的。

那么，为什么标准关联容器是基于等价而不是相等的呢?因为标准关联容器是保持排列顺序的，所以每个容器必须有一个比较函数(默认less)来决定保持怎样的顺序。

注意，对于非标准的基于散列表的关联容器，有两种常见设计，一种基于相等的，一种基于等价的。

20. 为包含指针的关联容器指定比较类型

假定有一个包含string*的set，打印集合内容，期望看到这些字符串是以字母顺序出现的：

set<string*> ssp;
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lenur"));
ssp.insert(new string("Penguin"));for (set<string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i) {cout << *i << endl;
}

你期望看到Anteater，Lenur，Penguin。实际上，你看到的是4个十六进制数，它们是指针的值。因为集合中包含的是指针，所以*i不是string，是指向string的指针。改为**i：

for (set<string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i) {cout << **i << endl;
}

ssp会按照顺序保存string*的内容，因为包含的是指针，所以会按照指针的值进行排序，而不是按照字符串的值。4个指针共有24种可能的排列方式，且每种排列出现的概率是不同的。

为了解决这个问题，请记住：

set<string*> ssp;

是下面的缩写!

set<string*, less<string*>, allocator<string*>> ssp;

分配子与本条无关，不考虑。重点看less<string*>。

如果你想让string*指针在集合中按照字符串的值排序，那么不能使用默认的比较函数子类(functor class)less<string*>，应该自定义比较函数子类。

1 自定义比较函数子类

// binary_function见第40条
struct StringPtrLess: public binary_function<const string*, const string*, bool> {bool operator(const string *ps1, const string *ps2) const{return *ps1 < *ps2;}
};typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp;
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lenur"));
ssp.insert(new string("Penguin"));for (StringPtrSet::const_iterator i = ssp.begin(); i != ssp.end(); ++i) {cout << **i << endl;
}

打印正常。

2 通用的解指针引用比较函数子类

与transform和ostream_iterator一起使用

// 入参const T*，返回const T&
struct Dereference {template<typename T>const T& operator()(const T *ptr) const {return *ptr;} 
};// 通过解指针引用，转换ssp中的每个元素，并把结果写到cout中
transform(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"),Dereference);

每当你要创建包含指针的关联容器时，一定要记住，容器将会按照指针的值进行排序。大多数情况下，这不是你所期望的，所以你肯定要自定义比较函数子类。

那为什么不简单地写个比较函数呢?

bool StringPtrLess(const string *ps1, const string *ps2)
{return *ps1 < *ps2;
}
// 编译错误
set<string, stringPtrLess> ssp;

因为set模板的参数是类型不是函数，所以编译错误。

3 比较函数子模板

struct DereferenceLess {template<typename PtrType>bool operator(PtrType pT1, PtrType pT2) const{return *pT1 < *pT2;}
};
set<string*, DereferenceLess> ssp;

这样的模板使得我们不必编写像StringPtrLess这样的类。

21. 总是让比较函数在等值情况下返回false

来看一个有趣的现象。创建一个set，用less_equal作为它的比较类型，然后把10插入到该集合中，再插入10：

// s用"<="来排序
set<int, less_equal<int>> s;
// 插入10
s.insert(10);
// 再插入10
s.insert(10);

less_equal意味着operator<=：

// 检查10A和10B的等价性
!(10A <= 10B) && !(10B <= 10A)

false && false，返回false。表示10A和10B是不等价的，所以比较类型如果采用less_equal，那么后果是set集合中有两个10。即采用less_equal的比较类型破坏了set容器!

你只要记住，比较函数的返回值表明的是按照该函数定义的排列顺序，一个值是否应该在另一个之前。相等的值从来不会有前后顺序关系，所以对于相等的值，比较函数应当始终返回false。

你可能在想，对于set和map确实是这样，因为set和map不能包含重复的值。但对于multiset和multimap呢?这些容器可以包含重复的值，它可以吧这两个值都保存起来，没问题，对吗?举例说明：

// s用"<="来排序
multiset<int, less_equal<int>> s;
s.insert(10);
s.insert(10);

我们期望对它做equal_range操作，我们将得到一对迭代器，它们定义了一个包含这两个值的区间。但实际情况是，equal_range并不是指定一个包含相等值的区间，而是指定一个包含等价值的区间。

所以，结论就是：除非你的比较函数对相等的值总是返回false，否则你会破坏所有的标准关联容器，不管它们是否允许存储重复的值。

24. 当效率重要时，请在map::operator[]与map::insert之间做出正确选择

假定我们有一个Widget类，它支持默认构造函数，并根据一个double值来构造和赋值：

class Widget {
public:Widget();Widget(double weight);Widget& operator=(double weight);...
};// 初始化
map<int, Widght> m;
m[1] = 1.50;

map::operator[]的设计目的是为了提供添加和更新的功能。即对于map<K,V> m;表达式m[k]=v;的意思是：检查键k是否已经在map中了。如果没在，就加入，并以v作为相应的值；如果在，则更新值为v。

1 添加

m[1] = 1.50在功能上等同于：

typedef map<int, Widget> IntWidgetMap;
pair<IntWidgetMap::iterator, bool> result = m.insert(IntWidgetMap::value_type(1, Widget()));
result.first->second = 1.50;

换成对insert的直接调用：

m.insert(IntWidgetMap::value_type(1, 1.50));

可以看出，使用map::insert代替map::operator[]节省了3个函数调用：

(1) 默认构造临时Widget对象

(2) 析构该临时对象

(3) 调用Widget的赋值操作符(m[1] = 1.50)

这些函数调用的代价越高，节省的开销越大。

2 更新

情况与添加相反

// operator[]
m[k] = v;
// insert
m.insert(IntWidgetMap::value_type(k, v)).first->second = v;

insert调用需要IntWidgetMap::value_type类型的参数(即pair<int, Widget>)，当我们调用insert时，必须构造和析构pair和Widget。而operator[]不使用pair<int, Widget>，没有这些开销。

所以，结论就是：当向map中添加元素时优先使用insert；当向map中更新元素时优先使用operator[]。

4 迭代器

26. iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

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

对容器类container<T>来说，iterator类型相当于T*，而const_iterator相当于const T*。reverse_iterator与const_reverse_iterator同样对应于T*和const T*，对这两个迭代器进行递增的效果是由容器尾部反向遍历到容器头部。

先看两点说明。

1 vector<T>容器中insert和erase函数原型：

iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);

每个标准容器都提供了类似的函数，只不过对于不同的容器，返回值有所不同。

注意：这些函数仅接受iterator类型的参数。

2 下图清晰地表明了不同类型的迭代器之间的转换关系：

todo

(1)从iterator到const iterator，或从iterator到reverse_iterator，或从reverse_iterator到const_reverse_iterator之间都存在隐式转换。

(2)通过调用reverse_iterator的base成员函数，可以将reverse_iterator转换为iterator。类似地，通过调用const_reverse_iterator的base成员函数，可以将const_reverse_iterator转换为const_iterator。

注意：通过base()得到的迭代器可能不是你所期望的迭代器。(见28条)

(3)图中没有办法从const_iterator转换到iterator，也无法从const_reverse_iterator转换到reverse_iterator。

总结应尽可能使用iterator的原因：

1 有些版本的insert和erase要求使用interator。

2 隐式地将一个const_iterator转换为iterator是不行的，27条将const_iterator转换为iterator的技术并不普遍适用。

3 从reverse_iterator转换来的iterator在使用之前可能需要相应的调整。

27. 使用distance和advance将容器的const_iterator转换为iterator

你可能在想使用强制类型转换，让我们看看强制类型转换如何，下面试图将const_iterator转换为iterator：

typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;ConstIter ci;
...
// 编译错误，从const_iterator到iterator没有隐式转换
Iter i(ci);
// 编译错误，不能将const_iterator强制转换为iterator
Iter i(const_cast<iter>(ci));

编译错误的原因是，对于这些容器类型，iterator和const_iterator是完全不同的类，试图将一种类型转换为另一种类型是无意义的。当然，reinterpret_cast、static_cast或C语言类型转换也会错误。

有一种方法可以将const_iterator转换为iterator，下面代码需要稍作修改才能通过编译：

注意：这里介绍的方法对使用了引用计数的string可能无效。

typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;IntDeque d;
ConstIter ci;
// 使ci指向d的某个位置
// ci = d.begin() + offset;
...
// 使i指向d的起始位置
Iter i(d.begin());
// 移动i,使它指向ci所指的位置
advance(i, distance(i, ci));

思路：为了得到一个与const_iterator指向同一位置的iterator，首先创建一个新的iterator，将它指向容器的起始位置，然后取得const_iterator距离容器起始位置的偏移量，并将iterator向前移动相同的偏移量即可。两个函数模板，distance用来获得两个迭代器之间的距离，advance用来将一个迭代器移动指定的距离。

来看下编译失败的原因，先看下distance的函数声明：

template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator, InputIterator);

distance的第1个参数和第2个参数的类型相同，而当我们如下调用时：

// 移动i,使它指向ci所指的位置
advance(i, distance(i, ci));

对编译器而言，第一个参数推断出来的类型为deque<int>::iterator，第二个参数推断出来的类型为deque<int>::const_iterator。两者类型不一致，所以编译报错。要想顺利通过编译，需要排除二义性：

// 将（i, ci）都当做const_iterator
// iterator转换为const_iterator是隐式转换
advance(i, distance<ConstIter>(i, ci));

28. 正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

先来看下面这段代码，它把数值1到5放进一个vector中，然后将一个reverse_iterator指向数值3，并且通过其base()函数初始化一个iterator：

vector<int> v;
v.reserve(5);
// 插入1到5
for (int i = 1;i <= 5; ++i) {v.push_back(i);
}
// 使ri指向3
vector<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3);
// 使i与ri的base()相同
vector<int>::iterator i(ri.base());

执行上述代码后，vector和相应迭代器的状态如下图所示：

todo

如图所示，在reverse_iterator与由base()产生的iterator之间存在偏移。

vector的insert函数仅接受iterator作为迭代器参数，不接受reverse_iterator作为参数。erase也一样。

1 插入元素

假如我们要在ri所指定的位置上插入一个新的元素到v中，假设插入元素的值99。

v.insert(i, 99);

注意，上图中ri遍历vector的顺序是自右向左，而insert操作会将新元素插入到其参数所指定的位置的元素的前面，我们期望插入99后，布局如下：

todo

在插入元素前，ri指向元素3，而通过base()得到的i指向元素4。考虑到insert与遍历方向的关系，直接使用i进行insert操作，其结果与用ri来指定插入位置得到的结果完全相同。

结论：如果要在一个reverse_iterator ri指定的位置上插入新元素，则只需在ri.base()位置处插入元素即可。即对于插入操作而言，ri和ri.base()是等价的。

2 删除元素

先回顾下在最初的矢量中，ri与i的关系：

todo

如果要删除ri所指的元素，不能直接使用i了，因为i与ri分别指向不同的位置，你必须删除i前面的元素。

结论：如果要在一个reverse_iterator ri指定的位置上删除一个元素，则需要在ri.base()前面的位置上执行删除操作。对于删除操作而言，ri和ri.base()是不等价的。

来看这样一个删除操作的实际代码：

vector<int> v;
// 插入1到5
...
// ri指向3
vector<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3);
// 试图删除ri.base()前面位置的元素；对于vector，编译不过
v.erase(--ri.base());

表达式--ri.base()确实指出了我们希望删除的元素。对于除了vector和string的标准容器，这段代码可以正常工作；对于vector和string，很可能无法通过编译，因为有些vector和string的实现中iterator是以内置指针的方式来实现的，即ri.base()的结果是一个指针。一般来说，C和C++里从函数返回的指针不应该被修改，类似--ri.base()的表达式无法通过编译。

换个更通用性的解法，先递增reverse_iterator，然后再调用base()函数即可：

...
v.erase((++ri).base());

这种方法对所有的标准容器都适用。

29. 对于逐个字符的输入请考虑使用istreambuf_iterator

假如我们想把一个文本文件的内容复制到一个string对象中：

ifstream inputFile("xxx.txt");
// 不正确
string fileData(istream_iterator<char>(inputFile), istream_iterator<char>());

这段代码并没有把文件中的空白字符复制到string对象中。因为istream_iterator使用operator>>函数来完成实际的读操作，而默认情况下operator>>函数会跳过空白字符。

如果希望保留空白字符，需要清除输入流的skipws标志：

ifstream inputFile("xxx.txt");
inputFile.unsetf(ios::skipws);
string fileData(istream_iterator<char>(inputFile), istream_iterator<char>());

现在，inputFile中的所有字符会被复制到fileData中。

但是这种方法效率较低，有一种更有效的方法，使用istreambuf_iterator。istream_iterator<char>对象使用operator>>从输入流中读取单个字符，而istreambuf_iterator<char>直接从流的缓冲区读取下一个字符。

ifstream inputFile("xxx.txt");
string fileData(istreambuf_iterator<char>(inputFile), istreambuf_iterator<char>());

对于非格式化的逐个字符输入过程，总是应该考虑使用istreambuf_iterator。对于非格式化的逐个字符输出过程，总是应该考虑使用ostreambuf_iterator。

5 算法

30. 确保目标区间足够大(transform+inserter)

事实上，STL只有8个容器类，却包含超过100个算法。

当新对象被添加进容器时，STL容器会自动扩容。但是，当程序员未能选用正确的方法来添加元素时，问题就来了。

1 假如我们想把value中的全部元素以新元素的形式插入到results末尾

// 根据x生成一个新的值
int transmogrify(int x);
vector<int> values;
// values中存入一些值
...
vector<int> results;
// 将transmogrify作用在values的每个对象上，并把返回值追加在results的末尾
transform(values.begin(), values.end(), results.end(), transmogrify);

transfrom的任务是对values的每个元素调用transmogrify，并且将结果写到从results.end()开始的目标区间中，因为在*result.end()中没有对象，这种transform调用是错误的，它导致了对无效对象的赋值操作。

正确的做法是通过调用back_inserter生成一个迭代器来指定目标区间的起始位置：

vector<int> results;
// 将transmogrify作用在values的每个对象上，并把返回值追加在results的末尾
transform(values.begin(), values.end(), back_inserter(results), transmogrify);

back_inserter返回的迭代器将使得push_back被调用，适用于所有提供了push_back方法的容器(所有的标准容器：vector,string,deque和list)。

如果需要在容器的头部插入元素，则可以使用front_inserter。front_inserter是调用push_front。

// vector没有提供push_front方法
list<int> results;
// 将transform的结果以逆向顺序插入到results的头部
transform(values.begin(), values.end(), front_inserter(results), transmogrify);

如果你希望transform把输出结果存放在results的前端，同时保留它们在values中原有的顺序，只需要按照相反顺序遍历values即可：

// vector没有提供push_front方法
list<int> results;
// 将transform的结果以逆向顺序插入到results的头部
transform(values.rbegin(), values.rend(), front_inserter(results), transmogrify);

可以看出，front_inserter将结果插入到容器的头部，back_inserter将结果插入到容器的尾部，inserter用于将算法的结果插入到容器中的特定位置：

// 在调用transform之前，先在results中加入了一些数据
vector<int> results;
// 将transform的结果插入到results容器的中间位置
transform(values.rbegin(), values.rend(), inserter(results, results.begin() + results.size()/2), transmogrify);

2 有时只是希望简单地覆盖容器中已有的元素，而不是插入新的元素

假如希望transform覆盖results容器中已有的元素，就需要确保results中已有的元素至少和values中的元素一样多。否则，必须使用resize来保证这一点。

vector<int> values;
vector<int> results;
...
// 确保results大小至少和values大小一样大
if (results.size() < values.size()) {results.resize(values.size());
}
// 覆盖results中前values.size()个元素
transform(values.begin(), values.end(),results.begin(),transmogrify);

31. 了解各种排序选择(partition,stable_partition,nth_element,partial_sort,sort,stable_sort)

1 完全排序sort

排序首先想到的是sort，但它并非在任何场合都是完美的，因为有时你不需要一个完全的排序。

2 部分排序partial_sort

如果你有一个存放Widget的vector，你需要将质量最好的20个Widget送给最重要的客户，那么只需排序出前20个Widget，其他的Widget可以不排序。

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{// 返回lhs的质量是否好于rhs的质量的结果
}
// 将质量最好的20个元素顺序放在widgets的前20个位置上
partial_sort(widgets.begin(), widgets.begin()+20，widgets.end(), quailtyCompare);

3 nth_element

如果只需要找到最好的20个Widget，这20个Widget可以以任意顺序排列。nth_element用于排序一个区间，它使得位置n上的元素正好是全排序情况下的第n个元素。

来看下如何使用nth_element来保证最好的20个Widget被放到vector的前面：

// 将最好的20个元素放在widgets的前部，但并不关心它们的具体排列顺序
nth_element(widgets.begin(),widgtes.begin() + 19,widgets.end(),qualityCompare);

partial_sort对位置1~20中的元素进行了排序，而nth_element没有对它们进行排序。

nth_element除了可以找到排名在前的n个元素外，还可以用来找到一个区间的中间值，或者找到某个特定百分比上的值：

vector<Widget>::iterator begin(widgets.begin());
vector<Widget>::iterator end(widgets.end());
// 感兴趣的元素
vector<Widget>::iterator goalPosition = begin + widgets.size() / 2;
// 找出具有中间质量级别的Widget
nth_element(begin, goalPosition, end, qualityCompare);vector<Widget>::size_type goalOffset = 0.25 * widgets.size();
// nth_element质量由高到低"全排序"
// 找到75%质量的元素
nth_element(begin, begin + goalOffset, end, qualityCompare);

4 stable_sort

partial_sort、nth_element和sort都属于非稳定的排序算法。

stable_sort是与sort功能相同的稳定的排序算法。STL中没有与partial_sort和nth_element功能相同的稳定的排序算法。

5 patition

假如所需要的不是质量最好的20个Widget，而是所有的一级品和二级品。

partition算法可以把所有满足某个特定条件的元素放在区间的前面。首先定义一个函数来标志出那些Widget满足要求：

bool hasAcceptableQuality(const Widget& w)
{
}// 将满足hasAcceptableQuality的所有元素移动到前面，返回一个迭代器指向第一个不满足条件的Widget
vector<Widget>::iterator goodEnd = partition(widgets.begin(), widgets.end(), hasAcceptableQuality);

对应的稳定排序是stable_patition。

总结：

1 sort、stable_sort、partial_sort和nth_element等算法都要求随机访问迭代器，所以这些算法只适用于vector、string、deque和数组。

2 partition和stable_pattition只需要双向迭代器，所以适用于所有标准序列容器。

3 对vector、string、deque和数组中的元素完全排序，可以使用sort或stable_sort。

4 对vector、string、deque和数组中的元素，对最前面的n个元素进行排序，可以使用partial_sort。

5 对vector、string、deque和数组中的元素，需要找到第n个位置上的元素，或者需要找到最前面的n个元素但不必对这n个元素进行排序，可以使用nth_element。

6 对标准序列容器的元素按照是否满足某个条件区分开，可以使用partition和stable_partition。

7 对于list，可以使用partition和stable_partition；不可以使用sort和stable_sort，替代方案是使用list::sort。

32. 如果确实需要删除元素，需要在remove这一类算法之后调用erase

下面是remove的声明：

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

remove需要一对迭代器来指定所要进行操作的元素区间，它不接受容器作为参数，所以remove并不知道这些元素被存放在哪个容器中。

从容器中删除元素的唯一方法是条用该容器的成员函数erase，而erase并不知道它元素所在的容器，所以remove不可能从容器中删除元素。这说明一个现象：用remove从容器中删除元素，而容器中的元素数目不会因此而减少：

vector<int> v;
v.reserve(10);
for (int i = 1; i <= 10; i++) {v.push_back(i);
}
// 10
cout << v.size();v[3] = v[5] = v[9] = 99;
remove(v.begin(), v.end(), 99);
// 仍然输出10
cout << v.size();

请记住：remove不是真正意义上的删除，因为它做不到。

下面看下remove究竟做了哪些工作：

remove移动了区间中的元素，结果是"不用被删除"的元素移动到了区间的前部（保持原来的顺序）。它返回的迭代器指向最后一个"不用被删除"的元素之后的元素。

举个例子，调用remove之前v的布局如下：

todo

一般情况下，在新的逻辑结尾后面的元素仍然保留其旧的值。调用了remove之后，v的布局如下：

todo

哪些你想要删除的元素很容易标识，它们位于原区间中，从newEnd到原区间的结尾。为了删除这些元素，只需调用区间形式的erase。

vector<int> v;
...
// 真正删除所有值为99的元素
v.erase(remove(v.begin(), v.end(), 99), v.end());
// 输出7
cout << v.size();

特例，remove和erase被合并起来融入到了list的remove成员函数中，这是STL中唯一一个名为remove并且确实删除了容器中元素的函数：

list<int> li;
...
// 删除所有值为99的元素，删除后li的大小会改变
li.remove(99);

注意：还有两个属于"remove类"的算法：remove_if和unique，同样适用于这种情形。

unique-erase：从容器中删除重复的值。

list::unique：从list中删除重复的值。

33. 对包含指针的容器使用remove这一类算法时要特别小心

假如现在有一些动态分配的Widget，其中每一个Widget可能已经被验证过了，然后把结果指针存放在一个vector中：

class Widget {
public:// 是否被验证过bool isCertified() const;...
};vector<Widget*> v;
...
v.push_back(new Widget);

你想要删除那些没被验证过的Widget，基于第32条，你会自然地使用erase-remove_if习惯用法。

// 删除那些指向未被验证过的Widget对象的指针
// mem_fun见第41条
v.erase(remove_if(v.begin(), v.end(), not1(mem_fun(&Widget::isCertified))), v.end());

基于第7条，删除容器中的裸指针会导致资源泄漏(没delete)。但实际上，调用remove_if之后就已经造成资源泄漏了。

在调用remove_if之前v的布局如下图所示：

todo

调用了remove_if之后，v如下图所示：

todo

"要被删除"的指针已经被那些"不会被删除"额指针覆盖了，没有任何指针再指向Widget B和Widget C，所以它们永远不会被删除，资源泄漏。

remove_if和erase都返回之后，v如下图所示：

todo

得出结论：当容器中存放的是指向动态分配的对象的指针时，应该避免使用remove和类似的算法(remove_if和unique)。

解决该问题的方法：在进行erase-remove习惯用法之前，先把那些指向未被验证过的Widget的指针删除并置为空，然后清除该容器中所有的空指针。

// pWidget如果是未被验证的Widget，则删除该指针，并把它置为空
void delAndNullifyUncertified(Widget* pWidget) {if (!pWidget->isCertified()) {delete pWidget;pWidget = 0;}
}
// 将未被验证的Widget对象的指针删除并置为空
for_each(v.begin(), v.end(), delAndNullifyUncertified);
// 删除空指针
v.erase(remove(v.begin(), v.end(), static_cast<Widget*>(0)), v.end());

注意：容器中如果存放的是具有引用计数功能的智能指针，那么可以直接使用erase_remove_if习惯用法。

vector<Widget*> v;
...
v.push_back(make_shared(new Widget));// 删除那些指向未被验证过的Widget对象的指针
// mem_fun见第41条
v.erase(remove_if(v.begin(), v.end(), not1(mem_fun(&Widget::isCertified))), v.end());

34. 要求使用排序的区间作为参数的算法

有些算法要求使用排序的区间；有些算法使用排序的区间，效率会更高。

要求使用排序区间的STL算法如下：

1 binary_search,lower_bound,upper_bound,equal_range

2 set_union,set_intersection,set_difference,set_symmetric_difference

3 merge,inplace_merge

4 includes

另外，如下算法不要求排序的区间，但通常与排序的区间一起使用：

5 unique,unique_copy

1 binary_search,lower_bound,upper_bound,equal_range

用于查找的算法要求排序的区间，它们使用二分法查找。

对数时间的查找效率，前提是测试区间已经排序和拥有随机访问迭代器。

2 set_union,set_intersection,set_difference,set_symmetric_difference

只有提供了排序的区间，才能保证线性时间效率的集合操作

3 merge,inplace_merge

实现了合并和排序的联合操作：它们读入两个排序的区间，然后合并为一个新的排序区间。

只有源区间已经排过序，才能保证线性时间。

4 includes

用来判断一个区间中的所有对象是否在另一个区间中。

只有两个区间已经排过序，才能保证线性时间。

5 unique,unique_copy

删除每一组连续相等的元素，仅保留其中的第一个。

注意：unique并非真正意义上的删除。(见32条)

STL允许你为排序操作选择特定的比较函数，所以不同的区间可能有不同的排序方式。如果你为算法提供了一个排序的区间，而这个算法也带一个比较函数作为参数，那么，你一定要保证算法的比较函数与排序区间使用的比较函数有一致的行为。

下面这个例子说明了不一致的情形：

vector<int> v;
...
// 降序排列
sort(v.begin(), v.end(), greater<int>());
...
// 在数组中查找5，默认这个区间是升序排序的
bool r = binary_search(v.begin(), v.end(), 5);

binary_search默认情况下是升序排序，和排序sort行为不一致，则不会得到预期结果了。

修改如下：

// binary_search使用升序查找
bool r = binary_search(v.begin(), v.end(), 5, greater<int>());

总结：

1 提供排序的区间

2 保证算法使用的比较函数与排序使用的比较函数行为一致

35. 通过mismatch或lexicographical_compare实现忽略大小写的字符串比较

首先，需要一种办法来判断两个字符是否相同，而不去管它们的大小写：

1 mismatch

ciStringCompare根据两个字符串之间的关系返回一个负数、零或正数。

mismatch将标识出两个区间中第一个对应值不相同的位置。前提是，短的字符串作为第一个区间参数。mismatch返回一对迭代器，指示了这两个区间中对应字符第一次比较失败的位置：

int ciStringCompareImpl(const string& s1, const string& s2);int ciStringCompare(const string& s1, const string& s2)
{if (s1.size() <= s2.size()) return ciStringCompareImpl(s1, s2);else return ciStringCompareImpl(s2, s1);
}int ciStringCompareImpl(const string& s1, const string& s2)
{// PSCI = "pair of string::const_iterator"typedef pair<string::const_iterator, string::const_iterator> PSCI;PSCI p = mismatch(s1.begin(), s1.end(),s2.begin()not2(ptr_fun(ciCharCompare)));// 0:s1与s2相等;-1:s1比s2短if (p.first == s1.end()) {if (p.second == s2.end()) {return 0;} else {return -1;}}// p.first != s1.end()时等价于字符之间的比较return ciCharCompare(*p.first, *p.second);
}

2 lexicographical_compare

// 返回在忽略大小写的情况下,c1是否在c2之前
bool ciCharLess(char c1, char c2)
{return tolower(c1) < tolower(c2);
}bool ciStringCompare(const string &s1, const string &s2)
{return lexicographical_compare(s1.begin(), s1.end(),s2.begin(), s2.end(),ciCharLess);
}

如果第一个区间的字符串小于第二个区间的字符串，那么lexicographical_compare返回true；如果第一个区间的字符串大于等于第二个区间的字符串，那么lexicographical_compare返回false。

参考资料：

STL算法之lexicographical_compare的基本用法_hp_cpp的博客-CSDN博客

36. 理解copy_if算法的正确实现

STL中有11个包含"copy"的算法：

copy copy_backward repalce_copy reverse_copy replace_copy_if ...

但是copy_if算法并没有。

假如有一个函数来判断一个Widget是否有破损：

bool isDefective(const Widget& w);

你打算把一个vector中的所有破损Widget对象写到cerr中。

下面是大多数人以为正确的copy_if实现和调用：

templace<typename InputIterator,typename OutputIterator,typename Predicate>    //谓语
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{return remove_copy_if(begin, end, destBegin, not1(p));
}copy_if(widgets.begin(), widgets.end(),ostream_iterator<Widget>(cerr, "\n"),isDefective);

把not1应用到isDefective时会编译出错，第41条会解释为什么not1不能被直接应用到一个函数指针上。

下面是copy_if的正确实现：

templace<typename InputIterator,typename OutputIterator,typename Predicate>    //谓语
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{while (begin != end) {if (p(*begin)) *destBegin++ = *begin;++begin; }return destBegin;
}

37. 使用accumulate进行区间统计

对于区间，STL的算法：

count：统计出区间中有多少元素

count_if：统计出满足某个判别式的元素个数

min_element：最小值

max_element：最大值

假如你需要按照自定义的方式对区间进行统计处理，用accumulate，头文件<numeric>。

accumulate有两种形式：

(1)参数是两个迭代器和一个初始值，返回该初始值加上由迭代器标识的区间中的值的总和

list<double> ld;
...
double sum = accumulate(ld.begin(), ld.end(), 0.0);

注意：初始值被指定为0.0，不是0。0的话最后结果会被裁剪。

accumulate只要求输入迭代器，所以你可以使用istream_iterator和istreambuf_iterator：

cout << "The sum of the ints of cin: "<< accumulate(istream_iterator<int>(cin), istream_iterator<int>(), 0);

(2)参数是一个初始值和一个任意的统计函数

考虑用accumulate来计算一个容器中字符串的长度总和。

string::size_type stringLengthSum(string:size_type sumSoFar, const string& s)
{return sumSoFar + s.size();
}

stringLengthSum统计函数有两个参数，一个是目前为止区间中元素的统计值，一个是区间的下一个元素；返回值是新的统计值。size_type是容器中用于计数的类型。

set<string> ss;
..
string::size_type lengthSum = accumulate(ss.begin(), ss.end(), static_cast<string::size_type>(0), stringLengthSum);

同理,计算一个区间中数值的乘积：

vector<float> vf;
...
float product = accumulate(vf.begin(), vf.end(), 1.0f, multiplies<float>());

利用了标准的multiplies函数子类(functor class)。

6 函数子类及函数

38. 遵循按值传递的原则来设计函数子类(桥接模式)

C或C++都不允许将函数作为参数传递，只能传递函数指针，以标准库中的qsort为例：

void qsort(void* base, size_t nmemb, size_t size,int(*cmpfcn)(const void*, const void*));

第46条会解释通常情况下sort算法优于qsort函数。cmpfcn这个函数指针采用了按值传递的方式。

STL中函数对象在函数之间的传递也是按值传递的。以for_each算法为例，它需要一个函数对象作为参数，同时其返回值也是一个函数对象，都是按值传递的：

template<class InputIterator, class Function>
// 按值返回 return-by-value
Function for_each(InputIterator first, InputIterator last,Function f);    // 按值传递 pass-by-value

你可以迫使for_each按照引用方式传递参数和返回：

for_each<ClassA, Func&>(...);

但是STL使用者几乎不会这么做，因为将函数对象按照引用来传递时，有些STL算法根本不能通过编译，以not1配接器为例：

template <class Predicate>
unary_negate<Predicate>
not1(const Predicate& pred);

如果判别式Predicate是引用形式，则编译报错，因为C++不支持"引用的引用"。

所以，函数对象往往是按值传递和返回的，这意味着：

(1)函数对象必须尽可能小，否则复制的开销大

(2)函数对象必须是单态的，不能是多态的，即不能使用虚函数，否则会产生剥离问题(第3条)。

但实际上，不是所有的函数对象都小巧且单态。所以，需要找到一种方法：既允许函数对象可以很大且多态，也可以与STL采用的按值传递习惯保持一致。

方法是：将所需的数据和虚函数从函数子类中分离出来，放到一个新的类中；然后在函数子类中包含一个指针，指向这个新类的对象。

举例如下，一个包含大量数据且使用了多态的函数子类：

// BPFC:"Big Polymorphic Functor Class" 大的多态的函数子类
template<typename T>
class BPFC: public unary_function<T, void> {
private:Widget w;int x;...        //包含大量数据
public:virtual void operator()(const T& val) const;    //虚函数，存在剥离问题...
};

改写为创建一个小巧的、单态的类，其中包含一个指针，指向另一个实现类，将所有数据和虚函数都放在实现类里：

template<typename T>
class BPFCImpl: public unary_function<T, void> {
private:Widget w;int x;...    //大量数据virtual ~BPFCImpl();    //多态类需要虚析构函数virtual void operator()(const T& val) const;
friend class BPFC<T>;    //允许BPFC访问内部数据
};template<typename T>
// BPFC类：短小，单态
class BPFC: public unary_function<T, void> {
private:BPFCImpl<T> *pImpl;
public:void operator()(const T& val) const{pImpl->operator()(val);}...
};

这个技术在C++比较常用，《Effective C++》的第34条，《Design Patterns》的Bridge Pattern(桥接模式)。

参考网址：

http://c.biancheng.net/view/1364.html

39. 确保Predicate判别式是纯函数

先引入几个概念：

一个判别式(predicate)是一个返回值为bool类型(或可以隐式转换为bool)的函数。

一个纯函数(pure function)是指返回值仅仅依赖于其参数的函数。C++中，纯函数所能访问的数据应该仅局限于参数以及变量。

判别式类(predicate class)是一个函数子类，它的operator()函数是一个判别式，STL中凡是能接受判别式的地方，也可以接受一个判别式类的对象。

我们先看看违反此约束的后果，考虑以下设计拙劣的判别式类，它在第3次被调用的时候返回true，其余的调用均返回false：

class BadPredicate: public unary_function<Widget, bool> {
public:BadPredicate():timesCalled(0) {}bool operator()(const Widget&){return ++timesCalled == 3;}        
private:size_t timesCalled;
};

假设我们使用这个判别式来删除vector<Widget>中的第3个Widget：

vector<Widget> vw;
...
// 删除第3个元素
vw.erase(remove_if(vw.begin(), vw.end(), BadPredicate()), vw.end());

代码看似是正确的，实际上，它不仅删除了vw容器中的第3个元素，而且还删除了第6个元素。假如remove_if的一种实现：

template<typename FwdIterator, typename Predicate>
FwdIterator remove_if(FwdIterator begin, FwdIterator end, Predicate p)
{// p按值传递begin = find_if(begin, end, p);if (begin == end) return begin;else {FwdIterator next = begin;// p按值传递return remove_copy_if(next++， end, begin, p);}
}

在两次传参过程中，p都是按值传递的，也就是说是复制的。每次传递，会导致p的成员timesCalled为0。所以上述实现会导致不仅删除第3个元素，也会删除第6个元素。

STL中凡是可以接受一个判别式类的地方都可以接受一个判别式函数。所以注意，BadPredicate()改写为判别式函数也是错误的!如下：

bool BadPredicate(const Widget& w)
{static int timesCalled = 0;return ++timesCalled == 3;
}

40. 若一个类是函数子类，则应使它可配接

假设有一个包含Widget对象指针的list容器：

list<Widget*>::iterator widgetPtrs;
bool isInteresting(const Widget* pw);

现在想找到list中第一个满足isInteresting()的条件的Widget指针：

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), isInteresting);
if (i != widgetPtrs.end()) {// 处理第一个指向有趣Widget的指针...
}

如果，想找到list中第一个不满足isInteresting()的条件的Widget指针：

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), not1(isInteresting));

会编译出错，正确的做法是在not1之前，先将ptr_fun应用在isInteresting上：

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(), not1(ptr_fun(isInteresting)));
if (i != widgetPtrs.end()) {// 处理第一个指向有趣Widget的指针...
}

为什么需要先应用ptr_fun？因为ptr_fun完成了一些类型定义的工作，而isInteresting作为一个函数指针，缺少not1所需要的类型定义。

4个标准的函数配接器(not1,not2,bind1st和bind2nd)都要求一些特殊的类型定义，提供了这些必要的类型定义的函数对象被称为可配接的函数对象；反之，则称为不可配接的。这些特殊的类型定义是：argument_type,first_argument_type,second_argument_type以及result_type。提供这些类型定义最简便的办法是让函数子从特定的基类继承，如果函数子类的operator()只有一个实参，那么它应该从std::unary_function继承；如果函数子类的operator()有两个实参，那么它应该从std::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()的参数类型和返回类型。

一般来说，传递给unary_function或binary_function的非指针类型需要去掉const和引用(&)部分。

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

对于以指针作为参数或返回类型的函数子类，一般的规则是：传给unary_function或binary_function的类型与operator()的参数和返回类型完全相同。

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

unary_function和binary_function作为函数子类的基类，它们提供了函数对象配接器所需要的类型定义，这样通过简单的继承，我们产生了可配接的函数对象。应用如下：

list<Widget> widgets;
...
// 找到最后一个不符合阈值为10的Widget
list<Widget>::reverse_iterator i1 = find_if(widgets.rbegin(), widgets.rend(), not1(MeetsThreshold<int>(10)));
Widget w(...);
// 找到按WidgetNameCompare定义的规则排序时，在w之前的第一个Widget对象
list<Widget>::iterator i2 = find_if(widgets.begin(), widgets.end(), bind2nd(WidgetNameCompare(), w));

如果我们的函数子类并不是从unary_function或binary_function继承而来的，那么例子则无法编译，因为not1和bind2nd只能用于可配接的函数对象。

bind1st，bind2nd：

https://www.cnblogs.com/iyoyos/p/4157669.html

41. 理解ptr_fun、mem_fun和mem_fun_ref的来由

这些函数的主要任务是解决C++语法中的一个语法不一致问题。

如果有一个函数f和一个对象x，希望在对象x上调用函数f，为了执行这个调用，C++提供了3种不同的语法：

// 语法#1:f是一个非成员函数
f(x);
// 语法#2:f是一个成员函数，且x是一个对象或对象的引用
x.f();
// 语法#3:f是成员函数，且p是一个指向对象x的指针
p->f();

假如有一个测试函数test:

// 测试函数test
void test(Widget& w);
vector<Widget> vw;
...
// 调用#1，可通过编译
for_each(vw.begin(), vw.end(), test);

假如test是Widget的成员函数：

class Widget {
public:...void test();...
};
// 调用#2，不能通过编译
for_each(vw.begin(), vw.end(), &Widget::test);

假如有一个存放Widget*指针的容器：

list<Widget*> lpw;
// 调用#3，不能通过编译
for_each(lpw.begin(), lpw.end(), &Widget::test);

(1)一个非成员函数(2)一个对象和一个成员函数(3)一个对象指针和一个成员函数，难道我们需要3个版本的for_each实现么？然而，现实是，我们只有一个for_each算法：

template<typename InputIterator, typename Function>
Function for_each(InputIterator begin, InputIterator end, Function f)
{while (begin != end) f(*begin++);
}

可以看出，STL中的惯例是：函数或函数对象在被调用时，总是使用非成员函数的语法形式。

所以mem_fun和mem_fun_ref之所以存在的原因是它们被用来调整#语法2，#语法3的成员函数，使之能够通过#语法1被调用。来看下转换原理，mem_fun、mem_fun_ref是函数模板：

//mem_fun声明针对不带参数的非const成员函数
//C是类，R是指向的成员函数的返回类型
template<typename R, typename C>
mem_fun_t<R,C> mem_fun( R(C::*pmf)() );

mem_fun带一个指向某个成员函数的指针参数pmf，并且返回一个mem_func_t类型的对象。mem_func_t是一个函数子类，它拥有该成员函数的指针，并提供了opeartor()函数，在operator()中调用了通过参数传递进来的对象上的该成员函数。（相当于将类的一个成员函数转换为一个函数子类了）

list<Widget*> lpw;
...
//现在可以通过编译了
for_each(lpw.begin(), lpw.end(), mem_fun(&Widget::test));

mem_fun_ref与mem_fun类似，它将语法#2转换为语法#1，并产生一个类型为mem_fun_ref_t的配接器对象。（mem表示member，成员函数的意思）

ptr_fun使用的策略是，出现编译错误时使用，作用是提供必要的类型定义。

42. 确保less＜T＞与operator＜具有相同的语义(POLA)

假设Widget包含一个重量值和一个最大速度值：

class Widget {
public:...size_t weight() const;size_t maxSpeed() const;...
};

通常情况下，按重量对Widget排序是最自然的方式：

bool operator<(const Widget& lhs, const Widget& rhs)
{return lhs.weight() < rhs.weight();
}

假如我们需要创建一个按照最大速度进行排序的multiset<Widget>容器。multiset<Widget>的默认比较函数是less<Widget>，而less<Widget>在默认情况下会调用operator<来完成它的工作。一种方法是特例化less<Widget>，切断less<Widget>和operator<之间的关系，让它只考虑Widget的最大速度：

// 这是std::less对Widget的特化版本；一种不好的做法
template<>
struct std::less<Widget> : public std::binary_function<Widget, Widget, bool> {bool operator()(const Widget& lhs, const Widget& rhs) const{return lhs.maxSpeed() < rhs.maxSpeed();}
};

作为一般性规则，对std名字空间的组件进行修改通常是禁止的，会导致未定义的行为。但在某些特定情况下，对std名字空间的修补工作仍然是允许的，特别是，针对用户定义的类型，特化std中的模板。下面的例子就是Boost库的智能指针shared_ptr的部分实现：

namespace std {// 针对boost::shared_ptr<T>的std::less特化template<typename T>struct less<boost::shared_ptr<T>> : public     binary_function<boost::shared_ptr<T>, boost::shared_ptr<T>, bool> {bool operator()(const boost::shared_ptr<T>& a, const boost::shared_ptr<T>& b) const {// shared_ptr::get返回shared_ptr对象的内置指针return less<T*>()(a.get(), b.get());}};
}

这没有什么不合理，上面的less特化只是确保智能指针的排序行为与它们的内置指针的排序行为一致。

让less不调用operator<而去做别的事情，这会无端地违背程序员的意愿，违背了最小惊讶原则POLA(the principle of least astonishment)。

回到那个按照最大速度对multiset<Widget>容器进行排序的例子，你只需要创建一个函数子类，然后让这个函数子类完成你所期望的比较操作：

struct MaxSpeedCompare: public binary_function<Widget, Widget, bool> {bool operator()(const Widget& lhs, const Widget& rhs) const{return lhs.maxSpeed() < rhs.maxSpeed();}
};

我们使用MaxSpeedCompare作为比较类型来创建我们的multiset：

multiset<Widget, MaxSpeedCompare> widgets;

总结：

应该尽量避免修改less的行为，因为这样做很可能会误导其他的程序员，违背POLA程序设计原则。

7 使用STL

43. 算法调用优先于手写的循环

STL是由容器、迭代器、算法以及函数对象组成的。本章主要讨论编程时什么时候使用循环、什么时候使用算法、什么时候使用容器的成员函数。

由于STL算法涉及很广，所以意味着本该写循环完成的任务也可以用STL算法完成。假如有一个支持重画的Widget类：

class Widget {
public:...void redraw() const;...
};

当你重画一个list中的所有Widget对象时，可以用一个循环来完成：

list<Widget> lw;
...
for (list<Widget>::iterator i = iw.begin; i != iw.end(); ++i) {i->redraw();
}

也可以使用for_each算法来完成：

for_each(lw.begin(), lw.end(), mem_fun_ref(&Widget::redraw));

事实上，算法往往优先于循环，有三个理由：

1 效率。

2 正确性。

3 可维护性。

1 效率

(1)使用算法可以减少冗余的计算

list<Widget> lw;
...
for (list<Widget>::iterator i = iw.begin; i != iw.end(); ++i) {i->redraw();
}

每次循环，list::end()会被调用一次。但是我们并没有改变list，list::end()无需每次都调用一次。

for_each(lw.begin(), lw.end(), mem_fun_ref(&Widget::redraw));

for_each只调用了一次list::end()，其作为参数传递到for_each里了。

(2)算法内部做了优化，效率高于循环

2 正确性

当编写循环代码时，最关键的是要保证使用的迭代器是有效的。假设有一个数组，你想让每个数组元素加上41，然后把它插入到一个deque的前面。如果自己写循环，可能的实现如下：

// 函数中将会向这个数组写入数据，返回值是实际被写入的元素个数
size_t fillArray(double *pArray, size_t arraySize);
double data[maxNum];
deque<double> d;
...
size_t nums = fillArray(data, maxNum);
for (size_t i = 0; i < nums; ++i) {// 把数组元素每个加41，然后插入到d的前面d.insert(d.begin(), data[i] + 41);
}

上面代码每次插入的位置都是d.begin()，结果是最后插入的元素在deque的最前面，而我们期望的是最后插入的元素在deque的最后面。你也许想用以下方法对它进行修改：

deque<double>::iterator insertLocation = d.begin();
for (size_t i = 0; i < nums; ++i) {d.insert(insertLocation++, data[i] + 41);
}

上面代码会产生未定义的行为，每次deque::insert调用的时候，都会使deque中的所有迭代器失效，包括insertLocation。第一次调用insert后，insertLocation就已经失效了。正确的代码如下：

deque<double>::iterator insertLocation = d.begin();
for (size_t i = 0; i < nums; ++i) {// 每次insert被调用之后，更新insertLocation，以便保持迭代器有效，然后递增迭代器insertLocation = d.insert(insertLocation, data[i] + 41);++insertLocation;
}

花了很长时间才写到正确的代码！来和使用transform算法的代码比较下：

// 将data中的元素复制到d的前部，每个元素加上41
transform(data, data + nums,inserter(d, d.begin()),bind2nd(plus<double>(), 41));

(1)指定源数据的起点和终点 (2)使用inserter作为目标区间的起始迭代器 (3)正确使用bind2nd(plus<double>(), 41)

推荐使用算法，把迭代器的问题交给算法。

3 可维护性

来看下代码可读性，清晰度。

当你看到一个算法调用的时候，它的名字会指示它的用途。如transform，你会意识到某个函数将被应用到一个区间中的每一个对象，而这些结果将被写到某一个地方；当你看到for，while时，你知道的只是一种循环将要出现。

总结

(1) 如果你要做的工作与一个算法所实现的功能很相近，那么使用算法调用更好。

(2) 如果你的循环很简单，若使用算法来实现的话，却要使用配接器或要求一个单独的函数子类，那么使用循环更好。

(3) 如果你在循环中要做的工作很多且复杂，最好使用算法调用。因为复杂的计算应当当道单独的函数里，那么总可以找到一种办法把这个函数传给一个算法(往往是for_each)。

44. 容器的成员函数优先于同名的算法

有些STL容器提供了一些与算法同名的成员函数。如，关联容器提供了count、find、lower_bound、upper_bound和equal_range，而list则提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下，你应该使用这些成员函数，而不是相应的STL算法。理由有两点：

(1) 成员函数往往速度快

(2) 成员函数通常与容器结合得更紧密，这是算法所不能比的

1 关联容器

(1) 效率

假设有一个set<int>容器，其中包含了一百万个整数。现在你想知道727是否包含在其中，如果在的话，第一次出现727是在哪里。下面是两种不同的方法：

set<int> s;
...
set<int>::iterator i = s.find(727);
if (i != s.end()) ...
set<int>::iterator i = find(s.begin(), s.end(), 727);
if (i != s.end()) ...

set容器的find成员函数以对数时间运行(红黑树)，find算法以线性时间运行，以下是两者的效率统计结果：

find成员函数：最坏40此，平均20次。

find算法：最坏1000000次，平均500000次。

(2) “相同性”测试

STL算法以相等性来判断两个对象是否具有相同的值，而关联容器则使用等价性来进行“相同性”测试。第19条find算法在一个关联容器中搜索失败，而使用find成员函数来搜索同样的值可以成功。

2 list

(1) 效率

remove、remove_if、unique、sort、merge以及reverse这些算法无一例外地需要复制list容器中的对象，而专门为list容器量身定做的成员函数则无需任何对象副本，它们只是简单地维护好那些list节点连接起来的指针。所以list的成员函数性能会更好。

(2)list成员函数的行为不同于与其同名的算法的行为

如32条所述，要从一个容器中删除对象的话，在调用了remove、remove_if或unique算法之后，必须紧接着调用erase；而list的remove、remove_if和unique成员函数则实实在在地删除了元素，无须再调用erase。

sort算法与list的sort函数：sort算法要求随机访问迭代器，不能别应用到list容器上，list的迭代器只是双向迭代器。

merge算法与list的merge函数：merge算法是不允许修改其源区间的，而list::merge则总是在修改它操作的链表。

总结：

成员函数的性能更为优越，且它们能够与容器的行为保持一致。

45. 正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

1 找到区间中某个值

1.1 区间未排序

想知道list容器中是否存在某个特定的Widget对象w。使用count：

list<Widget> lw;
Widget w;
...
if (count(lw.begin(), lw.end(), w) != 0) {// w在lw中...
} else {// w不在lw中...
}

count返回0表示没找到，>0表示找到了元素。

使用find：

if (find(lw.begin(), lw.end(), w) != lw.end()) {...
} else {...
}

需要测试find的返回值是否等于链表的end迭代器。find找到第一个匹配结果后马上就返回了，而count必须要到底区间的末尾。

如果我们不仅要知道一个值是否存在，而且要知道哪个对象时，需要使用find：

list<Widget>::iterator i = find(lw.begin(), lw.end(), w);
if (i != lw.end()) {// 找到了,i指向第一个匹配的对象...
} else {...
}

1.2 区间排序

使用查找算法，binary_search、lower_bound、upper_bound和equal_range是以对数时间运行的。

1 binary_search

测试排序区间中是否存在某个特定的值：

vector<Widget> vw;
...
// 对vector进行排序
sort(vw.begin(), vw.end());
// 待查找的值
Widget w;
...
if (binary_search(vw.begin(), vw.end(), w)) {// w在vw中...
} else {// w不在vw中...
}

2 lower_bound

定位区间中的对象，当用lower_bound来查找某个特定值时，它会返回一个迭代器，迭代器要么指向该值的第一份副本(找到的话)，要么指向一个适合于插入该值的位置(没找到的话)。所以，你必须测试lower_bound返回的迭代器，以判断该对象是否是你想要找的值。

许多程序员会按如下方式使用lower_bound：

vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);
// 这里有个错误！
if (i != vw.end() && *i == w) {...
} else {...
}

上面if里是个相等性测试，但lower_bound使用等价性来搜索的。大多数情况下等价性测试和相等性测试结果是相同的，但19条也说明了不同的情况。

3 equal_range

定位区间中的对象，使用equal_range。equal_range返回一对迭代器，第一个迭代器等于lower_bound返回的迭代器，第二个迭代器等于upper_bound返回的迭代器。equal_range返回的这一对迭代器标识了一个子区间，其中的值与你所查找的值等价。

(1)如果返回的两个迭代器相同，则说明查找所得的对象区间为空：即没有找到这样的值

vector<Widget> vw;
...
sort(vw.begin(), vw.end());typedef vector<Widget>::iterator VWIter;
typedef pare<VWIter, VWIter> VWIterPair;VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if (p.first != p.second) {// 找到了特定值，p.first指向了第一个与w等价的对象，p.second指向最后一个与w等价的对象的下一个w位置...
} else {// 没找到特定值，p.first和p.second都指向w的插入位置...
}

这段代码只使用了等价性，所以总是正确的。

(2)equal_range返回的迭代器之间的距离与这个区间中的对象数目是相等的

例如，如果要在vw中找到与w等价的Widget对象的位置，并打印出有多少个这样的对象：

VWIterPair p = equal_range(vw.begin(), vw.end(), w);
cout << "There are " << distance(p.first, p.second) << " elements in vw equivalent to w";

2 找到区间中某个位置

到目前为止，我们要在一个区间中查找某个特定的值，但有时我们需要找到区间中的某个位置。

例如，假设我们有一个Timestamp类和一个存放Timestamp的vector，且vector已经排序，其中老的时间戳在前面(即时间小的值在前面，时间大的值在后面)：

class Timestamp {...};
// 判断lhs是否在rhs之前
bool operator<(const Timestamp& lhs, const Timestamp& rhs);
vector<Timestamp> vt;
...
sort(vt.begin(), vt.end());

我们希望从vt中删除比ageLimit这个时间戳值小的元素，即需要找到>=ageLimit值的位置：

Timestamp ageLimit;
...
// 从vt中删除所有在ageLimit之前的对象
vt.erase(vt.begin(), lower_bound(vt.begin(), vt.end(), ageLimit));

我们希望删除比ageLimit这个时间戳值小的元素并包含ageLimit的元素也删除，即需要找到>ageLimit的值：

vt.erase(vt.begin(), upper_bound(vt.begin(), vt.end(), ageLimit));

3 标准关联容器使用成员函数

之前的建议适合标准序列容器(vector、string、deque和list)。对于标准关联容器只需要选择同名的成员函数即可。只有binary_search例外，关联容器没有与之对应的成员函数。要在set或map中查找一个值是否存在，使用count习惯用法：

set<Widget> s;
...
Widget w;
...
if (s.count(w)) {// 存在与w等价的值...
} else {...
}

对于multiset或multimap中测试一个值是否存在，则一般情况下使用find，因为find只要找到一个期望值就返回。

4 总结

表格如下：

想知道什么	使用算法		使用成员函数
想知道什么	未排序区间	排序区间	set/map	multiset/multimap
特定的值是否存在	find	binary_search	count	find
特定的值存在哪里	find	equal_range	find	find
第一个不超过特定值的对象在哪里	find_if	lower_bound	lower_bound	lower_bound
第一个在特定值之后的对象在哪里	find_if	upper_bound	upper_bound	upper_bound
具有特定值的对象有多少个	count	equal_range (distance)	count	count
具有特定值的对象都在哪里	find (反复调用)	equal_range	equal_range	euqal_range

排序一栏中，equal_range出现的次数很多，因为在查找过程中使用等价性测试很重要。如果使用lower_bound或upper_bound，会很容易回退到相等性测试，需要额外注意。

46. 考虑使用函数对象而不是函数作为STL算法的参数

1 将函数对象传递给STL算法往往比传递实际的函数更高效

假定需要将一个包含double类型数据的vector按降序排序，使用函数对象：

vector<double> v;
...
sort(v.begin(), v.end(), greater<double>());

使用内联函数：

inline bool doubleGreater(double d1, double d2)
{return d1 > d2;
}
...
sort(v.begin(), v.end(), doubleGreater);

你会发现，使用greater<double>的sort调用比使用doubleGreater的sort调用快很多。解释如下：

如果一个函数对象的operator()函数已经被声明为内联的，那么它的函数体可以直接被编译器使用。函数greater<double>::operator()是一个内联函数，所以编译器在sort的实例化过程中将其内联展开；如果使用doubleGreater来作为参数调用sort算法，情况不同。我们要清楚，在C/C++中并不能真正地将一个函数作为参数传递给另一个函数。如果我们试图将一个函数作为参数进行传递，则编译器会隐式地将它转换成一个指向该函数的指针，即转换为如下：

void sort(vector<double>::iterator first, vector<double>::iterator last,bool (*comp)(double, double));

所以在sort内部每次comp被用到的时候，编译器都会产生一个间接的函数调用，即通过指针发出的调用。大多数编译器不会对此进行内联优化，即使标识为inline。

2 避免一些语言本身的缺陷

下面是一个例子：

// 函数模板
template<typename FPType>
FPType average(FPType val1, FPType val2)
{return (val1 + val2) / 2;
}template<typename InputIter1, typename InputIter2>
void writeAverages(InputIter1 begin, InputIter1 end1, InputIter2 begin2, ostream& s)
{// iterator_traits模板类用来萃取迭代器的特性transform(begin1, end1, begin2,ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s, "\n"),average<typename iterator_traits<InputIter1>::value_type>);
}

问题在于如果存在另一个名为average的函数模板，它也只带一个类型参数。那么就会有二义性，编译器就无法分辨使用哪一个函数模板。解决办法是自定义函数对象来替代函数模板：

// 函数对象
template<typename FPType>
struct Average: public binary_function<FPType, FPType, FPType> {FPType operator()(FPType val1, FPType val2) const{return (val1 + val2) / 2;}
}template<typename InputIter1, typename InputIter2>
void writeAverages(InputIter1 begin, InputIter1 end1, InputIter2 begin2, ostream& s)
{// iterator_traits模板类用来萃取迭代器的特性transform(begin1, end1, begin2,ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s, "\n"),Average<typename iterator_traits<InputIter1>::value_type>);
}

47. 避免产生直写型(write-only)的代码

假定有一个vector<int>,现在要删除其中所有<x的元素，但是保留最后>=y的元素之前的所有元素。

{1,1,3,...,7,8,1,2} x=3,y=8 则需要删除最后的1和2元素

解决该问题的思路大致如下：

1 通过以reverse_iterator作为参数调用find_if，找到容器中最后一个其值>=y的元素

2 通过erase_remove习惯用法杀出区间中符合条件的元素

看下面的代码：

vector<int> v;
int x,y;
...
v.erase(remove_if(find_if(v.rbegin(), v.end(), bind2nd(greater_equal<int>(), y)).base(), v.end(),bind2nd(less<int>(), x)),v.end()
);

上面代码有两方面不妥之处：

1 过于复杂的嵌套函数调用。

2 若要理解这条语句，必须有很强的STL背景。它使用了find和remove算法的if形式；它使用了reverse_iterator；它将reverse_iterator转换为iterator；它使用了bind2nd；它创建了匿名的函数对象；它还使用了erase-remove习惯用法。

下面是一种分解的做法：

typedef vector<int>::iterator VecIntIter;
VecIntIter rangeBegin = find_if(v.rbegin(), v.rend(), bind2nd(greater_equal<int>(), y)).base();
v.erase(remove_if(rangeBegin, v.end(), bind2nd(less<int>(), x)), v.end());