这是个人阅读Effective STL所做的读书笔记第五部分，包含《Effective STL》条款41~条款50的笔记内容，Effective STL读书笔记此篇完结。

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

事实上unary_function、binary_function已经在C++17中删除，对unary_function和binary_function进行适配的ptr_fun函数模板也已经在C++17中删除，当然在C++17完全支持的编译器之前的编译器版本ptr_fun这些仍然可以正常使用。
mem_fun和mem_fun_ref适用于当自定类容器在使用一些STL方法时，需要使用该自定类的成员方法来操作时，例如书上所举的for_each的例子：

class Widget
{
public:
    void test();
};

vector<Widget> vw;
for_each(vw.begin(), vw.end(),  mem_fun_ref(&Widget::test));

list<Widget*> lpw;
for_each(lpw.begin(), lpw.end(), mem_fun(&Widget::test));

关于这三个函数模板的使用时机，正如书上所说的，ptr_fun在使用STL函数时，如果编译不通过则需要考虑使用ptr_fun；而如果在传递成员函数指针给STL方法时，如果不加mem_fun或者mem_fun_ref做适配，编译则一定不会通过。

条款42：确定less表示operator<

由于less<T>默认使用类型T的operator<，关联容器默认使用less<T>来排序容器内元素，所以如果单独给类型T特化了less<T>而不使用T的operator<，会导致类型T的所有关联容器都不使用operator<来进行排序。所以比较合理的做法是如果需要特殊方法排序的关联容器，则自定义一个排序仿函数类，构造关联容器时提供该仿函数类型作为容器模板参数。

class Widget
{
public:
    Widget(size_t iWeight, size_t iMaxSpeed) :
        m_iWeight(iWeight), m_iMaxSpeed(iMaxSpeed)
    {}
    size_t weight() const
    {
        return m_iWeight;
    }
    size_t maxSpeed() const
    {
        return m_iMaxSpeed;
    }
private:
    size_t m_iWeight;
    size_t m_iMaxSpeed;
};

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

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

...
multiset<Widget> widgets;    //以weight()排序
...
multiset<Widget, MaxSpeedCompare> widgets;     // 以maxSpeed()排序
...

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

三个理由使用算法调用代替手写循环：
效率：算法通常比程序员产生的循环更高效
正确性：写循环时比调用算法更容易产生错误
可维护性：算法通常使代码比相应的显示循环更干净、更直观
这里书上提到了一个手写循环可能比使用算法好的情况，找出vector中第一个比x大又比y小的元素，使用循环的实现：

vector<int>::iterator i = v.begin();
for (; i != v.end(); ++i)
{
    if (*i > x && *i < y)
        break;
}

若使用算法调用，书上的写法：

vector<int>::iterator i = find_if(v.begin(), v.end(),
    compose2(logical_and<bool>(),
        bind2nd(greater<int>(), x),
        bind2nd(less<int>(), y)));

或者

template<typename T>
class BetweenValues : public unary_function<T, bool>
{
public:
    BetweenValues(const T& lowValue, const T& highValue) :
        lowVal(lowValue), highVal(highValue)
    {}
    bool operator()(cont T& val) const
    {
        return val > lowVal && val < highVal;
    }
private:
    T lowVal;
    T highVal;
};

...
vector<int>::iterator i = find_if(v.begin(), v.end(),
    BetweenValues<int>(x, y));
...

这往往是更长的、更不容易理解的代码，这也成为我们平时选择循环还不是算法的一个原因，这一问题在c++11中得到改善。在C++ 11中引入的lambda给这种情况带来了更简洁更方便的解决方法：

1 2	vector<int>::iterator i = find_if(v.begin(), v.end(), [&x, &y](int i) { return i > x && i < y; });

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

对于标准关联容器，成员函数而不是同名算法的几个好处：

成员函数拥有对数时间性能，同名算法只有线性时间性能
成员函数使用等价来作为“相同”这一判断标准，这也是关联容器的默认定义，而算法则使用相等
对于map和multimap来说，成员函数自动地只处理key而不是pair<key,value>

