Just for the record, when I originally looked at insert_before() and insert_after(), here's some of things that bugged me a little:

* insert_before(currkey, newkey, newvalue) ncan raise TypeErrors for hashability from either key.   It can raise a KeyError when currkey doesn't exist and a KeyError when newkey already exists.  It can raise a ValueError with currkey is equal to newkey.   That is a mess of exceptions that a user might need to untangle with exception chaining or custom exceptions.

* One use case for the insert methods is trying to maintain a sort order (such as an alphabetical order) but we don't have any efficient search methods such as a binary search to find an insertion point.  For example, if I read an alphabetically sorted config file of key / value pairs, how would I insert a new key/value pair in the proper position?

I also looked at adding an OrderedSet at one point and held-off because:

* there were no feature requests from users
* at the time, I wasn't finding third-party implementations on pypi,
  in the wild, or in the rich toolsets like Enthought's distro.
* it was so easy to build one by inheriting from a MutableSet
  and using an underlying OrderedDict.
* I also put a direct impplementation in a recipe on ASPN
  http://code.activestate.com/recipes/576694/
  to see if there was any uptake
* it was unclear what the ordering semantics should be on the
  various set-to-set operations (it would entail turning off
  some of the current optimizations such as intersection()
  looping over the smaller input set rather than the first
  listed set).
* In Python 3 and 2.7, fromkeys() readily constructs a set
  and the views on keys() and items() already support set
  operations.  AFAICT, nobody uses these even though all the
  desired set functionality is already there.

Since that time, there has been very little interest shown in an ordered set.  There have been a few upvotes on the ASPN recipe and a little activity on PyPi with a C version using Cython (see https://pypi.python.org/pypi?%3Aaction=search&term=ordered+set&submit=search ).

Another thing that caused me to hold-off was the possibility that regular sets could be made to be ordered with very little overhead (completely eliminating the need for a separate type).  I have two different approaches ready if we wanted to go down that path.

Now that PyPI has an ordered set offering, there is even less of a need for us to put one in the standard library unless it becomes more of an everyday need.