Binsite

本文发自 http://www.binss.me/blog/my-excerpt-of-effective-stl/，转载请注明出处。

接下来是看《Effective STL》。依然还是受益匪浅，然而也有许多未理解之处，期望日后第二遍时有更深入的理解。

以下是读书过程中的摘录。

引言

凡是涉及指针容器的的设计几乎无一例外地会用到引用计数。

所有重载了operator() 的类都是 函数子 类（functor class）。从这些类创建的对象被称为函数对象或函数子，因为它们可以像函数那样被调用。

模版的嵌套从属类型前需要加typename（避免被当作静态成员）。

第一章 容器

1 慎重选择容器类型

标准序列容器：vector、string、deque、list

标准关联容器：set、multiset、map、multimap

非标准序列容器：slist（单向列表）、rope（重型string）

非标准关联容器：hash_set、hash_multiset、hash_map、hash_multimap

非STL容器：数组、bitset、valarray、stack、queue、priority_queue

连续内存的容器：vector、deque、string、rope

基于节点的容器：list、slist、标准关联容器、散列容器

在任意位置插入新元素：序列容器

元素无序：散列容器

随机访问迭代器：vector、deque、string、rope

避免插入删除时移动元素：别使用连续内存容器

数据布局和C兼容：vector

关注查找速度：散列容器->排序的vector->标准关联容器

避免引用计数：别使用string、rope

可回滚：基于节点的容器。只有list支持多个元素操作的回滚。

避免迭代器、指针、引用无效：基于节点的容器

迭代器随机访问，若没有删除且插入只发生在容器末尾，则指针和引用不会失效（但迭代器可能会失效）：deque

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

不要妄想更换容器后代码无须改变：

• 专有操作：比如序列容器才支持push_front和push_back，关联容器才支持count和lower_bound

• 操作因容器不同而不同：如insert和erase

• 只能使用功能的交集而无法使用特性

• 迭代器、指针、引用失效时机不同

为了方便日后更换容器（或分配子）、缩短类型名称的长度，可以用typedef为容器和其迭代器定别名。

为了避免容器暴露，还可以用类对容器进行封装。

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

对象存入容器中时会被复制，被取出时也会被复制（copy in, copy out）。

在进行排序等操作时，容器中的对象也会被复制（移动）。

不要将子类元素放入基类容器中，不仅不能利用虚特性，还导致对象被切割。

为了高效，可以考虑智能指针。

STL仅在需要时才创建对象，比数组聪明的多。

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

empty对所有的标准容器都耗费常数时间，而对于一些list实现，size耗费线性时间。

这些list实现追求让操作（如splice）耗费常数时间，不维护链表的大小，而是直到调用size()时才进行计算。否则，splice操作为了计算所链接的元素个数，需要耗费线性时间。

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

简单来说，能一次拷多个的就不要一个个拷，因为一个个拷效率低。也不要用alogirithm的copy+插入迭代器来拷，因为copy往往不能准确地表达语义，并且效率和一个个拷差不多。

注：copy的原型：

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator _First, InputIterator _Last, OutputIterator _DestBeg);

区间函数列表：

• 区间创建

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

• 区间插入

  序列容器：void container::insert(iterator position, InputIterator begin, InputIterator end);

  关联容器：void container::insert(InputIterator begin, InputIterator end);

• 区间删除

  序列容器：iterator container::erase(iterator begin, iterator end);

  关联容器：void container::erase(iterator begin, iterator end);

• 区间赋值

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

区间成员函数的优势：

• 意图清晰
• 代码精简
• 效率更高

假设容器中有n个元素，现新插入k个元素。

减少了不必要的函数调用：区间成员函数只需调用一次；而单元素成员函数要调用k次。

减少了容器中元素的移动开销：区间成员函数只需移动一次，带来n次赋值操作符函数的调用和k次复制构造函数的调用的开销；而单元素成员函数要移动k次，带来( n-1)*k次赋值操作符函数的调用和k次复制构造函数的调用的开销。

