Generic<Programming>:类型和值之间的映射

类别:VC语言 点击:0 评论:0 推荐:

Generic<Programming>:类型和值之间的映射
Andrei Alexandrescu

在C++中,术语“转化”(conversion)描述的是从另外一个类型的值(value)获取一个类型(type)的值的过程。可是有时候你会需要一种不同类型的转化:可能是在你有一个类型时需要获取一个值,或是其它的类似情形。在C++中做这样的转化是不寻常的,因为类型域和值域之间隔有有一堵很严格的界线。可是,在一些特定的场合,你需要跨越这两个边界,本栏就是要讨论该怎么做到这个跨越。

映射整数为类型

一个对许多的generic programming编程风格非常有帮助的暴简单的模板:

template <int v>
struct Int2Type
{
    enum { value = v };
};

对传递的每一个不同的常整型值,Int2Type“产生”一个不同的类型。这是因为不同的模板的实体(instantiation)是不同的类型,所以Int2Type<0>不同于Int2Type<1>等其它的类型的。此外,产生类型的值被“存放”在枚举(enum)的成员值里面。

不管在任何时候,只要你需要快速“类型化”(typify)一个整型常数时,你都可以使用Int2Type。比如这个例子,你要设计一个NiftyContainer类模板。

template <typename T>
class NiftyContainer
{
    ...
};

NiftyContainer存储了指向T的指针。在NiftyContainer的一些成员函数(member functions)中,你需要克隆类型 T的对象,如果T是一个非多态的类型,你可能会这样说:

T* pSomeObj = ...;
T* pNewObj = new T(*pSomeObj);

对于T是多态类型的情形,情况要更为复杂一些,那么我们假定你建立了这样的规则,所有的使用于NiftyContainer 的多态类型必须定义一个Clone虚拟函数(virtual function)。那么你就可以像这样来克隆对象:

T* pNewObj = pSomeObj->Clone();

因为你的容器(container)必须能够接受这两种类型,所以你必须实现两种克隆算法并在编译时刻选择适当的一个。那么不管通过NiftyContainer的布尔(非类型,non-type)模板参数传递的类型是不是多态的,你都要和它交互,而且还要依赖程序员给它传递的是正确的标识。

template <typename T, bool isPolymorphicWithClone>
class NiftyContainer
{
    ...
};

NiftyContainer<Widget, true> widgetBag;
NiftyContainer<double, false> numberBag;

如果你存储在NiftyContainer里的类型不是多态的,那么你就可以对NiftyContainer的许多成员函数进行优化处理,因为可以借助于常量的对象大小(constant object size)和值语义(value semantics)。在所有的这些成员函数中,你需要选择一个算法,或是另外一个依赖于模板参数isPolymorphic的算法。

乍一看,似乎只用一个if语句就可以了。

template <typename T, bool isPolymorphic>
class NiftyContainer
{
    ...
    void DoSomething(T* pObj)
    {
        if (isPolymorphic)
        {
            ... polymorphic algorithm ...
        }
        else
        {
            ... non-polymorphic algorithm ...
        }
    }
};

问题是编译器是不会让你摆脱这些代码的。例如,如果多态算法使用了pObj->Clone,那么NiftyContainer::DoSomething就不会那些任何一个没有定义Clone成员函数的类型而编译。的确,看起来在编译时刻要执行哪一个if语句分支是很明显的,但是这不关编译器的事,编译器仍然坚持不懈地尽心尽职地编译这两个分支,即使优化器最终会消除这些废弃代码(dead code)。如果你试图调用NiftyContainer<int, false>的DoSomething函数的话,编译器就会停留在pObj->Clone的调用之处,这是怎么回事?

等等,问题还多着呢。如果T是一个多态类型,那么代码将又一次不能通过编译了。如果T将它的copy constructor设为private和protected,禁止外部对其访问——作为一个行为良好的多态类,应该如此。那么,如果非多态的代码分支要做new T(*pObj),则代码不能编译通过。

