[Issue 16429] New: Sorted multimap data structure based on std.container.rbtree

[via Digitalmars-d-bugs]

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 at puremagic.com
          Reporter: dhasenan at 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.

--