On Thursday 10 January 2008 16:35:22 Sebastian Redl wrote:
dizzy wrote:
The final (best?) solution I came with now is using RTTI. RTTI's typeid() is by design non-intrusive (actually the way it is implemented by the compiler is intrusive but it happens anyway for any polymorphic type so why not use it) and it does not have any of the problems listed above, the implementation is "small enough" that I can include it here:
If I understand correctly, your implementation is O(n) with n = size(typelist), right? The advantage of virtual calls is that they're O(1), no matter how big the hierarchy.
Yes, that is true. But at the same time, AFAIK, the CPU optimizes my case better than jumping to a memory loaded address, in general code of the form: if (case1) func1(); if (case2) func2(); Should be faster than of: typedef void (*Function)(); Function funcs[2] = { &func1, &func2 }; funcs[getindex(input)](); As I understand it in the first case it can realise the possible outcomes from analyzing of the CPU instructions loaded (and thus may start to load instructions at the possible jump locations it has seen), in the later it cannot until it has loaded the contents of the array from memory (it probably does not matter if that is already cached as it happens for often used vtables).
Though if that is a problem in the real world is a different question. How big are visited class hierarchies usually?
In my case I use that visitor for 2 hierarchies of an average 5-6 visitable types. Your questions make me think of possibly implementing a virtual function based solution too (with that parallel hierarchy template wrapper technique described in the previous mail) and maybe have the user decide which of them to use? As there are user variables here that may decide the best to use in terms of CPU and memory resources: - number of visitable types - number of visits (or better, the ratio of visits/visitable-types) -- Mihai RUSU Email: dizzy@roedu.net "Linux is obsolete" -- AST