STL

STL表示C++标准库中与迭代器一起工作的那部分，其中包括标准容器(包含string)、iostream库的一部分、函数对象和各种算法。STL主要组成部分包括：容器、迭代器、算法、函数对象。
所有重载了**函数调用操作符(即operator()**)的类都是一个函数子类(functor class)。从这些类创建的对象被称为函数对象(function object)或函数子(functor)。在STL中，大多数使用函数对象的地方同样也可以使用实际的函数。

• 
  

  标准STL序列容器：vector、string、deque、list、forward_list(C11)、array(C11)。
  标准STL关联容器：set、multiset、map、multimap、unordered_set(C11)、unordered_multiset(C11)、unordered_map(C11)、unordered_multimap(C11)。
  标准的非STL容器，包括：bitset(include <bitset> )、valarray(include <valarray>)。其它STL容器：stack(include<stack> )、queue(include<queue> )和priority_queue((include<queue> ))。
  vector<char>可以作为string的替代。vector作为标准关联容器的替代。有时vector在运行时间和空间上都要优于标准关联容器。
  vector是默认应使用的序列类型，当需要频繁地在序列中间做插入和删除操作时，应使用list；当大部分插入和删除操作发生在序列的头部和尾部时， deque是应考虑的数据结构。

  queue和deque的区别：

  queue是容器适配器，queue底层默认容器是vector，底层也可以是list和deque

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

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

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

区间成员函数是指这样的一类成员函数，它们像STL算法一样，使用两个迭代器参数来确定该成员操作所执行的区间。如果不使用区间成员函数就得写一个显示的循环。
优先选择区间成员函数而不是其对应的单元素成员函数有三条充分的理由：区间成员函数写起来更容易，更能清楚地表达你的意图，而且它们表现出了更高的效率。

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

(1).要删除容器中有特定值的所有对象：如果容器是vector, string或deque，则使用erase-remove习惯用法；如果容器是list，则使用list::remove；如果容器是一个标准关联容器，则使用它的erase成员函数。
(2).要删除容器中满足特定判别式(条件)的所有对象：如果容器是vector, string或deque，则使用erase-remove_if习惯用法；如果容器是list，则使用list::remove_if；如果容器是一个标准关联容器，则使用remove_copy_if和swap，或者写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对它进行后缀递增。std::list的remove成员函数是STL中唯一一个名为remove并且确实删除了容器中元素的函数。
(3).要在循环内做某些(除了删除对象之外的)操作：如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次调用erase时，要用它的返回值更新迭代器；如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对迭代器做后缀递增。

    //关联容器    
    for (std::set<int>::iterator i = c3.begin(); i != c3.end();) {
        if (badValue(*i)) 
            c3.erase(i++); // 对坏值，把当前的i传给erase，递增i是副作用
        else ++i;                        // 对好值，则简单的递增i
    }
    //序列容器
    for (std::vector<int>::iterator i = c1.begin(); i != c1.end();) {
        if (badValue(*i)) {
            logFile << "Erasing " << *i << '\n';
            i = c1.erase(i); // 把erase的返回值赋给i，使i的值保持有效
        }
        else ++i;
    }

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

当涉及到STL容器和线程安全性时，你可以指望一个STL库允许多个线程同时读一个容器，以及多个线程对不同的容器做写入操作。你不能指望STL库会把你从手工同步控制中解脱出来，而且你不能依赖于任何线程支持。

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

许多string实现在背后使用了引用计数技术，这种策略可以消除不必要的内存分配和不必要的字符拷贝，从而可以提供很多应用程序的效率。如果你在多线程环境下使用了引用计数的string，那么注意一下因支持线程安全而导致的性能问题。vector的实现不允许使用引用计数，所以不会发生隐藏的多线程性能问题。

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

对于vector和string，增长过程是这样来实现的：每当需要更多空间时，就调用与realloc类似的操作。这一类似于realloc的操作分为四部分：(1).分配一块大小为当前容量的某个倍数的新内存。在大多数实现中，vector和string的容量每次以2的倍数增长，即，每当容器需要扩张时，它们的容量即加倍。(2).把容器的所有元素从旧的内存拷贝到新的内存中。(3).析构掉就内存中的对象。(4).释放旧内存。
reserve成员函数能使你把重新分配的次数减少到最低限度，从而避免了重新分配和指针/迭代器/引用失效带来的开销。避免重新分配的关键在于，尽早地使用reserve，把容器的容量设为足够大的值，最好是在容器刚被构造出来之后就使用reserve。
大小(size)和容量(capacity)之间的关系使我们能够预知什么时候插入操作会导致vector或string进行重新分配的动作，进而又使我们有可能预知什么时候一个插入操作会使容器中的迭代器、指针和引用失效。
通常有两种方式来使用reserve以避免不必要的重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少元素，则此时可以使用reserve。第二种方式是，先预留足够大的空间(根据你的需要而定)，然后，当把所有数据都加入以后，再去除多余的容量。

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

