On Oct 13, 2019, at 19:15, Steve Jorgensen <stevej@stevej.name> wrote:
What if, instead, there was an `OrderedBag` class that acts like a `list` and supports set operations.
The advantage of this is that any hidden indexing that is used to optimize the operations could be efficiently created in the object that results from the set operation during its construction while performing the operation. Using lists, any such indexes would have to be produced and discarded for each operation (or could perhaps be kept in weak references or something like that, but that's messy).
This sounds doable, but nontrivial to design and implement, and with a lot of tradeoffs to consider. I’m not sure there is a one-size-fits-all implementation that would be good enough for most uses, but if there is, you probably need to find it and at least give us a proof of concept. For example, when I’ve needed to do the kind of thing you seem to be talking about, it’s often because I have a (multi)set of values with different orderings on it. Like a database table with multiple indices. If you don’t have any ordering except for a partial ordering on hash/equality, you probably wouldn’t want the same thing I do.