Reputation: 4421
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
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