|   登录   |   注册   |   设为首页   |   加入收藏   

用户登录

close

用户名:

密码:

新用户注册

close

用户名:

密码:

密码确认:

电子邮箱:

关注内容:

个人主页:

帮助

close

龙宇网成立于2008年3月,网站进入整体运作于2010年10月1日。

在这里,我们把它做成了一个真正意义上的网站,完全以个人的信息为内容,以网友的需要为主导,全力搜罗各种信息,建立完善的网站功能,使网友在这里可以第一时间找到所需要的信息。

现在,经过三年的努力,网站的资料已经相当丰富,而网站得到了大家的喜爱和认可。

但,我们还是会继续努力下去,让网间的这份快乐继续持续下去,让这份闲暇时的日子,与快乐一并同行。

寻觅快乐,网住快乐,关注网络,是龙宇网的宣言与承诺。

Generic:类型和数值间的映射

分类: 数据结构 发布时间: 2019-04-11 15:19:43 浏览次数: 1301
内容提要: 在C++里,“转换(conversion)”一词描述了从一种类型的值取得另一种类型的值的过程。然而,有时候你会需要另一种转换:你可能需要从一种类型里取得一个数值,或者相反。这样的转换在C++里不太自然,因为类型和数值之间有一条难以逾越的鸿沟。但是在一些特定的情况下,我们需要突破这两者之间的界限,这篇文章将讨论怎么做。

在C++里,“转换(conversion)”一词描述了从一种类型的值取得另一种类型的值的过程。然而,有时候你会需要另一种转换:你可能需要从一种类型里取得一个数值,或者相反。这样的转换在C++里不太自然,因为类型和数值之间有一条难以逾越的鸿沟。但是在一些特定的情况下,我们需要突破这两者之间的界限,这篇文章将讨论怎么做。

从整数映射到类型

对很多泛型编程惯用法来说,有一个很有用的模板,它却出人意料地简单:

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

对于每一个不同的常整数参数,Int2Type会“生成”一个不同的类型。因为不同的模板实例是不同的类型,所以Int2Type<0>和Int2Type<1>等是不同的。而且,产生这个类型的值被“保存”在枚举成员value里。

我们可以方便地使用Int2Type来“类型化”某个常整数。比如说,我们设计了一个类模板NiftyContainer:

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

NiftyContainer保存了一个指向T的指针。在NiftyContainer的一些成员函数里,我们需要复制T类型的对象。如果T是非多态的类型,我们可以这样:

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

对于多态的类型,那就要复杂一些。我们约定,所有用于NiftyContainer的多态类型都要定义虚函数Clone,然后就可以这样复制对象:

T* pNewObj = pSomeObj->Clone();

因为容器要能够接受两种类型,所以我们必须实现上面两种复制算法,并且在编译时能够选择适当的一个。我们可以为NiftyContainer增加一个布尔类型的模板参数来表示T是否为一个多态类,靠程序员来传递正确的标志。

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

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

如果NiftyContainer里的类型不是多态的,那么它的很多成员函数都可以优化,因为可以期望对象的大小是固定的,而且对象有确定的语义。在这些成员函数里,我们要根据模板参数isPolymorphic在两个算法中择其一。

乍一看,只需要用一个if就可以做到。

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

问题是,这样的代码不能编译。举例来说,如果多态的算法用到了pObj->Clone,那么对于没有定义成员函数Clone的类型,NiftyContainer::DoSomething都不能编译。编译时if的哪个分支会执行是很明显的,但是编译器可不管这些,它总会编译两个分支,尽管最后优化的时候会删除不会执行的死代码。当你调用NiftyContainer<int, false>的DoSomething时,编译器会停在调用pObj->Clone的地方,并且说:“嘿!”

还不止这些呢。即使T是多态类型,这段代码可能还是不能编译。假设T的拷贝构造函数被禁用了(通过把拷贝构造函数声明为private或者protected,一个设计良好的多态类应该这样做),那么针对非多态类的那个分支里的new T(*pObj)调用将编译失败。

如果编译器可以不去编译死代码就好了,但现实不是如此。那么什么是令人满意的解决方案呢?

