4 ms·
Luckily, you can do the rewrite manually. I recently implemented an array mapped trie that shared structure when copied. `find`, `erase`, and `at` were all re
by sonyandy 11y ago
Luckily, you can do the rewrite manually. I recently implemented an array mapped trie that shared structure when copied. `find`, `erase`, and `at` were all rewritten to use loops after first implementing them recursively (and profiling indicated it to be a problem).
- masklinn 11y agoIf you follow the link, the issue isn't iteration, iteration is easy. The issue is the recursive destruction of the tree when the root is destroyed and no subtree is shared. > The list implementation is simple/nice but it imposes a limit on number of stored elements because of "additional effect" of recursive destruction.
- sonyandy 11y agoHow would you perform destruction of a tree with more than one child tail recursively? I mean this as an honest question - my current implementation of array_mapped_trie performs this operation via non-tail recursive calls. EDIT: I also don't see how destruction of a list is any harder than iteration of a list, as far as writing it tail recursively. You would need to make sure your node destructors are trivial, but you probably need to do this anyway if you intend to support using a custom Allocator (would instead have template <typename Allocator> destroy(node*, Allocator&); that calls Allocator::destroy on the contained value and Allocator::deallocate on the node). The implementation would then look something along the lines of: decltype(head) next; for (auto ptr = head; ptr; ptr = next) { next = ptr->next; if (ptr->unique()) { destroy(ptr, allocator); } } (unique() is a method on node - intrusive ref count.)