减少了容器扩展开销：基于连续内存的容器在容量不足进行扩展时会将容量加倍，区间成员函数能够一次到位；而单元素成员函数要扩展log2(k)次。

基于节点的容器虽然没有移动和扩展开销，但相应的，会带来2*(k-1)次不必要的节点next和prev指针赋值开销。

6 当心C++编译器最烦人的分析机制

C++会尽可能地解释为函数声明而非对象声明。

list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>()); 会被解析成一个data函数。

为了避免，只能使用命名的迭代器：

istream_iterator<int> dataBegin(dataFile);

istream_iterator<int> dataEnd;

list<int> data(dataBegin, dataEnd);

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

使用智能指针容器（容器中的对象为智能指针，且要求为引用计数形式的，如std::shared_ptr），保证容器中new出来的资源总能被释放。

8 切勿创建包含auto_ptr的容器对象

复制auto_ptr时，它所指对象的所有权会移交给新的指针。这样在容器中会导致严重后果：

对于vector sort()的一种实现——快排，在选轴(pivot)时会把对象的所有权转移到临时变量（pivot用于比较），然后临时变量在sort()结束时被释放，导致vector中的智能指针丢失对象（变为NULL）。

注：auto_ptr已在C++11中废弃。见 http://stackoverflow.com/questions/3697686/why-is-auto-ptr-being-deprecated

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

没有对所有容器都适用的删除元素方法。

基于连续内存的容器：采用erase-remove

c.erase(remove(c.begin(), c.end(), deleteValue), c.end());
c.erase(remove_if(c.begin(), c.end(), deleteValuePredicate), c.end())

list：

c.remove(deleteValue);
c.remove_if(deleteValuePredicate);

或

for(Container<ValueType>::i=c.begin(); i != c.end();)
{
    if(deleteValuePredicate(*i))
    {
        i = c.erase(i);
    }
    else
    {
        ++i;
    }
}

10 了解分配子（allocator）的约定和限制

STL内存分配子是一个模版，用于分配和释放原始内存。

声明：

template<typename T>
{
public:
    pointer allocate(size_type numOjbects, const void *localityHint=0);
    void deallocate(pointer ptrToMemory, size_type numOjbects);
    ...
};

模版参数T代表其分配内存对象的类型。它应该提供类型定义pointer（T*）和reference（T&）。

对于pointer（T *），即使T对象未进行构造，但是却返回了一个T的指针。STL期望调用者会在返回内存中构造T对象，然而在reserve情况下可能并不会发生构造。

C++标准允许STL的实现假定同一类型的分配子是等价的，因此可移植的分配子都不能拥有非静态的数据成员。

标准容器依赖于rebind模版，因此分配子必须提供rebind模版。

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

如果STL默认的分配子有新要求，可以自定义分配子，然后在构造容器时作为第二个模版参数传入。如：

vector<double, SharedMemoryAllocator<double>> SharedDoubleVec;

注意同类型的分配子必须等价。

主要需求：

• 使用共享内存

• 将不同容器的对象放置于不同的堆

12 切勿对STL容器的线程安全性有不切实际的依赖

STL标准只能保证：

• 多个线程读是安全的

• 多个线程对不同容器的写是安全的

为了实现线程安全，在容器的成员函数调用结束前、容器返回的迭代器生存期结束前、作用于容器的算法结束前，都要锁住容器。

有时还需要对多行代码进行同时加锁，STL很难推断出来。

加锁开销大，如果STL都加锁，对无须线程安全的用户不公平。

应该通过加锁类来创建容器，这样锁在容器作用域结束时随着析构自动释放。为了使加锁类发挥作用，创建新的代码块来括住要加锁的代码。

第二章 vector和string

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

使用new需要确保：必须调用且只能调用一次delete（否则会资源泄漏），且delete形式正确（delete还是delete[]）

vector和string消除了这些负担，且提供了begin、end、size这些方便的函数以及迭代器。因此考虑用vector和string来替代new T[...]。

