ABSTRACT
An ordered collection is an untagged algorithmically positioned collection of comparable elements that may contain duplicates. That is, order is defined by a comparator and the collection may contain multiple “equal” elements and multiple occurrences of the same element. The primary methods are to add an element, determine if an element is in the collection, to remove an element, and to find the previous or next element in the ordering defined by the comparator. The iteration order must follow the ordering defined by the comparator. Data structures for an ordered collection typically provide logarithmic time implementations for these methods. However, in some cases the data structures support constant time implementations, or require linear time implementations.