C++11中增加了shrink_to_fit成员函数，作为容器的成员函数被调用。

• 避免使用vector

在一个典型的实现中，储存在”vector”中的每个”bool”仅占一个二进制位，一个8位的字节可容纳8个”bool”。在内部，vector使用了与位域(bit field)一样的思想，来表示它所存储的那些bool，实际上它只是假装存储了这些bool。
位域与bool相似，它只能表示两个可能的值，但是在bool和看似bool的位域之间有一个很重要的区别：你可以创建一个指向bool的指针，而指向单个位的指针则是不允许的。指向单个位的引用也是被禁止的。
当你需要vector时，标准库提供了两种选择，可以满足绝大多数情况下的需求。第一种是deque。deque几乎提供了vector所提供的一切(没有reserve和capacity)，但deque是一个STL容器，而且它确实存储bool。当然deque中元素的内存不是连续的，所以你不能把deque中的数据传递给一个期望bool数组的C API。
第二种可以替代vector的选择是bitset。bitset不是STL容器，但它是标准C++库的一部分。与STL容器不同的是，它的大小(即元素的个数)在编译时就确定了，所以它不支持插入和删除元素。

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

相等的概念是基于operator==的。等价关系是以”在已排序的区间中对象值的相对顺序”为基础的。标准关联容器是基于等价而不是相等。
标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数(默认为less)来决定保持怎样的顺序。等价的定义正是通过该比较函数而确定的，因此，标准关联容器的使用者要为所使用的每个容器指定一个比较函数(用来决定如何排序)。如果该关联容器使用相等来决定两个对象是否有相同的值，那么每个关联容器除了用于排序的比较函数外，还需要另一个比较函数来决定两个值是否相等。(默认情况下，该比较函数应该是equal_to，但equal_to从来没有被用作STL的默认比较函数。当STL中需要相等判断时，一般的惯例是直接调用operator==，例如unordered_map对于自定义的数据类型，需要重载operator==，且需要重写仿函数)。

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

每当你要创建包含指针的关联容器时，一定要记住，容器将会按照指针的值进行排序。绝大多数情况下，这不会是你所希望的，所以你几乎肯定要创建自己的函数子类作为该容器的比较类型(comparison type)。

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

int test_item_20()
{
    std::set<std::string*, DereferenceLess> ssp; // 与std::set<std::string*, StringPtrLess> ssp;的行为相同
    ssp.insert(new std::string("Anteater"));
    ssp.insert(new std::string("Wombat"));
    ssp.insert(new std::string("Lemur"));
    ssp.insert(new std::string("Penguin"));

    for (auto it = ssp.cbegin(); it != ssp.cend(); ++it) {
        fprintf(stdout, "%s\n", (**it).c_str());
    }
    return 0;
}

如果你有一个包含智能指针或迭代器的容器，那么你也要考虑为它指定一个比较类型。对指针的解决方案同样也适用于那些类似指针的对象。就像DereferenceLess适合作为包含T*的关联容器的比较类型一样，对于容器中包含了指向T对象的迭代器或智能指针的情形，DereferenceLess也同样可用作比较类型。

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

比较函数的返回值表明的是按照该函数定义的排列顺序，一个值是否在另一个之前。相等的值从来不会有前后顺序关系，所以，对于相等的值，比较函数应当始终返回false。对set和map确实是这样，因为这些容器不能包含重复的值。对multiset和multimap也是这样。从技术上来说，用于对关联容器排序的比较函数必须为它们所比较的对象定义一个”严格的弱序化”(strict weak ordering)。(对于传递给像sort这类算法的比较函数也有同样的限制。)任何一个定义了”严格的弱序化”的函数必须对相同值的两个拷贝返回false。

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

像所有的标准关联容器一样，set和multiset按照一定的顺序来存放自己的元素，而这些容器的正确行为也是建立在其元素保持有序的基础之上的。如果你把关联容器中的一个元素的值改变了(比如把10改为1000)，那么，新的值可能不在正确的位置上，这将会打破容器的有序性。

    std::map<int, std::string> m{ { 0, "xxx" } };
    //m.begin()->first = 10; // build error, map的键不能修改

    std::multimap<int, std::string> mm{ { 1, "yyy" } };
    //mm.begin()->first = 10; // build error, multimap的键同样不能修改

    std::set<int> s{ 1, 2, 3 };
    //*(s.begin()) = 10; // build error, set的键不能修改
    const_cast<int&>(*s.begin()) = 10; // 强制类型转换

    std::vector<int> v{ 1, 2, 3 };
    *v.begin() = 10;

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

