3.1 指针的算术运算

容器
Vector - 连续的存储块
List - 双向链表构成的存储块

考虑要实现一种通用的查找容器的方法find

3.1.1 Step 1 我们要实现一个vector<int>容器的元素查找

很容易实现，find 函数中轮询vector里面所有元素，找到就返回

int* find(const vector<int> &vec, int value)
{
    for( int ix = 0 ; ix < vec.size(); ++ix)
    {
        if (vec[ ix ] == value)
        {
            return &vex[ ix ];
        }
    }

    return std::nullptr;
}

3.1.2 Step 2 实现任意类型的vector元素的查找

这个时候我们引入了模板函数

template<typename elemType>
elemType* find(const vector<elemType> &vec, 
                const elemType& value)
{
    for( int ix = 0 ; ix < vec.size() ; ++ix)
    {
        if ( vec[ix] == value)
        {
            return &vec[ix];
        }
    }

    return std::nullptr
}

你可以用这个函数查找任何诸如vector<float>之类的容器了

3.1.3 Step 3 我要用同一个函数来实现数组的查找，可行么？

这个时候vector要在find函数里面不可见，所以我们想到了指针

template<typename elemType>
elemType* find(const elemType *array, int size,
                const elemType& value)
{
    if ( ! array || size < 1 )
    {
        return 0;
    }

    for ( int ix = 0 ; ix < size ; ++ix )
    {
        if ( vec[ix] == value )
        {
            return &vec[ix]
        }
    }

    return std::nullptr;
}

如果是数组，我们只要传递数组的首地址即可；如果是vector，只要传递容器中数据的首地址也能做到

3.1.4 Step 4 如果我现在还要是先list的查找呢

那就有点困难了，因为list底层是一个链表结构，不是连续内存，find函数这个时候就失效了。

3.2 了解Iterator

简单来说Iterator也是一组类，但是却可以实现和指针相同的语法，也提供内置的运算符操作(*, !=, ++ )。
那么我们怎么样来定义这样的一个迭代器类型呢？我们可能有vector<xxx>，有list<xxx>，怎么来进行区分？
标准库中是这么来定义的，

std::vector<std::string> svec;
std::vector<std::string>::iterator iter = svec.begin();

这里的iter指向vector<string>容器的第一个元素，我们前面说了你可以把它当成指针来用，比如说取第一个string的内容：*iter；指向下一个元素；iter++
这样，看来我们就能解决前一节中的最后一个问题了

template<typename IteratorType, typename elemType >
IteratorType find(IteratorType first, IteratorType last, 
                const elemtType &value)
{
    for (; first != last; ++first)
    {
        if(*first == value)
        {
            return first;
        }
    }
    return last;
}

这个时候，如果你要查找的是一个数组你可以这么写

    const inst asize = 8;
    int ia[ asize ] = { 1, 1, 2, 3, 5, 8, 13, 21};

    int* pia = find( ia, ia+asize, 1024);

vector可以这样

    vector<int> ivec;
    vector<int>::iterator it(ia, ia + asize); 
    it = find(ivec.begin, ivec.end(), 1024);

list可以这样

    list<int> ilist;
    list<int>::iterator iter(ia, ia + asize);
    iter = find(ilist.begin(), ilist.end(), 1024);

看样子大功告成了。

常用的泛型算法

• 搜索算法： find(), count(), etc;
• 排序及次序整理算法：merge(), sort(), reverse(), etc;
• 赋值、删除、替换算法：copy(), remove(), swap(), etc；
• 关系算法：equal(), include();
• 生成（generation）与质变（mutation）算法： fill(), for_each(), generate(), transform();
• 数值算法：accumulate(), partial_sum();
• 集合算法：set_union(), set_difference()

3.3 顺序型容器

3.5 设计一个泛型算法（Generic Algorithm）

3.5.1 从问题开始

Step1， 我需要设计一个算法，输入是一个vector<int>，输出是一个新的vector，包含了原vector中所有小于10的值。
很容易做到，

std::vector<int> less_than(std::vector<int>& vec, int level)
{
    std::vector<int> nvec;
    for（ int ix = 0; ix < vec.size(); ++ix）
    {
        if(vec[ix] < level)
        {
            nvec.push_back(vec[ix]);
        }
    }
    return nvec;
}

Step 2, 现在我们增加一些难度，允许用户指定不同的操作，比如说过滤大于一个值的元素，或者过滤等于一个值的元素。
一种解决的办法就是，增加第三个参数，一个函数指针，这第三个入参就是用户可以指定的操作，

vector<int> filter_ver1(const vector<int>& vec, 
                    int filter_value,
                    bool (*pred)( int, int))
{
    vector<int> nvec;

    for( int ix = 0 ; ix < vec.size(); ix++)
    {
        if(pred(vec[ix], filter_value))
        {
            nvec.push_back(vec[ix]);
        }
    }

    return nvec;
}

这个时候用户可以自己定义小于操作

bool less_than(int a, int b)
{
  return a < b ? true : false;
}

3.5.2 函数对象

函数对象实际上是某种类的实例对象，这种对象对函数调用运算符()进行了重载操作，而这个时候运算符()重载函数通常是inline的，从效率上来说要优于函数指针。
标准库定义了很多函数对象

我们来看一个使用这些运算符的例子，加入说我要对一个vector里的元素以降序排序，我们可以这么来写

#include <functional>
sort( vec.begin(), vec.end(), greater<int>());

• 前两个参数标记范围；
• 第三个参数告知操作；

3.5.3 函数对象适配器（Function Object Adapter）

