[Python-Dev] Compact ordered set

[Xavier Morel]

> On 2019-02-28, at 12:56 , Antoine Pitrou <solipsis at pitrou.net> wrote:
> 
> On Thu, 28 Feb 2019 22:43:04 +1100
> Steven D'Aprano <steve at pearwood.info> wrote:
>> On Wed, Feb 27, 2019 at 02:15:53PM -0800, Barry Warsaw wrote:
>> 
>>> I’m just relaying a data point.  Some Python folks I’ve worked with do 
>>> make the connection between dicts and sets, and have questions about 
>>> the ordering guarantees of then (and how they relate).  
>> 
>> Sets and dicts are not related by inheritence (except that they're both 
>> subclasses of ``object``, but so is everything else). They don't share 
>> an implementation. They don't provide the same API. They don't do the 
>> same thing, except in the most general sense that they are both 
>> collections.
>> 
>> What connection are these folks making?
> 
> 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.

Indeed e.g. Rust's hashset is a trivial wrapper around a hashmap (with
no value): https://doc.rust-
lang.org/src/std/collections/hash/set.rs.html#121-123, its btreeset has
the exact same relationship to btreemap: https://doc.rust-
lang.org/src/alloc/collections/btree/set.rs.html#72-74

> 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.

I can't speak for anyone else but before seeing this thread I actually
assumed (without any evidence or having checked obviously) that the set
builtin was built on top of dict or that they were built on the same
base and that the changes to dict's implementation in 3.6 (ordering,
space, …) had affected  sets in the same way.

That seems intuitively straightforward, even more so with dict.keys()
being a set.