在排序的vector中存储数据可能比在标准关联容器中存储同样的数据要耗费更少的内存，而考虑到页面错误的因素，通过二分搜索法来查找一个排序的vector可能比查找一个标准关联容器要更快一些。当然，对于排序的vector，最不利的地方在于它必须保持有序。
插入和删除操作对于vector来说是昂贵的，但对于关联容器却是廉价的。这就是为什么只有当你知道”对数据结构的使用方式是：查找操作几乎从不跟插入和删除操作混在一起”时，再考虑使用排序的vector而不是关联容器才是合理的。否则，使用排序的vector而不是标准关联容器几乎肯定是在浪费时间。

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

当向映射表中添加新元素时，要优先选用insert，而不是operator[]；而从效率和美学的观点考虑，结论是：当更新已经在映射表中的元素的值时，要优先选择operator[]。

• iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

• [x] 使用distance和advance将容器的const_iterator转换成iterator

    typedef std::deque<int> IntDeque;
    typedef IntDeque::iterator Iter;
    typedef IntDeque::const_iterator ConstIter;
  
    IntDeque d(5, 10);
    ConstIter ci;
    ci = d.cbegin() + 1; // 使ci指向d
    Iter i(d.begin());
    std::advance(i, std::distance<ConstIter>(i, ci));
  

  std::distance用以取得两个迭代器(它们指向同一个容器)之间的距离；std::advance则用于将一个迭代器移动指定的距离。

• [x] 确保目标区间足够大 ```cpp int transmogrify(int x) { return (x + 1); }

int test_item_30() { std::vector values{ 1, 2, 3 }; std::vector results; results.reserve(results.size() + values.size()); // 可避免内存的重新分配 //std::transform(values.cbegin(), values.cend(), results.end(), transmogrify); // 错误，segmentation fault std::transform(values.cbegin(), values.cend(), std::back_inserter(results), transmogrify); // 正确 // 在内部，std::back_inserter返回的迭代器将使得push_back被调用，所以back_inserter可适用于所有提供了push_back方法的容器

std::list<int> results2;
std::transform(values.cbegin(), values.cend(), std::front_inserter(results2), transmogrify);
// std::front_inserter在内部利用了push_front，所以front_inserter仅适用于那些提供了push_front成员函数的容器
return 0;

}

无论何时，如果所使用的算法需要指定一个目标区间，那么必须确保目标区间足够大，或者确保它会随着算法的运行而增大。要在算法执行过程中增大目标区间，请使用插入型迭代器，比如ostream_iterator或者由back_inserter、front_inserter和inserter返回的迭代器。<br />

- [x] **了解各种与排序有关的选择**

(1).如果需要对vector、string、deque或者数组中的元素执行一次完全排序，那么可以使用sort或者stable_sort。<br />(2).如果有一个vector、string、deque或者数组，并且只需要对等价性最前面的n个元素进行排序，那么可以使用partial_sort。<br />(3).如果有一个vector、string、deque或者数组，并且需要找到第n个位置上的元素，或者，需要找到等价性前面的n个元素但又不必对这n个元素进行排序，那么，nth_element正是你所需要的函数。<br />(4).如果需要将一个标准序列容器中的元素按照是否满足某个特定的条件区分开来，那么，partition和stable_partition可能正是你所需要的。<br />(5).如果你的数据在一个list种，那么你仍然可以直接调用partition和stable_partition算法；你可以用list::sort来替代sort和stable_sort算法。但是，如果你需要获得partial_sort或nth_element算法的效果，那么，你可以有一些间接的途径来完成这项任务。

- [x] **对包含指针的容器使用remove这一类算法时要特别小心**

当容器中存放的是指向动态分配的对象的指针的时候，应该避免使用remove和类似的算法(remove_if和unique)。<br />如果容器中存放的不是普通指针，而是具有引用计数功能的智能指针，那么就可以直接使用erase-remove的习惯用法。
```cpp
class Widget33 {
public:
    bool isCertified() const { return true; }
};

// 如果*pWidget是一个未被验证的Widget33,则删除该指针，并把它置成空
void delAndNullifyUncertified(Widget33*& pWidget)
{
    if (!pWidget->isCertified()) {
        delete pWidget;
        pWidget;
    }
}

