C++ has handled general dynamic casting since 1987,
when multiple inheritance was added to the language [47].
Wirth later presented a technique that can be used to imple-
ment subtype tests by traversing a linked list of types [54].
His encoding required little space, but ran in time propor-
tional to the distance between the two types in the class hi-
erarchy. A trivial constant-time type inclusion test can be
implemented with a binary matrix, encoding the subtyping
relation on the class hierarchy [12]. While efficient in time,
it has quadratic space requirements, which makes it expen-
sive for use on large class hierarchies. Cohen proposed the
first space-efficient constant-time algorithm, but it can only
deal with single inheritance [9]. Hierarchical encoding is an-
other constant-time test that maps subtype queries into sub-
set queries on bit-vectors [7, 31]. The approach can handle
multiple inheritance, but the space and time required for a
subtype test in this encoding increases with the size of the
class hierarchy; also, Caseau’s approach [7] is limited to
class hierarchies that are lattices. Schubert’s relative num-
bering [45] encodes each type with an interval [l, r], ef-
fectively making type inclusion tests isomorphic to a sim-
ple range checking. The encoding is optimal in space and
time, but it is limited to single inheritance. PQ-Encoding of
Zibin and Gil employs PQ-trees to improve further space and
time efficiency of the constant-time inclusion testing [57].
While capable of handling type inclusion queries on hier-
archies with multiple inheritance, the approach makes the
closed world assumption and can be costly for use with dy-
namic linking because it is not incremental. The approach of
Gibbs and Stroustrup [23] employs divisibility of numbers to
obtain a constant-time type inclusion test. The approach can
handle multiple inheritance and was the first constant-time
technique to addresses the problem of casts between subob-
jects. Unfortunately, the approach limits the size of the class
hierarchies that can be encoded with this technique. Ducour-
nau proposed a constant-time inclusion test based on the fact
that, in an open solution, a class has a known number of base
classes, and thus perfect hashes can be used to map them
to this-pointer offsets typically used to implement subobject
casts [17]. Unfortunately, the approach addresses only vir-
tual multiple inheritance and (similarly to other approaches)
relies on load-time computations. An excellent introduction
to and detailed analysis of existing constant-time type inclu-
sion tests can be found in [50, 57].

Dafuq... подумать только.

#ttfnzo

3 comments recommend bookmark subscribe