如果编译器不为编译废弃代码费神那多好啊,但无望的期望不是解决之道,那么怎样才是一个满意的解决方案呢?

已经证实,有许多的解决办法。Int2Type就提供了一个非常精巧的解决方案。对应于isPolymorphic的值为true和false,Int2Type可以将特定的布尔值isPolymorphic转化为两个不同的类型。那么你就可以通过简单的重载(overloading)来使用Int2Type<isPolymorphic>了,搞定!

“整型类型化”(integral typifying)风格的原型(incarnation)如下所示:

template <typename T, bool isPolymorphic>
class NiftyContainer
{
private:
    void DoSomething(T* pObj, Int2Type<true>)
    {
        ... polymorphic algorithm ...
    }
    void DoSomething(T* pObj, Int2Type<false>)
    {
        ... non-polymorphic algorithm ...
    }
public:
    void DoSomething(T* pObj)
    {
        DoSomething(pObj, Int2Type<isPolymorphic>());
    }
};

这个代码简单扼要,DoSomething调用重载了的私有成员函数,根据isPolymorphic的值,两个私有重载函数之一被调用,从而完成了分支。这里,类型Int2Type<isPolymorphic>的虚拟临时变量没有被用到,它只是为传递类型信息之用。

不要太快了,天行者!

看到上面的方法,你可能认为还有更为巧妙的解决之道,可以使用比如template specialization这样的技巧。为什么必须用虚拟的临时变量,一定还有更好的方式。但是,令人惊奇的是,在简单性、通用性和效率上,Int2Type是很难打败的。

一个可能的尝试是,根据任意的T及isPolymorphic的两个可能的值,对NiftyContainer::DoSomething作特殊处理。这不就是partial template specialization的拿手戏吗?

template <typename T>
void NiftyContainer<T, true>::DoSomething(T* pObj)
{
    ... polymorphic algorithm ...
}

template <typename T>
void NiftyContainer<T, false>::DoSomething(T* pObj)
{
    ... non-polymorphic algorithm ...
}

看上去很美,可是啊呀,不好,它是不合法的。没有这样的对一个类模板的成员函数进行partial specialization的方式,你可以对整个NiftyContainer作partial specialization:

template <typename T>
class NiftyContainer<T, false>
{
    ... non-polymorphic NiftyContainer ...
};

你也可以对整个DoSomething作specialization:

template <>
void NiftyContainer<int, false>::DoSomething(int* pObj)
{
    ... non-polymorphic algorithm ...
}

但奇怪的是,在[1]之间,你不能做任何事。

另一个办法可能是引入traits技术[2],并在NiftyContainer的外部来实现DoSomething(在traits类中),但把DoSomething分开来实现显得有些笨拙了。

第三个办法仍然试图用traits技术,但把实现都放在一起,这就要在NiftyContainer里面把traits定义为私有的内部类。总之,这是可以的,但在你设法实现的时候,你就会认识到基于Int2Type的风格有多好。而且这种风格最好的地方可能就在于:在实际应用中,你可以把这个小小的Int2Type模板放在库中,并把它的预期使用记录在案。

类型到类型的映射

考虑下面这个函数:

template <class T, class U>
T* Create(const U& arg)
{
    return new T(arg);
}

Create通过传递一个参数给T的构造函数(constructor)而产生了一个新的对象。

现在假设在你的应用中用这么一个规则:类型Widget的对象是遗留下来的代码,在构造时必须要带两个参数,第二个参数是一个像-1这样的固定值。在所有派生自Widget的类中你不会碰到什么问题。

你要怎么对Create作特殊化处理,才能让它在处理Widget时,不同于所有的其它类型呢?你是不可以对函数作partial specialization的,也就是说,你不能像这样做:

// Illegal code - don't try this at home
template <class U>
Widget* Create<Widget, U>(const U& arg)
{
    return new Widget(arg, -1);
}