我们再回到我们要实现这个泛型算法filter，我们可以使用标准库中使用的这些函数对象了，
Step 3， 使用标准库提供的函数对象less<int>来作为filter的第三个入参，
除此之外我们还希望用函数find_if来替代原来用for循环遍历整个vector的方式，但是我们知道find_if的第三个入参（用来作为查找条件的）应该是一个一元操作函数对象，只接受一个输入参数；但我们这里的sort函数是一个二元操作函数对象，那我们该怎么实现？

std::vector<int> filter(std::std::vector<int>& vec, int val, less<int>& lt)
{
    std::vector<int> nvec;
    
    std::vector<int>::const_iterator iter = vec.begin();
    while(( iter = 
                find_if(iter, vec.end(), 
                    bind2nd(lt, value)) != vec.end())
    {
        nvec.push_back(*iter);
        iter++;
    }
    return nvec;
}

这个时候就引出了本节所要介绍的一个新东西了，叫函数对象适配器，这个适配器会对普通的函数对象进行修改，来满足用户所需。
比如说这个例子里用到的绑定适配器（binder adapter）可以将函数对象的参数绑定到一些特定值，这样我们的二元操作符sort就可以变成我们所需的一元的了。

NOTE: C++11以后引入了std::bind函数，使得适配器操作起来更加灵活

Step4， 消除filter()与vector的元素类型，让我们的泛型算法更加通用
使用模板函数，

template<typename InputIterator, typename OutputIterator
        typename ElemType, typename Comp>
OutputIterator filter(InputIterator first, InputIterator last, 
                OutputIterator at, ElemType& val, Comp pred)
{
    while((first = find_if(first, last, bind2nd(pred,val))) != last)
    {
        *at++ = *first++;
    }
    return at;
}

• 首先，要消除filter的返回值类型vector<int>，如前所述的，我们只能返回迭代器；这里定义了返回值迭代器类型OutputIterator；
• 然后，消除第一个入参的类型vector<int>，也使用迭代器来标记过滤的范围；
• 之后，加一个参数at，标记filter的结果保存的目的地址；
• 接着是查找对象以及区别算法的定义。

NOTE: 后面章节中有另一种解决方法，叫做插入迭代器适配器（insert iterator adapter）

这里还要介绍另外一种迭代器，交租哦negator，它会对函数对象的true/false值取反。

3.9 如何使用Iterator Inserter

3.9.1 笨一点的调用泛型算法filter的方法

我们再回到3.5节中最后实现的filter函数，用户使用这个函数的时候，可以这么来做,

void main()
{
    int ia[5] = {1, 4, 2, 0, 9, 8};
    std::vector<int> ivec( ia, ia+5 );

    std::vector<int> ovec(5);

    filter(ivec.begin(), ivec.end(), ovec.begin(), 3, greater<int>());
}

上述的程序中，由于filter函数内部是直接给目标容器的迭代器进行赋值操作，所以调用的时候，需要满足如下的这些条件

• 预先定义目标容器必须足够大，这样才足以填充filter函数中的每个过滤出来的结果；
  也就是说我们可能需要定义一个和源容器一样大的目的容器，预留足够的空间，这个显然是会带来内存空间的浪费的。

那么我们可不可以定义一个空的容器呢？我们知道，进行赋值操作（assignment）的时候，容器并不会自动扩容，也就是空的容器会一直保持为空，这样调用的时候必然会报错；
那么我们可不可以使用类似push_back这样的操作来替换赋值操作呢？这样的话，我们就不需要定义一个固定大小的目标容器了，答案是有的，这就是所谓的迭代器插入适配器（insertion adapter）,

3.9.2 借助Iterator Inserter之后的聪明方法

借助back_inserter，

filter(ivec.begin(), ivec.end(), back_inserter(ovec), 3, greater<int>());

3.10 使用iostream iterator

这节首先我们考虑要实现一个新的问题，

• 从标准输入读取字符，保存到一个vector容器中；
• 然后进行排序；
• 然后通过标准输出到设备上；

3.10.1 首先还是笨点的办法

很容易理解，标准输入都进来，写入text，然后排序，然后写出去，

int main()
{
    std::string word;
    std::vector<std::string> text;

    while (std::cin >> word)
    {
        text.push_back(word);
    }

    std::sort(text.begin(), text.end());

    for (int ix = 0; ix < text.size(); ix++)
    {
        std::cout << text[ix] << std::endl;
    }
}

3.10.2 借助标准库的iostream迭代器的聪明方法

这里用到了iostream迭代器

• 首先我们考虑使用copy算法，源是cin，目的是text；
• copy算法也有三个入参，前两个是源的范围（类似指针的范围）；最后一个是text，这里我们借助back_inserter来把copy内部的赋值操作转换成了push_back操作；
• 然后是输出，定义一个ostream_iterator，用于作为copy的目的；

int main()
{
    std::istream_iterator<std::string> is(std::cin);
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(std::cout, " ");
    std::copy(text.begin(), text.end(), os);
}

3.10.3 来看看上述第二种方法带来的妙用吧

假如说这个时候我又有新的需求，不再从标准输入读入，从标准输出写出；而是要从文件读入，文件写出，该怎么做？
很简单，只要做到如下两点

• istream_iterator绑定到ifstream对象
• ostream_iterator绑定到ofstream对象
  这就大功告成了

int main()
{
    std::ifstream in_file("in.txt");           // 新建ifstream和ofstream
    std::ofstream out_file("out.txt");

    std::istream_iterator<std::string> is(in_file);   // in_file替换std::cin
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(out_file, " ");  // out_file替换std::cout
    std::copy(text.begin(), text.end(), os);
}

这就是泛型带来的优势，一套代码，满足你各种需求。