STL——前闭后开区间表示法和function call 操作符

前开后闭开区间表示法[)

任何一个STL算法，都需要获得由一对迭代器（泛型指针）所标示的区间，用以表示操作范围，这一对迭代器所标示的是个所谓的前闭后开区间，以[first,last)表示，也就是说，整个实际范围从first开始，直到last-1.迭代器last所指的是“最后一个元素的下一位置”。这种off by one（偏移一格，或说pass the end）的标示法，带来了很多方便，例如下面两个STL算法的循环设计，就显得干净利落：

template<class InputIterator,class T>
InputIterator find(InputIterator first,InputIterator last,const T&value)
{
    while(first!=last&&*first!=value) ++first;
    return first; //返回迭代器
}

template <class InputIterator,class Function>
Function for_each(InputIterator first,InputIterator last,Function f)
{
    for(;first!=last;++first)
        f(*first);
    return f;
}

　　前闭后开区间示意图如下（注意，元素之间无需占用连续内存空间）：

function call 操作符

函数调用操作（C++语法中的左右小括号）也可以被重载。

许多STL算法都提供了两个版本，一个用于一般情况（例如排序时以递增方式排列），一个用于特殊情况（例如排序时由使用者指定以何种特殊关系进行排列），像这种情况，需要用户指定某个条件或某个策略，而条件或策略的背后由一整组操作构成，便需要某种特殊的东西来代表这“一整组操作”。

代表“一整组操作“的，当然是函数，过去C语言时代，欲将函数当做参数传递，唯有通过函数指针才能达成，例如：

#include<iostream>
#include<cstdlib>
using namespace std;

int fcmp(const void* elem1,const void* elem2);

int main()
{
    int ia[10]={32,92,67,58,10,4,25,52,59,54};
    for(int i=0;i<10;i++)
        cout<<ia[i]<<" ";
    cout<<endl;
    qsort(ia,sizeof(ia)/sizeof(int),sizeof(int),fcmp);

    for(int i=0;i<10;i++)
        cout<<ia[i]<<" ";
    cout<<endl;
}

int fcmp(const void* elem1,const void* elem2)
{
    const int *i1=(const int*)elem1;
    const int *i2=(const int*)elem2;
    if(*i1<*i2)
        return -1;
    else if(*i1==*i2)
        return 0;
    else if(*i1>*i2)
        return 1;
}

　　运行结果：

但是函数指针有缺点，最重要的是它无法持有自己的状态（所谓局部状态，local states），也无法达到组件技术中的可适配性（adaptability）——也就是无法再将某些修饰条件加诸于其上面而改变其状态。

qsort函数：
功 能： 使用快速排序例程进行排序
头文件：stdlib.h
用 法： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
参数： 1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针，用于确定排序的顺序

为此，STL算法的特殊版本所接受的所谓“条件”或“策略”或“一整组操作”，都以仿函数形式呈现。所谓仿函数（functor）就是使用起来像函数一样的东西。如果你针对么某个class进行operator()重载，它就是一个仿函数，至于要成为一个可配接的仿函数，还需要做一些额外的努力。

#include<iostream>
//注意，不能使用using namespace std 不然plus和minus会有歧义
using std::cout;
using std::endl;

template <class T>
struct plus
{
    T operator()(const T& x,const T& y) const {return x+y;}
};

template <class T>
struct minus
{
    T operator()(const T& x,const T& y)const {return x-y;}
};

int main()
{
    plus<int> plusObj;
    minus<int> minusObj;
    cout<<plusObj(3,5)<<endl;
    cout<<minusObj(3,5)<<endl;
    //注意下面的调用，不要忘记调用默认构造函数的小括号以及函数对象调用参数的小括号
　　//以下直接产生仿函数的临时对象（第一对小括号），并调用之（第二对小括号）
    cout<<plus<int>()(43,50)<<endl;
    cout<<minus<int>()(43,50)<<endl;
}

运行结果：