对于list来说，算法中的remove、remove_if、unique、sort、merge和reverse都涉及拷贝对象，而成员函数只需要操作连接节点的指针；同时对于remove、remove_if和unique来说，算法中的版本如果你想要删除掉之后的元素，需要调用erase做删除，而成员函数的remove、remove_if和unique是真的去掉了元素，不需要再接erase调用；算法sort由于需要的是随机访问迭代器，list的双向迭代器并不能作用于sort之上，所以只能使用成员版本的sort；算法merge不修改源list，而成员函数的merge将会在本容器上合并入参容器，并将该入参容器置空。

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

	算法		成员函数
	无序区间	有序区间	set或map	multiset或multimap
期望值是否存在	find	binary_search	count	find
期望值是否存在？如果有，第一个等于这个值的位置在哪里？	find	equal_range	find	find或lower_bound
第一个不在期望值之前的对象在哪里？	find_if	lower_bound	lower_bound	lower_bound
第一个在期望值之后的对象在哪里？	find_if	upper_bound	upper_bound	upper_bound
有多少对象等于期望值？	count	equal_range，然后distance	count	count

本节主要讨论的就是以上表格里的内容：对于无序区间来说只能选择算法中的find、find_if和count来完成目标对象的查找和统计，并且这些方法都是消耗线性时间的。
对于有序区间来说可以选择性能更好的binary_search、equal_range、lower_bound和upper_bound，这些算法消耗对数时间，但要注意这些方法都使用等价来进行搜索。这里要说明下“期望值是否存在？如果有，第一个等于这个值的位置在哪里？”为何要使用equal_range而不是lower_bound。
使用lower_bound的情况大致如下：

vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);
if( i != vw.end() && *i == w )    //找到了对象w的位置
{
...
}

但是由于lower_bound使用的是等价的判断，*i == w这个判断式可能并不为真，这将导致这个判断失效。所以比较简便的方式是使用equal_range：

typedef vector<Widget>::iterator VWIter;
typedef pair<VWIter, VWIter> VWIterPair;
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if( p.first != p.second )        //找到了w，其第一个位置位于p.first上
{
...
}

这段代码只使用等价，所以总是正确。
关联容器由于提供了搜索成员函数，且这些成员搜索函数更快行为更自然，所以它们往往是比algorithm算法更好的选择。要注意几点：
set和map由于不允许重复键值，所以查找一个键值是否存在，count也许更为方便。
同样是在“期望值是否存在？如果有，第一个等于这个值的位置在哪里？”情景下，multiset和multimap使用find可能返回的并不是给定值的第一个元素，所以可以使用lower_bound来完成这个工作。

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

理由有以下几个：
效率上来说，由于大部分编译器不会试图去内联通过函数指针调用的函数，而函数对象的operate()可以进行内联调用，所以对于同样的函数代码来说，在算法方法中函数对象的效率可能高于函数。不过个人观点来看，这一论点是基于这个函数可以被内联的基础之上的，对于一些过长或者过于复杂的函数来说，虽然我们声明了inline，但如果编译器认为该函数不能内联，该函数最后也就不会产生内联，那么此优势也就不将存在。当然这个优势在可以被内联的函数上来说是存在的。
另一个原因是某些STL平台处理const成员函数时存在bug，所以可以使用函数对象来代替。
最后一个原因是对于使用函数模板的场景，形如以下代码：

template<typename FPType>
FPType average(FPType val1, FPType val2)
{
    return (val1 + val2) / 2;
}

template<typename InputIter1, typename InputIter2>
void writeAverages(InputIter1 begin1, InputIter1 end1, InputIter2 begin2, std::ostream& s)
{
    std::transform(begin1, end1, begin2,
        std::ostream_iterator<typename std::iterator_traits<InputIter1>::value_type>(s, "\n"),
        average<typename std::iterator_traits<InputIter1>::value_type>);
}

如果有其他同名的averge但是函数签名和个数都不同的函数模板，编译器将不知道该使用哪个造成编译不过，解决方法是使用函数对象：

template<typename FPType>
struct Average : public std::binary_function<FPType, FPType, FPType>
{
    FPType operator()(FPType val1, FPType val2) const
    {
        return average(val1, val2);
    }
};