string一般实现为引用计数，如果用于多线程环境，可以考虑用vector<char>取代。

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

每当vector和string需要更多空间时，就会执行以下步骤：

1. 分配一块大小为当前容量n倍的内存（一般n为2）

2. 将原容器的内容从旧内存拷贝到新的内存中

3. 析构旧内存中的对象

4. 释放旧内存

为了避免频繁的重新分配，可以通过reserve(Container::size_type n)来扩大容器容量。

这种做法适用于预先能估算容器元素数量的情况；也可以先预留，在元素加入完后再去除多余容量。

15 注意string实现的多样性

一般来说，string的实现包含以下信息：字符串的大小、容量、字符串的值。还可能包含分配子的一个副本、值的引用计数等。

实现一

包含字符串的大小、容量、和分配子的副本，还有一个指向动态分配内存的指针，内存中包含引用计数和字符串值。

实现二

只包含指向struct的指针。struct包含了字符串的大小、容量、引用计数、指向值的指针，以及同步控制相关的其它数据。

实现三

同实现二，只不过指针指向了一块动态分配的内存。不支持针对单个对象的分配子。

实现四

内部包含一块内存，可以容纳15个字符（小字符串优化）。当字符串大小超过15时，内存的起始部分被替换为指向动态分配内存的指针，指向字符串的值。

为了有效使用STL，应该了解string的实现。

16 了解如何把vector和string数据传给旧API

vector中的元素存储在连续的内存中，所以能过直接把vector传给接受数组参数的API：

if(!v.empty())
{
    doSomething(&v[0], v.size());
}

利用数组来初始化vector：

size_t fillArray(double * pArray, size_t arraySize);
vector<double> vd(maxNumDoubles);
vd.resize(fillArray(&vd[0], vd.size()));

fillArray用于向vector中写入double元素，并返回写入成功的个数。

因为只有vector有这种特性，可以让其作为容器和C API之间的中介，如：

利用vector初始化list：

list<double> l(vd.begin(), vd.end());

利用set初始化vector：

vector<int> v(intSet.begein(), intSet.end());
if (!v.empty())
{
    doSomething(&v[0], v.size());
}

注意：这种取指针的方式通常（非排序）可以修改vector中的元素，但不能增加或删除vector中的元素。

17 使用swap技巧除去多余的容量

容器容量只会自动增加，不会自动减少。通过swap可以缩简容量：

vector<Contestant>(contestants).swap(contestants);

vector<Contestant>(contestants)会调用拷贝构造函数创建出临时对象，而拷贝复制函数只会为存在的元素分配内存，因此临时容器对象没有多余容量。然后通过swap交换两者的内容（当然迭代器、指针、引用也会被交换），于是原本容器中的内存随着临时变量的析构而释放了。

swap也可以用来清空容器：

vector<Contestant>().swap(contestants);

18 避免使用vector<bool>

vector<bool>并不存储bool，它无法完全满足STL容器的需求，不是一个STL容器。它是通过bitfield来实现的，用一个bit代表一个bool值，因此无法获取其中单独的一个元素对象。所以为了保持和其它容器行为上的一致，operator []返回代理而不是引用，导致对其返回值取址得到的不是一个bool指针，违反了STL的的要求。

可以使用deque<bool>和bitset（非STL）取代之。

第三章 关联容器

19 理解相等（equality）和等价（equivalence）的区别

相等：以operator ==为标准。只要operator ==返回true，不管内部是否相同，都表示相等。

等价：以"在排序的区间中对象值的相对顺序“为标准。

关联容器基于等价而非相等，始终使用判别式来排序、判断元素是否“相等”：

!c.key_comp()(x, y) && !c.key_comp()(y, x)

key_comp的默认实现为less，即“<“。可以自定义（通过函数子类，struct继承某个函数子）来实现：

struct StringCompare: public binary_function<string, string, bool>
{
    bool operator()(const string& lhs, const string& rhs) const
    {
        return my_compare(lhs, rhs);
    }
};