由于缺乏函数的partial specialization,我们所拥有的唯一工具,还是重载。可以传递一个类型T的虚拟对象,并重载。

// An implementation of Create relying on overloading
template <class T, class U>
T* Create(const U& arg, T)
{
    return new T(arg);
}
template <class U>
Widget* Create(const U& arg, Widget)
{
    return new Widget(arg, -1);
}
// Use Create()
String* pStr = Create("Hello", String());
Widget* pW = Create(100, Widget());

Create的第二个参数只是为作选择适当的重载函数之用,这也是这种自创风格的一个问题所在:你把时间浪费在建构一个你不使用的强类型的复杂对象上,即使优化器可以帮助你,但如果Widget屏蔽掉default construtor的话,那优化器也爱莫能助了。

The proverbial extra level of indirection can help here, too. (不好意思,这句不知道怎么翻译)一个想法是:传递T*而不是T来作为虚拟的模板参数。在运行时刻,总是可以传递空指针的,这在构造时的代价是相当低廉的。

template <class T, class U>
T* Create(const U& arg, T*)
{
    return new T(arg);
}
template <class U>
Widget* Create(const U& arg, Widget*)
{
    return new Widget(arg, -1);
}
// Use Create()
String* pStr = Create("Hello", (String*)0);
Widget* pW = Create(100, (Widget*)0);

这种方式对于Create的使用者来说,是最具迷惑性的。为了保持这种解决风格,我们可以使用同Int2Type有一些类似的模板。

template <typename T>
struct Type2Type
{
    typedef T OriginalType;
};

现在你可以这样写了:

template <class T, class U>
T* Create(const U& arg, Type2Type<T>)
{
    return new T(arg);
}
template <class U>
Widget* Create(const U& arg, Type2Type<Widget>)
{
    return new Widget(arg, -1);
}
// Use Create()
String* pStr = Create("Hello", Type2Type<String>());
Widget* pW = Create(100, Type2Type<Widget>());

比起其它的解决方案来说,这当然更加说明问题。当然,你又得在库里面包含Type2Type并将在它预期使用的地方记录在案。

检查可转化性和继承

在实现模板函数和模板类时,经常会碰到这样的问题:给出两个强类型B和D,你怎么检查D是不是派生自B的呢?

在对通用库作进一步的优化时,在编译时刻发现这样的关系是一个关键。在一个通用函数里,如果一个类实现了一个特定的接口,你就可以借助于一个优化的算法,而不必对其作一个dynamic_cast。

检查派生关系借助于一个更为通用的机制,那就是检查可转化性。同时,我们还要解决这样一个更为普遍的问题:要怎样才能检查一个强类型T是否支持自动转化为一个强类型U?

这个问题有一个解决办法,它可借助于sizeof。(你可能会想,sizeof不就是用作memset的参数吗,是吧?)sizeof有相当多的用途,因为你可以将sizeof使用到任何一个表达式(expression)中,在运行时刻,不管有多复杂,不用计较表达式的值是多少,sizeof总会返回表达式的大小(size)。这就意味着sizeof知道重载、模板实体化和转化的规则——每一个参与C++表达式的东东。实际上,sizeof是一个推导表达式类型的功能齐备的工具。最终,sizeof撇开表达式并返回表达式结果的大小[3]。

可转化性检查的想法借助于对重载函数使用sizeof。你可以巧妙地对一个函数提供两个重载:一个接受可以转化为U的类型,另一个则可以接受任何类型。这样你就可以调用以T为参数的重载函数了,这里T是你想要的可以转化为U 的类型。如果传入的参数为U的函数被调用,则T就转化为U;如果“退化”(fallback)函数被调用,则T不转化为U。

为了检查是哪一个函数被调用了,你可以让两个重载函数返回不同大小的类型,并用sizeof对其进行鉴别。只要是不同大小的类型,它们就难逃法眼。

