How does the in operator work in Python?

Question presented to candidate: "When you write x in something, what does Python actually do? Does it cost the same for a list, a set and a string, and how would you make your own class support in?"

What a strong answer should cover:

• x in y calls type(y).__contains__(y, x) when it exists; otherwise Python iterates y with __iter__; otherwise it tries the old __getitem__ protocol with indexes 0, 1, 2 ... until IndexError; otherwise TypeError.
• The result is always a bool (whatever __contains__ returns is converted), and not in is the exact negation; in bytecode both are one CONTAINS_OP instruction.
• Cost depends on the container: hash lookup, O(1) on average, for set, frozenset, dict and dict key views; a linear O(n) scan for list, tuple, dict.values() and iterators; substring search for str and bytes; arithmetic for an int in a range.
• Sequences test identity before equality (x is e or x == e), which is why nan in [nan] is True.
• Gotchas: in on a dict checks keys only; sets need a hashable left operand; in on an iterator consumes it; a float in a range falls back to a scan.

Code / implementation expected: Optional — a class with __contains__, or a demonstration of set vs list membership cost.