C++仿函数应用小例

写一道涉及图BFS的题目。图BFS需要一个visit数组管理已经访问过的顶点。因此需要另外开一个数组去管理这个过程。AC后我想这样管理实在是有点烦人，于是想办法把queue和visit管理重新打包成一个类去管理。

一开始我是这样打包的：

template<typename _Tp,typename _Sequence = deque<_Tp> >
class OnceBFS_Queue: public std::queue<_Tp,_Sequence>
{
    public:
        OnceBFS_Queue(int len, const _Sequence& __c = _Sequence()): uque(__c){ 
            vis = new bool[len];  
            memset(vis, 0, len*sizeof(bool)); 
        }
        ~OnceBFS_Queue() { free(vis); }
        bool push(const _Tp& _x){
            unsigned int idx = _x;
            if(vis[idx]) { return false; }
            else { vis[idx]=true; uque::push(_x); return true;}
        }
        bool isVis(const unsigned int& _x) { return vis[_x]; }
    protected:
        typedef std::queue<_Tp,_Sequence> uque;
        bool* vis;
};

因为绝大多数情况下，顶点的编号是一个非负整数。但是这道题偏偏有点不一样，BFS的过程中会绑定上另一个参数，并且希望将这个参数提取出来使用。而上面这种形式，缺乏应变的空间。应付诸如int unsigned long这样的原生变量还行，一旦遇上稍微复杂一点的自定义结构，例如本题中我用到的pair<int, unsigned long long>，则根本没办法通过编译。

究其原因是无法通过这些数据类型得到需要标记的下标。如果是整数，则对指针的[ ]操作可以被编译器直接翻译。但是显然[ ]中不能放pair<int, long long>类型的变量。这时候就需要一个单独的函数去完成这件事情。

一开始我的想法是传递一个函数指针。能够想到两种方案。一种是从构造函数中传递，也就是在运行时完成指定过程。还有一种方法，是通过模板参数指定。但这样一来缺乏灵活性，没办法适配各种各样的参数条件（万一需要通过绑定或者别的手段，向函数中带入参数呢？）；二来也不够优雅，STL缺乏合适的包装器和修饰器去表示一些简单的传递关系。

那么，借鉴一下算法竞赛中常用的——priority_queue。这是一个模板类，而且经常需要这样设定模板参数：

1	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>

在dijkstra算法中，需要这样指定priority_queue的参数，才能够正确地从队列顶部得到d值最大的顶点。让我们把注意力放在greater<pair<int,int>>上。之前我只知道这个STL类型可以像函数一样判断大小关系，并不知道其本质。但是只要转到它的定义去看看，就可以得到如下代码（因为STL s**t一样的代码风格，我稍微做了调整）：

template<typename _Tp>
struct greater : public binary_function<_Tp, _Tp, bool>
{
    _GLIBCXX14_CONSTEXPR
    bool operator()(const _Tp& __x, const _Tp& __y) const { 
        return __x > __y; 
    }
};

可以看到，所谓greater，实际上就是一个重载了( )运算符的struct。这就意味着，这个模板类被实例化之后，可以等价于这样的函数：

1	bool greater (const Type& __x, const Type& __y)

调用时也只需要类似：

1
2
3

int a, b;
/* Do something here */
bool ans = greater<int>(a, b)

可以发现，尽管greater<>是一个struct，但是经过运算符的重载，在使用中和函数无异。更重要的是，struct不比单纯的函数指针，你可以在不同的struct实例中夹带额外的内容。

这就是本文要说的——仿函数

实际上，仿函数并不是C++特有的概念。通过一些手段，可以在Java甚至C语言实现相同的原理。通过一些简单的封装，将复杂的操作通过一个类型带入各种作用域当中，同时降低了代码的耦合性，不得不说是一种很精妙的设计了。

通过仿函数设计出来的带有自动visit的数组是长这样的：

template<typename _Tp,typename _Ind,typename _Sequence = deque<_Tp> >
class OnceBFS_Queue: public std::queue<_Tp,_Sequence>
{
    public:
        OnceBFS_Queue(int len, const _Sequence& __c = _Sequence()): uque(__c)
            { vis = new bool[len];  memset(vis, 0, len*sizeof(bool)); }
        ~OnceBFS_Queue() { free(vis); }
        bool push(const _Tp& _x){
            unsigned int idx = Index(_x);
            if(vis[idx]) { return false; }
            else { vis[idx]=true; uque::push(_x); return true;}
        }
        bool isVis(const _Tp& _x) { return vis[Index(_x)]; }
        bool isVis(const unsigned int& _x) { return vis[_x]; }
    protected:
        typedef std::queue<_Tp,_Sequence> uque;
        bool* vis;
        _Ind Index;
};


struct cp { 
    unsigned int operator() (const pair<int,ull> &x) { 
        return x.first; 
        //看起来很蠢，是因为这里确实不需要额外的操作，但是操作的扩展性大大增强了
        //为了避免额外的性能开销，我还是把仿函数放在了模板参数，以尽量保持代码静态
    } 
};

原题目是多case的，即便如此，在不断的new和free中，也没有产生很明显的额外性能开销。实际上，在我们学校的垃圾OJ上，使用这样一个class，和使用传统C风格的写法，在性能上开销完全相同，不得不感叹一下C++的“0 cost”模板技术了。

经过观察，我发现还可以通过抽象基类的继承这种方式，实现对更大范围的容器的适配，例如前面提到的priority_queue，甚至stack和deque。

不过因为各种容器的接口并不是非常一致，导致想要扩增适配，还是要手动进行继承和设定。因此写了一半还是放弃了。但是这一切对于自己对泛型的理解，还是有一些帮助的。因为实际上这是我第一次写带有3个截然不同的模板参数的模板类，也算是一点进步了。

同温层的深冻

深冻的自留地

C++仿函数应用小例