int test_item_33()
{
    std::vector<Widget33*> v;
    for (int i = 0; i < 5; ++i) v.push_back(new Widget33);

    // 删除那些指向未被验证过的Widget33对象的指针，会资源泄露
    v.erase(std::remove_if(v.begin(), v.end(), std::not1(std::mem_fun(&Widget33::isCertified))), v.end());

    // 一种可以消除资源泄露的做法
    // 将所有指向未被验证的Widget33对象的指针删除并置成空
    std::for_each(v.begin(), v.end(), delAndNullifyUncertified);
    // 删除v中的空指针，必须将0转换成一个指针，这样C++才能正确推断出remove的第三个参数类型
    v.erase(std::remove(v.begin(), v.end(), static_cast<Widget33*>(0)), v.end());

    // 使用智能指针可防止资源泄露
    std::vector<std::shared_ptr<Widget33>> v2;
    for (int i = 0; i < 5; ++i) v2.push_back(std::make_shared<Widget33>());
    // 下面语句需要编译器必须能够把智能指针类型std::shared<Widget33>隐式转换为对应的内置指针类型Widget33*才能通过编译
    //v2.erase(std::remove_if(v2.begin(), v2.end(), std::not1(std::mem_fun(&Widget33::isCertified))), v2.end());

    return 0;
}

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

要求排序区间的STL算法：binaray_search、lower_bound、upper_bound、equal_range、set_union、set_intersection、set_difference、set_symmetric_difference、merge、inplace_merge、includes。

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

std::for_each和std::accumulate在两个方面有所不同：首先，名字accumulate暗示着这个算法将会计算出一个区间的统计信息。而for_each听起来就好像是对一个区间的每个元素做一个操作。

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

4个标准的函数配接器(not1、not2、bind1st、bind2nd，后两个，在C++11中已不推荐使用)都要求一些特殊的类型定义，那些非标准的、与STL兼容的配接器通常也是如此。
STL函数对象是C++函数的一种抽象和建模形式，而每个C++函数只有一组确定的参数类型和一个返回类型。所以，STL总是假设每个函数子类只有一个operator()成员函数，并且其参数和返回类型应该吻合unary_function或binary_function的模板参数。

• 理解ptr_fun、men_fun和mem_fun_ref的来由

std::ptr_fun：将函数指针转换为函数对象。
std::mem_fun：将成员函数转换为函数对象(指针版本)。
std::mem_fun_ref：将成员函数转换为函数对象(引用版本)。

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

有些STL容器提供了一些与算法同名的成员函数。比如，关联容器提供了count、find、lower_bound、upper_bound和equal_range，而list则提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下，你应该使用这些成员函数，而不是相应的STL算法。
这里有两个理由：第一，成员函数往往速度快；第二，成员函数通常与容器(特别是关联容器)结合得更加紧密，这是算法所不能比的。原因在于，算法和成员函数虽然有同样的名称，但是它们所做的事情往往不完全相同。
在sort算法与list的sort函数之间有一个很重要的区别是，前者根本不能被应用到list容器上，这是因为，list的迭代器是双向迭代器，而sort算法要求随机访问迭代器。在merge算法和list的merge函数之间也存在行为上的隔阂：merge算法是不允许修改其源区间的，而list::merge则总是在修改它所操作的链表。

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

在选择具体的查找策略时,由迭代器指定的区间是否是排序的，这是一个至关重要的决定条件。如果区间是排序的，那么通过binary_search、lower_bound、upper_bound和equal_range，你可以获得更快的查找速度(通常是对数时间的效率)。如果迭代器并没有指定一个排序的区间，那么你的选择范围将局限于count、count_if、find以及find_if，而这些算法仅能提供线性时间的效率。

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

以函数对象作为STL算法的参数，这种做法提供了包括效率在内的多种优势。从代码被编译器接受的程度而言，它们更加稳定可靠。当然，普通函数在C++中也是非常实用的，但是就有效使用STL而言，函数对象通常更加实用一些。

struct StringSize : public std::unary_function<std::string, std::string::size_type> {
    std::string::size_type operator()(const std::string& s) const
    {
        return s.size();
    }
};

int test_item_46()
{
    std::set<std::string> s{ "abc", "cde", "xyzw" };
    std::transform(s.begin(), s.end(), std::ostream_iterator<std::string::size_type>(std::cout, "\n"), std::mem_fun_ref(&std::string::size)); // 3 3 4，普通函数

    std::transform(s.begin(), s.end(), std::ostream_iterator<std::string::size_type>(std::cout, "\n"), StringSize()); // 3 3 4, 函数对象

    return 0;
}

• 总是包含(#include)正确的头文件

(1). 几乎所有的标准STL容器都被声明在与之同名的头文件中，比如vector被声明在中，list被声明在中，等等。但是和