https://issues.dlang.org/show_bug.cgi?id=16429

          Issue ID: 16429
           Summary: Sorted multimap data structure based on
                    std.container.rbtree
           Product: D
           Version: D2
          Hardware: x86_64
                OS: Windows
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: phobos
          Assignee: nobody@puremagic.com
          Reporter: dhasenan@gmail.com

It's not unusual to need a sorted map or multimap. For instance, a sparse event queue is easily implemented as a sorted multimap.

While it's not exactly difficult to implement that using std.container.rbtree, you need to know the trick of creating a struct that only uses one member in its comparator, implement that struct, then make a wrapper around the redblack tree implementation.

And that's assuming you know that a redblack tree can support the required operations before looking at the module names in std.container, and you're not tired or stressed enough to miss that the implementation presents an interface appropriate for the purpose of finding the lowest element etc.

It would be nicer to present a module 'std.container.sortedmap' that does the work for you, presents the interface you expect, and has a name that tells you it does what you're after. The module could present map and multimap variants.

--