ABSTRACT
Algorithmically positioned collections, such as ordered collections, priority queues, and spatial collections, use information about the elements to determine their proper placement within the data structure. Often, this information is extracted from the elements themselves with the help of a comparator, a digitizer, or other similar mechanism. However, in many cases it is desirable to organize elements not on the basis of information derived from the elements, but instead on the basis of information that is externally assigned to each element by the application. In other words, the application provides, for each element, an external tag that is to be associated with that element in the collection. A tagged collection is a collection that provides the necessary support for associating these tags with the corresponding elements. Most tagged collections permit duplicate tags. For example, in a collection of jobs, the application may assign to each element a tag denoting the priority of that job. There may be many jobs with the same priority. However, some tagged collections enforce the restriction that tags are unique. Each tag in such a collection is called a key, because it can be presented to the collection in order to find its associated element. However, even when the tags are unique, multiple keys may map to the same element.