结果是,有若干解决方案,用Int2Type可以提供一个特别干净利落的方法。Int2Type可以把布尔变量isPolymorphic的true和false两个值转换成两个不同的类型,然后我们就可以借助函数重载(overloading)使用Int2Type<isPolymorphic>了。瞧!

下面请惯用法“整数类型化”现身说法。

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>类型的临时变量根本没使用,它只是用来传递类型信息。

Not So Fast, Skywalker!

看了上面的例子,你可能会想,通过模板特化的种种技巧,也许还有更聪明的办法。为什么需要那个临时的哑变量呢?确实还有更好的办法。然而,令人惊奇的是,其他方法在简单性、一般性、有效性上,很难胜过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 ...
}

尽管上面的代码看上去非常漂亮,可这是不合法的,没有“部分特化类模板的一个成员函数”这么一回事。我们只能对NiftyContainer整体进行部分特化。

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

你也可以整体特化DoSomething:

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

但是,很奇怪,你不能做介于两者之间的事。[1]

另一个解决办法是使用traits[2],在NiftyContainer外面(traits类中)实现DoSomething。这可能是个很笨拙的方法,因为它把DoSomething的部分实现隔离开来了。

第三个方法还是用traits,通过在NiftyContainer内部定义私有的traits类,以求把所有东西都放在一起。长话短说,这个方法是可行的,但是当你最终实现它的时候,你就会认识到Int2Type方法有多好了。Int2Type方法最大的优点是,你可以把小巧的Int2Type模板放在你的类库里,并且在文档中注明它的用法。

类型到类型的映射

考虑下面的函数:

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

Create把参数传递给构造函数,以创建一个新的对象。

假设在你的应用程序里有一条规则:Widget类型是以前写的,其对象在构造的时候需要两个参数,第二个参数需要传固定的值-1。所有Widget的派生类却不需要这样做。

怎样对Create进行特化,使它特殊照顾Widget类型呢?你不能对部分特化模板函数,就是说不能这样干:

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

因为C++没有函数部分特化功能,我们唯一可用的手段还是重载。我们可以传递一个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不提供或不允许调用缺省构造函数,那就没辙了。

著名的谚语“额外的中间层(extra level of indirection)”在这里也可以得到运用。一个想法是用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>());

这样比原来的那个方法更容易说清楚。和Int2Type一样,你可以把Type2Type加到你的类库里去,并注明它的用法。

检测可转换性和继承关系

在实现模板函数和模板类时,经常会遇到一个问题:任意给定两个类型B和D,怎么才能知道D是不是从B继承下来的?

在编译时发现这样的关系,是在泛型库中实现高级优化的关键。在一个泛型函数中,如果这个类实现了某个特定的接口,我们就可以利用相应的优化算法,而不必对其进行dynamic_cast。

检测继承关系依赖于一个更一般的机制:检测可转换性(convertibility)。我们要一起解决的更一般性的问题是:如何检测一个任意类型T能不能自动转换为另一个任意类型U。

有一个用sizeof的解决方案(你原来是不是认为sizeof只在给memset传参数时才会用到?)。sizeof有令人吃惊的威力,因为任一个不管多复杂的表达式,sizeof都能得出其大小,并且竟然不用在运行时计算。这意味着sizeof可以识别重载、模板实例化、类型转换规则——在C++表达式里可能出现的任何东西。事实上,sizeof是一个完整的推导表达式类型的机制,最终sizeof丢掉表达式而只返回其结果的大小[3]。

进行类型检查的一个设想是用sizeof和重载函数。你提供一个函数的两个重载版本:一个接受类型U的参数,这是转换目的类型;另一个接受其他任何类型的参数。你用你希望测试可转换性的类型T去调用这个函数,如果接受U的那个函数被调用了,你就可以知道T可以转换成U;反之,如果另一个函数被调用,那么T不能转换成U。

为了检测哪个函数被调用,你要使两个重载版本返回大小不同的两个类型,然后用sizeof来区分它们。返回什么类型无所谓,只要它们有不同的大小。

让我们先来创建两个大小不同的类型(显然,char和long double确实有不同的大小,但是这不是C++标准保证的)。一个最简单的方案如下:

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

