6 ms·
What’s better in your opinion?
by hsivonen 9y ago
What’s better in your opinion?
- Someone 9y agoI would guess what (s)he writes in https://news.ycombinator.com/item?id=14150628 https://news.ycombinator.com/item?id=14150628, except that, maybe, vector<node*> children; is a typo, and should be vector<node>* children; Reason: I don't see how the former enforces "e) yet the structure ensures that there are no loops in the tree." The latter would mean more copying of nodes, but would have excellent cache locality, so I can see it could well be faster, too.
- c-smile 9y agoIt is precisely vector<node*> children; yet this vector<node>* children; makes little sense in DOM case.
- deleted 9y ago[deleted]
- smitherfield 9y agoThat does seem like it makes more sense; you could then implement `node_index` as a fast, stateless inline method like so: constexpr vector<Node>::difference_type node_index() const noexcept { return parent ? this - parent->children->begin() : -1; // is a root node }
- c-smile 9y agoThis does not work, element/node shall have stable address so to be O(1) addressable. Elements/nodes can participate in multiple lists at the same time. Rendering lists (a.k.a. rendering tree) and things like Document.querySelectorAll() that returns NodeList.
- deleted 9y ago[deleted]
- Someone 9y agoCan I conclude that your earlier statement "yet the structure ensures that there are no loops in the tree." isn't correct? I could easily create a loop like this: this.children[0] = this;
- wtetzner 9y agoHow could that happen, given that children isn't a pointer? vector<node*> children;
- Someone 9y agoIt is C++, and std::vector has an operator[] that makes a vector behave like a convention C 'pointer to data' for array accesses (in fact, the compiler likely will optimize the access to exactly what you would get if the declaration were of a C array of pointers to node)
- c-smile 9y agoThat case is easily manageable: you cannot insert/appendNode that has non-null parent. So you need to remove that node from its former parent first. Problem is that their solution by design contains loops. So on each tree traversal iteration you will need to access parent: Node* get_next_node(Node* that) { that = that->next; return that == that->parent->first_child ? nullptr : that; }
- hsivonen 9y agoGecko had that but migrated to neighbor pointers, so that's a data point of one real engine moving from a child array to neighbor pointers.