C++仿函数应用小例

/ 0评 / 0

写一道涉及图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。这是一个模板类,而且经常需要这样设定模板参数:

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。这就意味着,这个模板类被实例化之后,可以等价于这样的函数:

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

调用时也只需要类似:

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个截然不同的模板参数的模板类,也算是一点进步了。

发表评论

邮箱地址不会被公开。 必填项已用*标注