Reference » Collections and iterators » MSortList

Elgrint::MSortList<T> class

Declared in MSortList.h

Description

Linear ordered collection with automatic sorting capability.

Base class: Collection

Template parameters:

Name Description
T

The type of any element in MSortList. Must support public copy constructor, public destructor, and self-consistent binary operator<, which determines the sorting order.

Classes:

Name Description
CIter Constant iterator of MSortList.

Mutators:

Name Description
insert(x) Inserts x into the list, preserving the sorting (at O(lgn) time complexity).
remove(x) Removes an element equal to x (if any) from the list (at O(lgn) time complexity).

Revealers:

Name Description
getMax() Returns the last element on the list (which must be the largest one) at O(1) time complexity.
has(x) Returns true iff the list contains at least one element equal to x (at O(lgn) time complexity).

Details

The sort list contains an ordered sequence of items (not necessarily unique), which are always sorted in ascending order. In particular, the last item in the list (as returned by getMax) is also the largest item in the list. Any insert or remove operation preserves the sorting. The existing items can be enumerated in the ascending order using the constant iterator. Naturally, the sort list does not support non-constant iterators, because changing the item values may break the sorting, and thus the list's consistency. The sort list can also determine whether a given value exists in the list with logarithmic complexity (using has).

The sort list is useful for implementing large editable databases, which have to be sorted at all times, for example a phone book. For static databases, that need to be sorted infrequently or only once, a more efficient way is to use MVector::sort method.

The sorting order is determined by the operator< of the T type. By providing a suitable operator<, you can control the sorting in various ways. For example, if the custom operator< returns true when the first operand is larger than the second one (the opposite of the regular definition), then the resulting list will be sorted in descending order, rather than ascending. In the general case you will need a wrapper class for type T to accomplish this (see Example).

The sort list is based on the width list collection (see MWidthList for more details).

Example

Let us know

Please Contact us to report any errors on this page, or to suggest any improvements.

Miranor Home | About Miranor | About Elgrint | Create account | Login | Account settings | Contact Us | Privacy Policy | Site map

© Copyright 2014 by Miranor. All rights reserved. By using this site you agree to the Terms of Use.

Page last updated on August 10th, 2014.