首先创建两个不同大小的类型(显然,char和long double有不同的大小,但标准没有作此担保),一个简单的代码摘要如下所示:

typedef char Small;
struct Big { char dummy[2]; };

由定义可知,sizeof(Small)大小为1,Big的大小是未知的,但肯定是大于1的,对于我们来说,能保证这个已经足够了。

下一步,需要做两个重载,一个接受U并返回一个Small。

Small Test(U);

那你要怎样来写一个可以接受任何“东东”的函数呢?模板解决不了这个问题,因为模板会寻找最匹配的一个,由此而隐藏了转化。我们需要的是一个比自动转化要更差一些的匹配。快速浏览一下应用于给定了省略号的函数调用的转化规则。它就在列表的最后面,就是最差的那个,这恰恰就是我们所需要的。

Big Test(...);

(以一个C++对象来调用一个带省略符的函数会产生未知的结果,可谁在乎呢?又不会有人真的调用这样的函数,这种函数甚至都不会被实现。)

现在我要对Test的调用使用sizeof,给它传递一个T:

const bool convExists =
    sizeof(Test(T())) == sizeof(Small);

就是它!Test调用产生了一个缺省构造对象T,然后sizeof提取了表达式的结果的大小。它可能是sizeof(Small),也可能是sizeof(Big),这要看编译器是否找到了转化的可能。

还有一个小问题,如果T把它的缺省构造函数作为私有成员会怎么样?在这种情况下,T的表达式将不能通过编译,我们所构建的所有的这一切都是白费。幸好,这又一个简单的解决方案——只要使用一个能返回T的像稻草人一样没用的函数就好了。这样,一切问题统统解决!

T MakeT();
const bool convExists =
    sizeof(Test(MakeT())) == sizeof(Small);

