A new WG21 paper is available. A copy is linked below, and the paper will also appear in the next normal WG21 mailing. If you are not a committee member, please use the comments section below or the std-proposals forum for public discussion.

Document number: N3543

Date: 2013-03-15

Priority Queue, Queue and Stack: Changes and Additions

by Gary Powell, Tim Blechmann

Excerpt:

Priority Queues, Stacks and heaps are extremely useful data structures suitable for solving many common ordering problems. C++ 2011 provides only a couple of template adaptor classes; priority_queue, stack and queue, which provide limited functionality. To overcome the current limitations, this paper proposes that new containers be added to the standard library to replace the current adaptors which would then be depreciated. Additionally there are several alternative implementations of heaps having different performance characteristics which should be added to the standard library. Especially, the suggested options for these heaps deal with these additional aspects:

• Iterators: Heaps provide iterators to iterate all elements.
• Mutability: The priority of heap elements can be modified.
• Mergeable: While all heaps can be merged, some can be merged efficiently.
• Stability: Heaps can be configured to be stable sorted.
• Comparison: Heaps can be compared for equivalence.