[Python-ideas] Add OrderedSet now that OrderedDict is in collections

[Mart Sõmermaa]

On Fri, May 8, 2009 at 6:06 PM, Arnaud Delobelle <arnodel at googlemail.com> wrote:
>
> I implemented a unification algorithm that needed multisets to work in
> O(n^2).

Complexity is a totally different theme and best reserved for
extensions. Supporting  special-case containers that have various
space/speed and best/worst case tradeoffs have been discussed before
and the consensus seems to be that supporting them in stdlib is
infeasible -- with what I entirely agree. Supporting multiset only for
O(n^2) performance would violate that consensus.

However, ordered set and ordered map are not special-case in that
sense. It's not the O-complexity but general utility -- i.e. the
plugging of the holes in the ordering and uniqueness table and helping
people with the corresponding use cases -- that vouch for their
inclusion in the stdlib. Now that ordered map is in, ordered set could
follow.