并作为第二个模版参数传入：

set<string, StringCompare> my_set;

set的声明如下：

template <class Key, class Compare = less<Key>, class Allocator = allocator<Key> >
class set;

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

关联容器存放指针时，要想其按照内容排序（而不是按指针排序），应该自己实现比较函数子类（见#19），并作为第二个模版参数传入。

为了方便，可以创建比较函数子类模版：

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

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

在自定义比较函数子类时，可能导致在等值情况下比较函数子返回true（如>=），于是集合允许两个等值的元素插入到容器中（判断为不等价），违反了标准关联容器（如set等）的定义。

对关联容器排序的比较函数必须为它们所比较的元素定义一个“严格的弱序化”，其中一个要求就是：总是在比较等值的两个元素的时候返回false。

22 切勿直接修改set或multiset中的键

对于map和multimap，其中的元素类型为pair<const K, V>，所以键无法被修改。而set或multiset中的元素类型却是T而不是const T，因为元素的某些成员需要能够被修改。因此需要保证元素的键成员不要被修改，因为它们影响了容器的有序性。

在某些实现中，set或multiset中的元素不允许被修改。不要使用const_cast来去除const元素属性，因为在这种情况下键可能会被修改。

安全的修改步骤：

1. 用迭代器找出要修改的容器元素
2. 为该元素复制一份非const副本
3. 修改该副本
4. 把元素从容器中删除（erase）
5. 把元素副本插入到容器中（insert，可以传入1得到的迭代器作为提示）

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

若对查找速度要求高，可以采用散列容器（几乎为常数时间的查找，视散列函数）。

若对容器操作行为规律（始终按照批量设置->批量查找），可以采用排序的vector。相比标准关联容器，避免了二叉树指针空间开销（占用过多的内存会导致换页，产生page fault），并且由于其节点散布在全部内存空间中，降低了引用局限性。查找时间都是O(log2n)。

但是这种使用方法必须让vector保持有序，因此仅在操作行为规律，即模式为批量设置然后批量查找时采用。

而由于标准关联容器通常被实现为平衡二叉树，更适合增删查操作混杂时使用。

24 当效率至关重要时，请在map::operator[]与map::insert之间谨慎做出选择

map的operator []：先检查key是否在map中，如果是，返回其引用，如果否，构造一个新对象并返回它的引用。

在为map插入元素时，使用insert比operator[]后赋值效率高，因为可以直接调用构造函数而不是先调用默认构造函数再赋值。

但如果是修改元素，则operator[]效率更高，因为insert必须构造pair。

结合operator[]和insert的优点：

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapTypee::iterator efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgType& v)
{
    // lower_bound返回元素位置，如果元素不存在，则返回它应该在（插入到）什么位置
    typename MapType::iterator lb = m.lower_bound(k);
    if( lb != m.end() && !(m.key_comp()(k, lb->first)) )
    {
        lb->second = v;
        return lb;
    }
    else
    {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k,v));
    }
}

使用KeyArgType、而ValueArgType不是MapType::key_key、MapType::value_type，是为了避免对象因需要转换而被构造，在赋值情况下，直接调用类的operator = 赋值。

25 熟悉非标准的散列容器

STL没有散列容器。可以熟悉非标准版本的散列容器。

注：C++11引入散列容器std::unordered_map

第四章 迭代器

26 iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

STL为所有标准容器都提供了4种迭代器：

iterator：相当于T*

const_iterator：相当于const T*

reverse_iterator：相当于T*，从容器尾部反向遍历到头部

const_reverse_iterator：相当于const T*，从容器尾部反向遍历到头部

iterator是基类，const_iterator和reverse_iterator继承了iterator，const_reverse_iterator继承了const_iterator和reverse_iterator。

尽量使用iterator、避免混用的原因：

1. 大部分版本的insert和erase函数要求使用iterator。

2. 无法将const_iterator隐式转换为iterator

