woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

STL中的Concept和Boost库的Concept_Check

在generic programming当中,一个重要的概念就是concept(滑稽的是,如果把这个concept也翻译成“概念”,那就狗屁不通了。我倾向于说它是“操作集”)。concept就是一组操作,如果一个type具有这些操作,那么就说这个type是这个concept的一个model。
这其中的思想有那么一丁点像是oo当中的interface,一个class如果实现了一个interface,那么它就可以被当作这个interface来用。同样,如果一个type是一个concept的model,那么所有接受这个concept的操作也就可以接受这个type。
例如,在stl中,stable_sort这个算法必须接受randomaccessiterator,这里randomaccessiterator就是一个concept,它规定自己的model必须可以进行下标运算,那么不满足这个concept的type就无法被编译器接受(搞笑的是我在vc71里面把list<int> 的iterator传给stable_sort,它居然欣然接受,要知道list的iterator应该只是一个bidirectionaliterator 啊,比randomaccessiterator弱多了。不过仔细看看代码,发现vc71的stable_sort接受bidirectionaliterator就够了,不知道是好还是坏)。在gcc下面如果传递一个bidirectionaliterator给stable_sort,会得到一堆不知所云的错误提示,让人摸不着头脑。
c++语言本身并没有对于concept的直接支持,stl解决这个问题的办法是用了一些traits来限制iterator的特性,以达到在编译时期检查concept的目的。但是traits导致的编译错误提示实在是太可怕了,我非常怀疑有哪个正常人可以从这些错误提示推测出自己错在哪里。
在boost库里面,提供了一个conceptcheck库,它可以帮助我们写出带有concept检查的代码,而且没有运行时的开销,一旦用户违反concept限制,输出的错误提示也比较好懂。举个例子先,如果stl里面有conceptcheck,那么它的stable_sort大约会这样:
#include <boost/concept_check.hpp>
template <class randomaccessiter>
void stable_sort(randomaccessiter first, randomaccessiter last)
{
    function_requires< randomaccessiteratorconcept<randomaccessiter> >();
    //... bla bla bla......
}
有了这个 function_requires ,如果再传递给它list的iterator,编译器(vc71)就会报这样的错:


c:\boost_1_31_0\boost\concept_check.hpp(642): error c2676: 二进制“+=” : “std::list<_ty>::iterator”不定义该运算符或到预定义运算符可接收的类型的转换
        with
        [
            _ty=int
        ]
当然还有很多别的,但是至少它说了一点:传入的iterator不满足某个运算。这对于用户来说,应当是一个很有用的提示。
使用concept check还有一个额外的好处,那就是调用一个 function_requires可远比写一些traits容易,而且代码也清晰好维护。

这个好用的 function_requires 就定义在concept_check.hpp当中:
template <class concept>
inline void function_requires(mpl::identity<concept>* = 0)
{
#if !defined(ndebug)
  void (concept::*x)() = boost_fptr concept::constraints;
  ignore_unused_variable_warning(x);
#endif
}
换句话说,function_requires只在debug中起作用,那么是不是在debug当中它就添加了overhead呢?其实也没有,仔细看看代码:
void (concept::*x)() = boost_fptr concept::constraints;
这一句取constraints的地址。妙就妙在它让编译器“注意到”constraints,但又没有真正调用constraints,而constraints是一个虚函数,做实际的check。例如在randomaccessiteratorconcept(检查iterator是否符合randomaccessiterator的concept)当中,constraint是这个样子:
template <class tt>
struct randomaccessiteratorconcept
{
    void constraints() {
    function_requires< bidirectionaliteratorconcept<tt> >();
    function_requires< comparableconcept<tt> >();
#ifndef boost_no_std_iterator_traits
    typedef typename std::iterator_traits<tt>::iterator_category c;
    function_requires< convertibleconcept< c,
        std::random_access_iterator_tag> >();
    typedef typename std::iterator_traits<tt>::reference r;
#endif

    i += n;             // require assignment addition operator
    i = i + n; i = n + i; // require addition with difference type
    i -= n;             // require assignment subtraction operator
    i = i - n;                  // require subtraction with difference type
    n = i - j;                  // require difference operator
    (void)i[n];                 // require element access operator
    }
    tt a, b;
    tt i, j;
#ifndef boost_no_std_iterator_traits
    typename std::iterator_traits<tt>::difference_type n;
#else
    std::ptrdiff_t n;
#endif
};
从这个实现中我们完全可以读出randomaccessiterator的具体含义:
1. 它必须是一个bidirectionaliterator
2. 它必须满足“可比较 (comparable)”的concept
3. 它还必须满足“可转换 (convertible)”的concept,而且是转换成自己的iterator_category类别

4. 它必须定义了reference这个type
5. 这是最重要的,它必须有difference_type,而且可以进行 +, -, +=, -= 的运算
还要记得,由于这个函数没有真正的被调用过,所以无论你怎么写,它都不会变成实际的代码,所以也不会影响运行效率的!

posted on 2008-07-26 23:08 肥仔 阅读(1034) 评论(0)  编辑 收藏 引用 所属分类: C++ 基础


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理