Project proposal: A meldable, iterator-valid priority queue. CPH STL Report 2005-1

Research output: Working paperResearch

  • Jyrki Katajainen
The Standard Template Library (STL) is a library of generic algorithms and data structures that has been incorporated in the C++ standard and ships with all modern C++ compilers. In the CPH STL project the goal is to implement an enhanced edition of the STL. The priority-queue class of the STL is just an adapter that makes any resizable array to a queue in which the elements stored are arranged according to a given ordering function. In the C++ standard no compulsory support for the operations delete(), increase(), or meld() is demanded even if those are utilized in many algorithms solving graph-theoretic or geometric problems. In this project, the goal is to implement a CPH STL extension of the priority-queue class which provides, in addition to the normal priority-queue functionality, the operations delete(), increase(), and meld(). To make the first two of these operations possible, the class must also guarantee that external references to compartments inside the data structure are kept valid at all times.
Original languageEnglish
Number of pages37
Publication statusPublished - 2005

ID: 15430264