On Fri Feb 9 22:31:00 2024 +0000, Nikolay Sivov wrote:
Alright, push a variant with a list. Please take a look.
I would say that RB trees are essentially the same amount of work as lists (incidentally, I wish we used a language that made both more ergonomical and type-safe to use, but that's another matter). Given that the implementation is already done in both cases, I don't see strong reasons to prefer one or the other in abstract. Here we need, it seems, an unordered associative container supporting element addition and element retrieval from a key, which maps rather naturally to a RB tree, which is on average more efficient than a linked list for these operations. Of course it might be that in practical cases the list might be approximately as efficient, or even better, than the tree, but in those cases the cost is likely to be very small anyway; and in other (even if somewhat unexpected) cases the tree is likely to be much better than the list. Overall I think I'd choose the RB tree, though I can't say my opinion is really strong here.