3. 将reverse_iterator转换为iterator后要经过调整才能用

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

不存在从const_iterator到iterator的隐式转换，也无法通过const_cast进行强制类型转换（除了vector和string，因为它们的迭代器是指针）。

因此将容器的const_iterator转换成iterator的最好方法是复制一个：

Container d;
Container::const_iterator ci;
Container::iterator i(d.begin());
advance(i, distance<Container::const_iterator>(i, ci));

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

调用reverse_iterator的base()成员函数可以得到与之相对应的iterator，对于插入操作，可以直接用，而对于删除操作，reverse_iterator调用base()返回的是下一个位置，应该使用(++ri).base()。

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

使用istream_iterator<char>来复制文本内容到string中，要清除输入流的skipws标志：

inputFile.unsetf(ios::skiwps);

但istream_iterator内部调用opertaor>>来进行格式化输入，带来了类型检查、异常检查等开销。

如果单纯进行逐字符拷贝，可以使用istreambuf_iterator<char>，该迭代器只会简单地从流缓冲区中取出下一个字符。

相比来说，istreambuf_iterator比istream_iterator具有更优越的性能。

第五章 算法

30 确保目标足够大

transform：将一个容器中符合条件的元素复制到另外一个容器

使用transform算法时，因为默认进行的是替换型操作，必须确保目标容器相应的元素存在（即目标容器应该大于等于原容器，如果不够可以用resize调整）。

为了将transform的结果插入到目标容器尾端，需要传入back_inserter生成迭代器（需要容器支持push_back）：

transform(values.begin(), values.end(), back_inserter(results), transmogrify);

同理，front_inserter能将transform的结果插入到目标容器前端（需要容器支持push_front）。

inserter则能过将结果插入到特定位置，如插入到中间：

transform(values.begin(), values.end(), inserter(results, result.begin() + result.size()/2), transmogrify);

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

完全排序：

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

找到前n并排序：

template<class RandomIt, class Compare>
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

找到前n：

template<class RandomIt, class Compare>
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

sort、partial_sort、nth_element都属于非稳定排序，即在排列等价元素的时候，无法保证原来在前面的排完序依然在前面。

稳定排序：

template<class RandomIt, class Compare>
void stable_sort( RandomIt first, RandomIt last, Compare comp );

因为sort、partial_sort、nth_element、stable_sort需要随机访问迭代器，所以只能应用于vector、string、deque和数组。

满足函数UnaryPredicate（返回bool）的元素会被移到容器前端，返回指向最后一个满足条件元素的下一个元素的迭代器：

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

partition和stable_partition只需要双向迭代器，所以可以应用于所有标准序列容器。

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

无法从迭代器推知对应的容器类型。

remove算法不是真正意义上的删除，它不能从容器中删除元素，

实际上，remove将“不用被删除”的元素移动到区间前部，并返回指向最后一个“不用被删除”元素的下一个元素。

所以在remove后应该调用erase，如删除值为99的元素：

v.erase(remove(v.begin(), v.end(), 99), v.end());

与之相似的还有remove_if和unique。

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

通过remove（remove_if、unique）删除元素时，若元素是指针，则指针会因为被覆盖导致资源泄漏。

解决方法：

• 调用remove前先遍历容器，如果指针所指的元素要被删除，析构指针所指对象，保留空指针
• 使用智能指针

34 了解哪些算法要求使用排序的区间作为参数

要求排序区间的STL算法：

为了使用二分查找：binary_search、lower_bound、upper_bound、equal_range、

为了提高性能（保证线性时间）：set_union、set_intersection、set_difference、set_symmetric_difference、megre、inplace_merge、includes

不一定要排序区间（但排好序更好）：unique、unique_copy

如果容器的排序方式和算法的默认排序方式less（<）不同时，需要指定函数子，如：binary(v.begin(), v.end(), 5, greater<int>());

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

tolower的参数和返回值都是int，且规定除了EOF外（用负数表示），其他值必须能用unsigned char来表示。

