Thus, as far as I know, dict is using set as its keys underlying data structure.

Hmm, no not really. The opposite way around is a closer analogy: in the implementation, a set is like using dict with all null values.  dict came first in Python, sets did not appear until Python 2.2 (July 2000) - see PEP 218.

Also worth mentioning that dict.keys() is O(1) since Python 3, in Python 2 it's O(n) and you should use dict.viewkeys() for the set-like interface.

is list(set) O(1)?

No, it's O(n) - just the same as the list comprehension.

And how is this implemented?

Sets support the iterator protocol.

Thus, as far as I know, dict is using set as its keys underlying data structure.

Hmm, no not really. The opposite way around is a closer analogy: in the implementation, set is like a dict with all null values. The dict came first in Python, and set did not appear until Python 2.2 (July 2000) - see PEP 218.

Also worth mentioning that dict.keys() is O(1) since Python 3. In Python 2 it's O(n) and you should use dict.viewkeys() for the keys "view" (set-like interface).

is list(set) O(1)?

No, it's O(n) - just the same as the list comprehension.

And how is this implemented?

Sets support the iterator protocol.