根据定义,sizeof(Small)为1。Big的大小还是不知道,但是可以确定的是它肯定比1大,我们只要有这个保证就行了。

接下来,我们需要两个重载函数。一个接受U,返回上面的两个类型之一,比如说Small。

Small Test(U);

怎么写接受其他任何类型参数的函数呢?我们不能用模板,因为模板总是会实例化为最匹配那个版本,这样就避免了类型转换。我们需要的是更糟糕的参数匹配,而不是自动转换。快速浏览一下函数调用的匹配规则,我们发现省略参数方式是最倒霉的,它是最后被选择的方式。我们需要的就是这个。

Big Test(...);

(用一个C++对象调用省略参数的函数,将产生未定义的结果,但是不用管它,没有人会真的去调用它,这个函数甚至根本不用实现。)

然后我们传入一个T类型的实体,调用Test,再用sizeof测试结果:

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);

(像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::exists << ' '
        << Conversion::exists << ' '
        << Conversion<size_t, vector<int> >::exists << ' ';
}

这个小程序打印“1 0 0”。注意,尽管std::vector实现了一个以size_t为参数的构造函数,但是转换测试还是返回0,因为那个构造函数被声明为explicit。

我们可以在Conversion里实现另外两个常数:

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来实现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)

很显然是吗?可能还有一点模糊。如果D是从B共有继承下来,或者B和D是同一种类型,SUPERSUBCLASS(B, D)为真。SUPERSUBCLASS是通过检测能不能把const D*转换成const B*来实现的。只有在三种情况下可以把const D*隐式地转换为const B*:

B和D是同一种类型;
B是D的无二义性的共有基类;
B是void。


 

最后一种情况通过第二个判断排除。实际应用中接受第一种情况(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,我们总是在安全的一边。

为什么要叫SUPERSUBCLASS,而不是更漂亮的BASE_OF或者INHERITS呢?这是因为一个很实际的理由:如果用INHERITS(B, D)的话,我老是要忘记测试的方向——是测试B继承于D还是反过来?SUPERSUBCLASS(B, D)就可以把哪个是第一个哪个是第二个分清楚(至少对我来说是这样)。

结论

关于这里介绍的三个惯用法,最重要的一点是,它们是可重用的。你可以把它们写到类库里去,让别的程序员使用,而不需要要求他们掌握复杂的内部的工作机制。

重要技术的重用性是很重要的。如果要求人们记住一个复杂的技术来做一件事,而他们可以用相对简单但是有点冗长的方法做到同样的事,那么他们不会用复杂的方法。给他们一个简单的黑盒子,可以帮他们做一些奇妙而有用的事,他们会喜欢它并使用它,因为它是free的。

Int2Type,Type2Type和Conversion属于一个通用的工具类库。通过做一些重要的编译时类型推导,它们使程序员在编译时能做更多的事。

致谢

如果Clint Eastwood问我:“你觉得幸运吗?”,我一定会说是的。这是我在这一系列中的第三篇文章,这得益于Herb Sutter本人的直接关注,以及非常好的建议。感谢日本的Tomio Hoshida指出一个bug,并且提出富有洞察力的建议。

本文包括Andrei Alexandrescu所著Modern C++ Design(Addison-Wesley,2001)一书的部分内容。

注:

[1] 现在概念上没有要求C++支持函数的部分特化,我个人认为,这是一个值得期望的特性。

[2] Andrei Alexandrescu. "Traits: The else-if-then of Types", C++ Report (April 2000).

[3] 有个提案要求C++增加typeof操作符;就是返回一个表达式类型的操作符。如果有typeof的话,模板写起来会更容易,理解起来也更容易。GNU C++在它的扩展功能里,已经实现了typeof。显然,typeof和sizeof背后实现是类似的,因为sizeof总是要计算类型的。[参考Bill Gibbons将在以后的CUJ里发表的文章,他在目前的C++标准下提供了一个漂亮的,而且几乎是自然的typeof实现。]


 

15
20

分类: 数据结构   |   评论: 0   |   引用: 0   |   浏览次数: 1301