lexicographical_compare可以根据传入函数（判别式）来进行容器内容比较，返回两个容器不同的第一个位置。

不区分大小写字符串比较；

bool ciCharLess(char c1, char c2)
{
    return tolower(static_cast<unsigned char(c1)) < tolower(static_cast<unsigned char(c2));
}
bool ciStringCompare(const string& s1, const string& s2)
{
    return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), ciCharLess);
}

如果sting中间不包含空字符且不考虑国际化支持，可以把string专为 const char* 后用strcmp比较。

36 理解copy_if算法的正确实现

STL中没有copy_if( 注：C++11已加入 )，在此之前，只能手动复制：

while(begin != end)
{
    if( p(*begin) )
    {
        *destBegin ++ = *begin;
    }
    ++begin;
}

37 使用accumulate或者for_each进行区间统计

统计区间元素数目：count

统计区间满足判别式元素数目：count_if

区间最小值：min_element

区间最大值：max_element

自定义统计：

方法一：

template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);

init为统计初始值。op为统计函数，接受两个参数。op不能使任何迭代器失效，也不能修改范围内的任何一个元素（C++11）。

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);

特化版。统计函数为operator+。即以init为初始值进行累加。

方法二：

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);

f可以是统计函数，但只接受一个参数。在for_each执行完毕后，f的副本会被返回，我们必须从中提取我们所需的统计信息。

第六章 函数子、函数子类、函数及其它

38 遵循按值传递的原则来设计函数子类

对于函数（指针）和函数子，作为STL的参数和返回值都是按值传递的。

如果通过模版参数来强制指定为引用，则可能编译不通过（出于性能考虑，有些STL配接器和算法使用引用参数来接受函数子，这样做会造成引用的引用）。

为了避免函数子（对象）的巨大复制开销和子类向父类传参导致的切割问题，将函数子中的数据和虚函数放到一个新的类中，函数子只保留一个指向新类对象的指针（桥接模式）。

39 确保判别式是“纯函数”

判别式（predicate）是一个返回值为bool类型（或可隐式转换为bool）的函数。STL中常用于关联容器的比较函数以及排序算法的参数。

纯函数：返回值仅仅依赖于其参数的函数（当然还有常量）。

判别式类：函数子类，operator ()是判别式。

如果判别式不是纯函数，则其必定依赖于其它某些变量，如函数子的类成员、函数的static变量等。这样会导致判别式拥有状态，影响下次调用的结果。

由于STL中接受判别式的地方既可以接受判别式，也可以接受判别式对象。

40 若是一个函数子，则应使他可配接

STL函数配接器：能够将函数子与另一个函数子、或某一个一般函数、或某个值结合起来形成一个新的函数子，预定义由四个：not1、not2、bind1st、bind2nd。

函数配接器都要求参数可配接，即包含特殊的类型定义：argument_type、first_argument_type、second_argument_type、result_type。

ptr_fun：将普通函数转换为可配接

对于函数子，获取这些特殊类型定义的最好办法是继承以下基类：

template <class ArgumentType, class ResultType>
struct unary_function;
template <class ArgumentType1, class ArgumentType2, class ResultType>
struct binary_function;

尽量不要让函数子拥有多个operator()，因为函数子最多只能继承一个模版实例化的基类，因此只有一种调用形式是可配接的。

注：C++11中，bind1st和bind2nd被废弃。由更泛化的std::bind取代。

ptr_fun被废弃。由更泛化的std::function和std::ref取代。

unary_function和binary_function被废弃。可能是因为C++11引入了更泛化的可变参数模版std::function的原因？

41 理解ptr_fun、mem_fun和mem_fun_ref的来由

mem_fun：用于指针容器对象调整成员函数调用为普通的函数调用（ obj->function() -> function(obj) ）。函数返回配接器mem_fun_t，该函数子实现调用利用参数调用成员函数。

