[Python-Dev] Compact ordered set

[Chris Angelico]

On Thu, Feb 28, 2019 at 10:58 PM Antoine Pitrou <solipsis at pitrou.net> wrote:
> Some of them may be coming from C++, where the respective
> characteristics of set and map (or unordered_set and
> unordered_multimap) are closely related.  I'm sure other languages
> show similar analogies.
>
> On a more abstract level, set and dict are both content-addressed
> collections parametered on hash and equality functions.  For
> algorithmically-minded people it makes sense to see a close connection
> between them.

Looking from the opposite direction, sets and dicts can be used to
solve a lot of the same problems. Want to detect cycles? Stuff things
you see into a set. If the thing is in the set, you've already seen
it. What if you want to track WHERE the cycle came from? Then stuff
things you see into a dict, mapping them to some kind of trace
information. Again, if the thing's in the collection, you've already
seen it, but now, since it's a dict, you can pull up some more info.
And collections.Counter can be used kinda like a multiset, but it's
definitely a dictionary. I think the similarities are more pragmatic
than pure, but that doesn't mean they aren't real.

ChrisA