(By the way, isn't it nifty just how much you can do with functions, like MakeT and Test, which not only don't do anything, but which don't even really exist at all?)
(顺便说一下,就像MakeT和Test一样,这类函数是好是坏取决于你用它来做什么,它不但什么都不做,而且甚至根本不存在的?)

现在我们可以让它工作了,把一切都封装到一个类模板中,隐藏所有关于类型推导的细节,只把结果暴露出来。

template <class T, class U>
class Conversion
{
    typedef char Small;
    struct Big { char dummy[2]; };
    static Small Test(U);
    static Big Test(...);
    T MakeT();
public:
    enum { exists =
        sizeof(Test(MakeT())) == sizeof(Small) };
};

现在你可以这样来测试Conversion模板类了。

int main()
{
    using namespace std;
    cout
        << Conversion<double, int>::exists << ' '
        << Conversion<char, char*>::exists << ' '
        << Conversion<size_t, vector<int> >::exists << ' ';
}

这个小程序的打印结果为“1 0 0”。我们注意到,尽管std::vector实现了一个带参数为size_t的构造函数,转化测试返回的结果还是0,因为构造函数是显式的(explicit)。

我们可以在Conversion中实现这样的两个或是更多的常量(constants)。

exists2Way表示在T和U之间是否可以相互转化。例如,int和double就是可以相互转化的情况,但是各种自定义类型也可以实现这样的相互转化。
sameType表示T和U是否是同种类型。

template <class T, class U>
class Conversion
{
    ... as above ...
    enum { exists2Way = exists &&
        Conversion<U, T>::exists };
    enum { sameType = false };
};

我们通过对Conversion作partial specialization来实现sameType。

template <class T>
class Conversion<T, T>
{
public:
    enum { exists = 1, exists2Way = 1, sameType = 1 };
};

那么,怎么来做派生关系的检查呢?最漂亮的地方就在于此,只要你把转化处理好了,派生关系的检查就简单了。

#define SUPERSUBCLASS(B, D) \
    (Conversion<const D*, const B*>::exists && \
    !Conversion<const B*, const void*>::sameType)

是不是一目了然了?可能还有一点点的迷糊。SUPERSUBCLASS(B, D)判断D公有派生自B是否为真,或者B和D代表的是同种类型。通过判别一个const D*到const B*的可转化性,SUPERSUBCLASS就可以作出这样的判断。const D*隐式转化为const B*只有三种情况:

B和D是同种类型;
B是D的明确的公有基类;
B是空类型。
通过第二个测试可以排除最后一种情形。在实际应用中,第一种情形(B和D为同种类型)的测试是很有用的。因为出于实际考虑,你通常都会考虑一个类是它自己的超类。如果你需要一个更严格的测试,可以这样写:

#define SUPERSUBCLASS_STRICT(B, D) \
    (SUPERSUBCLASS(B, D) && \
    !Conversion<const B, const D>::sameType)

为什么这些代码中都加上了const修饰呢?原因是你总不想因为const的问题而让转化测试失败吧。所以,在每个地方都使用了const,如果模板代码使用了两次const(对一个已经是const的类型使用const),则第二个const将被忽略掉。简而言之,在SUPERSUBCLASS中使用const是基于安全考虑的。

Why SUPERSUBCLASS and not the cuter BASE_OF or INHERITS? For a very practical reason: with INHERITS(B, D), I kept forgetting which way the test works — does it test whether B inherits D or vice versa? SUPERSUBCLASS(B, D) makes it clearer (at least for me) which one is first and which one is second.
为什么用SUPERSUBCLASS而不是更为贴切的BASE_OF或是INHERITS呢?为了一个实际的原因:使用INHERITS(B, D),我会经常忘记检测的运作方式——它测试的是B派生自D呢,还是D派生自B?而对这个问题(谁是第一个谁是第二个),SUPERSUBCLASS(B, D)说明得更为清楚一些(至少对于我来说)。

小结

在这里介绍这三种风格,一个最重要的地方就是它们是可重用的。你可以把它们写在一个库里面,并可以让程序员们使用它们,而不是要他们掌握这其中复杂的内部实现工作。

nontrivial技术的可重用性是很重要的,要人们记住一个复杂的技术,即使这个技术可以用来帮助他们的实际工作更为简化一些,但如果这个技术稍显麻烦,他们也是不会用的。给人们一个简单的黑盒,它可以带来一些有用的惊奇,人们是会喜欢它并使用它的,因为这是一个“自由”的方式。

Int2Type,Type2Type,特别是Conversion都属于一个通用的工具库。通过使用重要的编译时刻的类型推导,它们扩展了程序员的编译时刻的能力。

致谢

如果Clint Eastwood问我:“你感觉幸运吗?”,我的回答肯定为“是”。这是我这个系列的第三篇文章,这得益于 Herb Sutter的直接的关注和重要的建议。感谢日本的Tomio Hoshida发现了一个bug并做了一些有深刻见解的建议。

注:这篇文章引用自Andrei Alexandrescu的即将出版的一本书,书名暂定为《Modern C++ Design》(Addison-Wesley, 2001)。(译注:这本书已经出版了,要是能早日拜读,那有多爽啊)
注释
[1]C++对函数的partial specialization支持是没有概念上的障碍的,这是一个很有价值的特性。
[2] Andrei Alexandrescu. "Traits: The else-if-then of types", C++ Report (April 2000).
[3]建议在C++中加入一个类型of操作符,也就是一个返回一个表达式的类型的操作符。有了这么一个操作符,将会使编写模板代码更加易于编写、易于理解。GNU C++已经把typeof作为一个扩展实现了。明显地,typeof和sizeof有同样的障碍,因为无论如何,sizeof都必须计算类型。[参阅Bill Gibbons在CUJ上的一篇文章,他介绍了一个漂亮的方法,这个方法用于在现在的Standard C++里创造一个(几乎是)天然的typeof操作符。]

本文地址:http://com.8s8s.com/it/it2627.htm