mem_fun_ref：用于容器对象调整成员函数调用为普通的函数调用（ obj.function() -> function(obj) ）。函数返回配接器mem_fun_ref_t，该函数子实现调用利用参数调用成员函数。

注：C++11中，mem_fun和mem_fun_ref被废弃。由更泛化的mem_fn和bind取代。

42 确保less<T>与operator<具有相同的语义

程序员可以针对用户定义的类型，特化std命名空间内的模版，但不能修改std命名空间中的组件。

less默认调用operator <来完成比较，为了避免违反直觉，不要修改less的行为。

第七章 在程序中使用STL

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

每一个算法都至少需要使用一对迭代器来指定一个区间，然后在该区间上执行操作。

算法优于手写循环的原因：

• 效率高（STL的设计者比使用者更了解其内部结构并进行相应的优化，能够采用更高效的算法）
• 正确性高（更不容易出错）
• 可维护性强（更简短、语义上更清晰）

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

有些STL容器提供了与算法同名的成员函数，原因：

• 成员函数速度更快（对于关联容器，对数时间对比线性时间）
• 成员函数和容器的一贯行为保持一致（对于关联容器，采取等价而不是等值比较；对于map，只比较键而不是全部）

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

线性时间、相等性判断：

• count：用作存在性测试，统计数目
• find：用作存在性测试，返回第一个匹配位置，比count效率更高。因为一旦匹配到立刻返回（如果没找到，指向end）

对数时间（需排好序）、等价性判断：

• binary_search：仅用作存在性判断（只返回bool，表示是否存在）
• lower_bound：用作存在性判断，返回匹配的第一个位置（如果没找到，指向第一个适合插入的位置），所以需要检查返回位置的值是否与目标值等价，要手工实现等价
• upper_bound：同lower_bound（如果没找到，指向最后一个适合插入的位置）
• equal_range：用作存在性判断，返回一对迭代器，第一个为lower_bound返回值，第二个为upper_bound返回值。通过两者返回值是否相等来判断存在，通过两者距离来统计数目（distance）。

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

使用函数子（函数对象）的效率比函数高。

编译器将函数子模版在实例化过程中将operator()内联，避免了函数调用。此外，在实例化的过程中进行了一些正确性检查，减少了运行期出错的可能。

而函数由于通过函数指针来传参，每次调用时都产生一次间址访问开销。受到函数指针的抑制，即使函数被声明为inline，编译器总是不会进行优化。

47 避免产生“直写型”的代码

在一行中调用多个算法的复杂语句被称为直写型代码，这种代码虽然很容易便携，但难以阅读和理解。

应该将复杂语句分解成容易理解的简单语句，并适当地加上一些注释。

48 总是包含（#include）正确的头文件

C++没有规定STL中头文件的相互包含关系，不同的实现中包含方式可能不同，基于可移植性，应该包含全部依赖的头文件，而不依赖于它们之间的相互包含。

几乎所有标准STL容器都被声明在与之同名的头文件中。

除了accumulate、inner_product、adjacent_difference、partial_sum在<numeric>中外，其它算法都被声明在<algorithm>中。

特殊类型的迭代器（如istream_iterator、istreambuf_iterator）被声明在<iterator>中。

标准函数子（如less<T>）和函数子配接器（如not1）被声明在头文件<functional>中。

49 学会分析与STL相关的编译器诊断信息

STL相关语句在编译错误时会抛出一大堆乱七八糟的诊断信息。

简化诊断信息：

• 对于string的诊断信息，可将basic_string相关的长字符串替换成string。
• 对于内部类（下划线开头），可以将其模版内容删除掉。
• 由于vector和string的迭代器是指针，因此可将指针替换为迭代器。

50 熟悉与STL相关的Web站点

SGI：为STL所有组建提供了详尽的文档。有些实现超出了STL范畴。

STLport：提供可在超过20种编译器上使用的SGISTL改进版本，并提供调试模式（用法错误时抛出错误）。

Boost：提供了大量的C++库，并称为STL标准的候补。简称干儿子。