glampert
glampert

Reputation: 4421

Is dynamic_cast constant time?

There are a lot of question on the subject, but none seem to address this specifically: Is there any guarantee that a dynamic_cast is a constant time operation? Or is it linear in the class hierarchy? I can think of a couple of ways one could implement it to perform in constant time, but a naive approach would surely be to just walk the inheritance chain. Does the C++ standard impose any constraints on it?

Upvotes: 1

Views: 319

Answers (1)

templatetypedef
templatetypedef

Reputation: 373042

Having read over the C++ spec, to the best of my knowledge, there are no restrictions on the runtime of dynamic_cast. The relevant sections of the spec purely focus on the observable behavior of how dynamic_cast operates rather than on time complexity.

To the best of my knowledge, most implementations of dynamic_cast and RTTI in general work by walking up in the type hierarchy at runtime and trying to determine whether the cast succeeds. There are other techniques for doing this that, for small type hierarchies, can be made to work in time O(1), but I don't believe any major C++ implementation does this.

Hope this helps!

Upvotes: 2

Related Questions