template<typename InputIter1, typename InputIter2>
void writeAverages(InputIter1 begin1, InputIter1 end1,
        InputIter2 begin2, std::ostream& s)
{
    std::transform(begin1, end1, begin2,
            std::ostream_iterator<typename std::iterator_traits<InputIter1>::value_type>(s, "\n"),
            Average<typename std::iterator_traits<InputIter1>::value_type>());
}

由于Average模板类里声明了averge的调用方式，将不会造成average的调用歧义，这样编译器只要去寻找符合这个函数签名的函数模板即可。

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

“It’s a software engineering truism that code is read more often than it is written. Equally well established is that software spends far more timing in maintenance than it does in development.”
这也是我平时坚持的，无法被他人理解的代码无法被维护，无法维护的软件不值得拥有。这里书上举了个例子：

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());

如果把这段代码写成一句：

1	v.erase(remove_if(find_if(v.rbegin(), v.rend(), something).base(), v.end(), something)), v.end());

如果是刚从学校毕业的我来看这句语句，肯定先骂开了，“又臭又长，阅读这代码的人得来回看几遍”，但对于已经毕业这些年的现在的我来看，这语句总比那些手写几个循环然后还写错了的强。

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

强调如果使用stl部件时需要写明引用的头文件，如果没有写明所使用头文件将造成移植性的问题，比如我在gcc环境里编译如下代码：

#include <iostream>
int main()
{
    std::string strTest;
    return 0;
}

g++将正常编译通过，这是由于在gcc的stl实现里iostream的头文件包含层次里包含了string，当这段代码移植到其他平台时可能因为其stl实现的不同导致编译无法通过。
头文件包含的快速概要：

几乎所有容器都在同名头文件里， vector在<vector>中声明，list在<list>中声明，例外的是multiset是在<set>中声明，multimap在<map>中声明。
accumulate、inner_product、adjacent_difference和partial_sum这四个算法在<numeric>中声明，其他算法都在<algorithm>中
特殊迭代器都在<iterator>中
标准仿函数、仿函数适配器在<functional>中

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

本节主要解释了使用STL在编译时可能遇到的一些问题，由于STL中的内部实现可能造成编译器诊断信息的难懂，比如书上提到的string的STL实现basic_string，当string使用出错时，编译器诊断信息会报出大量的类似std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >的错误，造成理解上的难度；再比如书上提到的map的从const_iterator赋值到iterator的错误，编译器会报出一堆std::_Tree<…>的错误，且一般如果该map嵌套包含了更复杂的stl容器时，这些_Tree尖括号报错信息可能会更长，也更加难懂。一个有经验的STL程序员应该能快速将这些信息替换降低到可以理解的东西，书上还提到了几个常见的STL编译器信息：

对于vector和string，迭代器有时是指针，如果迭代器出现了错误，编译器报错信息可能会设计指针类型。
提到back_insert_iterator、front_insert_iterator或insert_iterator的消息经常意味着你错误调用了back_inserter、front_inserter或inserter
编译器诊断信息包括binder1st或binder2nd，或许错误地使用了bind1st或bind2nd
输出迭代器（ostream_iterator、ostreambuf_iterators、和back_inserter、front_inserter和inserter返回的迭代器）在赋值操作符内部做输出或输入工作，所以这些迭代器使用出错时编译器报错可能发生在这些赋值操作符内
编译器报出STL算法实现内部的错误时，你可能给这些算法传错类型
使用STL组件而编译器不识别这些组件时，你可能没有包含对应的头文件

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

SGI http://www.sgi.com/tech/stl/
SGI于2016年被HPE（Hewlett Packard Enterprise）收购，SGI官网原先提供的SGI STL实现源码于2018年开始不再向外提供
STLport http://www.stlport.org/
STLport作为SGI STL实现的移植性改良版本，由于SGI不再提供实现源码也逐渐没落
Boost http://www.boost.org/
作为C++标准的实验室，boost社区一直保持着稳定良好的生态环境，如果你发现当前STL中有不支持的功能，也许你应该来boost看看

Joshua's Blog

Effective STL 读书笔记（五）