Now, whether that's a realistic use case is another question. But at the same time, you know someone on the Internet is doing it that way...
And yes, this was essentially my question. What are the realistic numbers in either scenario.
But it's a relatively easy performance enhancement to have a validity flag for the ordinals, and only rewrite them when a read requires them. That way, write-heavy workloads won't be punished.
ArrayList (sciter's children list) vs LinkedList (Edge children list) : http://stackoverflow.com/questions/322715/when-to-use-linked...
The specific questions would be how often are the trees of a site dynamic and how often they insert instead of prepend or append.
Edit: And, of course, I'm still interested in why more people don't use stackfree algorithms for DFS.
So we are speaking about vectors of pointers that contain 1000 elements. memmove() performance (used for quite rare operation of insertion of elements in the middle) on modern CPU is comparable with the need to access left/right elements in DL-lists for insertion. Consider cache misses, etc.
With this, I'm always bemused that there are not more discussions on algorithms for doing tree traversal that don't use a queue or a stack. I think you have everything you need here to accomplish that.