Project proposal: A meldable, iterator-valid priority queue
Author:Jyrki Katajainen
Publication:CPH STL Report 2005-1, Department of Computer Science, University of Copenhagen (2005), 37 pp.
Full text:<pdf.gif>PDF (188 kB)  <ps.gif>PS (512 kB)  

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.

Related:<html.gif>HTML (Compressed tar ball)  
  author = {Jyrki Katajainen},
  title = {Project proposal: {A} meldable, iterator-valid priority queue},
  type = {CPH STL Report},
  number = {2005-1},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2005},
  pagetotal = {37},
This page was generated by Jyrki Katajainen <> on 31.12.2011.