Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
Class

CGAL::Multiset<Type,Compare,Allocator>

Definition

An instance s of the parametrized data type Multiset<Type,Compare,Allocator> is a multi-set of elements of type Type, represented as a red-black tree (see [CLRS01, Chapter 13] for an excellent introduction to red-black trees). The main difference between Multiset<Type,Compare,Allocator> and STL's multiset is that the latter uses a less-than functor with a Boolean return type, while our Multiset<Type,Compare,Allocator> class is parameterized by a comparison functor Compare that returns the three-valued Comparison_result (namely it returns either SMALLER, EQUAL, or LARGER). It is thus possible to maintain the underlying red-black tree with less invocations of the comparison functor. This leads to a speedup of about 5% even if we maintain a set of integers. When each comparison of two elements of type Type is an expensive operation (for example, when they are geometric entities represented using exact arithmetic), the usage of a three-valued comparison functor can lead to considerable decrease in the running times.

Moreover, Multiset<Type,Compare,Allocator> allows the insertion of an element into the set given its exact position, and not just using an insertion hint, as done by std::multiset. This can further reduce the running times, as additional comparison operations can be avoided.

In addition, the Multiset<Type,Compare,Allocator> guarantees that the order of elements sent to the comparison functor is fixed. For example, if we insert a new element x into the set (or erase an element from the set), then we always invoke Compare() (x, y) (and never Compare() (y, x)), where y is an element already stored in the set. This behavior, not supported by std::multiset, is sometimes crucial for designing more efficient comparison predicates.

Multiset<Type,Compare,Allocator> also allows for look-up of keys whose type may differ from Type, as long as users supply a comparison functor CompareKey, where CompareKey() (key, y) returns the three-valued Comparison_result (key is the look-up key and y is an element of type Type). Indeed, it is very convenient to look-up equivalent objects in the set given just by their key. We note however that it is also possible to use a key of type Type and to employ the default Compare functor for the look-up, as done when using the std::multiset class.

Finally, Multiset<Type,Compare,Allocator> introduces the catenate() and split() functions. The first function operates on s and accepts a second set s', such that the maximum element in s is not greater than the minimal element in s', and concatenates s' to s. The second function splits s into two sets,one containing all the elements that are less than a given key, and the other contains all elements greater than (or equal to) this key.

Parameters

The Multiset class-template has three parameters:

#include <CGAL/Multiset.h>

Assertions

The assertion and precondition flags for the Multiset class use MULTISET in their names (i.e., CGAL_MULTISET_NO_ASSERTIONS and CGAL_MULTISET_NO_PRECONDITIONS).

Types

In compliance with STL, the types value_type and key_type (both equivalent to Type), reference and const_reference (reference to a value-type), key_compare and value_compare (both equivalent to Compare), size_type and difference_type are defined as well.

Multiset<Type,Compare,Allocator>::iterator
Multiset<Type,Compare,Allocator>::const_iterator
bi-directional iterators for the elements stored in the set.


Multiset<Type,Compare,Allocator>::reverse_iterator
Multiset<Type,Compare,Allocator>::const_reverse_iterator
reverse bi-directional iterators for the elements stored in the set.

Creation

Multiset<Type,Compare,Allocator> s;
creates an an empty set s that uses a default comparison functor.


Multiset<Type,Compare,Allocator> s ( Compare comp);
creates an an empty set s that uses the given comparison functor comp.


template <class InputIterator>
Multiset<Type,Compare,Allocator> s ( InputIterator first, InputIterator last, Compare comp = Compare());
creates a set s containing all elements in the range [first, last), that uses the comparison functor comp.


Multiset<Type,Compare,Allocator> s ( other);
copy constructor.

Multiset<Type,Compare,Allocator> s = other assignment operator.

void s.swap ( & other) swaps the contents of s with those of the other set.

Access Member Functions

Compare s.key_comp () const the comparison functor used.
Compare s.value_comp () const the comparison functor used (same as above). Both functions have a non-const version that return a reference to the comparison functor.

bool s.empty () returns true if the set is empty, false otherwise.

size_t s.size () returns the number of elements stored in the set.

size_t s.max_size () returns the maximal number of elements the set can store (same as size()).

iterator s.begin () returns an iterator pointing to the first element stored in the set (a const version is also available).

iterator s.end () returns an iterator pointing beyond the last element stored in the set (a const version is also available).

reverse_iterator s.rbegin () returns a reverse iterator pointing beyond the last element stored in the set (a const version is also available).

reverse_iterator s.rend () returns a reverse iterator pointing to the first element stored in the set (a const version is also available).

Comparison Operations

bool s == other const returns true if the sequences of elements in the two sets are pairwise equal (using the comparison functor).

bool s < other const returns true if the element sequence in s is lexicographically smaller than the element sequence of other.

Insertion Methods

iterator s.insert ( Type x) inserts the element x into the set and returns an iterator pointing to the newly inserted element.

template <class InputIterator>
void s.insert ( InputIterator first, InputIterator last)
inserts all elements in the range [first, last) into the set.

iterator s.insert ( iterator position, Type x)
inserts the element x with a given iterator used as a hint for the position of the new element. It Returns an iterator pointing to the newly inserted element.

iterator s.insert_before ( iterator position, Type x)
inserts the element x as the predecessor of the element at the given position.
Precondition:  The operation does not violate the set order - that is, x is not greater than the element pointed by position and not less than its current predecessor.

iterator s.insert_after ( iterator position, Type x)
inserts the element x as the successor of the element at the given position.
Precondition:  The operation does not violate the set order - that is, x is not less than the element pointed by position and not greater than its current successor.

Removal Methods

size_t s.erase ( Type x) erases all elements equivalent to x from the set and returns the number of erased elements.

void s.erase ( iterator position) erases the element pointed by position.

void s.clear () clears the set (erases all stored elements).

Look-up Methods

All methods listed in this section can also accept a Type element as a look-up key. In this case, it is not necessary to supply a CompareKey functor, as the Compare functor will be used by default.

template <class Key, class CompareKey>
iterator s.find ( Key key, CompareKey comp_key)
searches for the an element equivalent to key in the set. If the set contains objects equivalent to key, it returns an iterator pointing to the first one. Otherwise, end() is returned (a const version is also available).

template <class Key, class CompareKey>
size_t s.count ( Key key, CompareKey comp_key) const
returns the number of elements equivalent to key in the set.

template <class Key, class CompareKey>
iterator s.lower_bound ( Key key, CompareKey comp_key)
returns an iterator pointing to the first element in the set that is not less than key. If all set elements are less than key, end() is returned (a const version is also available).

template <class Key, class CompareKey>
iterator s.upper_bound ( Key key, CompareKey comp_key)
returns an iterator pointing to the first element in the set that is greater than key. If no set element is greater than key, end() is returned (a const version is also available).

template <class Key, class CompareKey>
std::pair<iterator,iterator> s.equal_range ( Key key, CompareKey comp_key)
returns the range of set elements equivalent to the given key, namely (lower_bound(key), upper_bound(key)) (a const version is also available).

template <class Key, class CompareKey>
std::pair<iterator,bool> s.find_lower ( Key key, CompareKey comp_key)
returns a pair comprised of lower_bound(key) and a Boolean flag indicating whether this iterator points to an element equivalent to the given key (a const version is also available).

Special Operations

void s.replace ( iterator position, Type x)
replaces the element stored at the given position with x.
Precondition:  The operation does not violate the set order - that is, x is not less that position's predecessor and not greater than its successor.

void s.swap ( iterator pos1, iterator pos2)
swaps places between the two elements given by pos1 and pos2.
Precondition:  The operation does not violate the set order - that is, pos1 and pos2 store equivalent elements.

void s.catenate ( Self& s_prime) concatenates all elements in s_prime into s and clears s_prime. All iterators to s and to s_prime remain valid.
Precondition:  The maximal element in s is not greater than the minimal element in s_prime.

template <class Key, class CompareKey>
void s.split ( Key key, CompareKey comp_key, Self& s_prime)
splits s such that it contains all elements that are less than the given key and such that s_prime contains all other elements.
Precondition:  s_prime is initially empty.

void s.split ( iterator position, Self& s_prime)
splits s such that it contains all set elements in the range [begin, position) and such that s_prime contains all elements in the range [position, end()).
Precondition:  s_prime is initially empty.

Implementation

Multiset uses a proprietary implementation of a red-black tree data-structure. The red-black tree invariants guarantee that the height of a tree containing n elements is O(log n) (more precisely, it is bounded by 2 log 2n). As a consequence, all methods that accept an element and need to locate it in the tree (namely insert(x), erase(x), find(x), count(x), lower_bound(x) , upper_bound(x), find_lower(x) and equal_range(x)) take O(log n) time and perform O(log n) comparison operations.

On the other hand, the set operations that accept a position iterator (namely insert_before(pos, x), insert_after(pos, x) and erase(pos)) are much more efficient as they can be performed at a constant amortized cost (see [GS78] and [Tar83] for more details). More important, these set operations require no comparison operations. Therefore, it is highly recommended to maintain the set via iterators to the stored elements, whenever possible. The function insert(pos, x) is safer to use, but it takes amortized O(min {d,log n}) time, where d is the distance between the given position and the true position of x. In addition, it always performs at least two comparison operations.

The catenate() and split() functions are also very efficient, and can be performed in O(log n) time, where n is the total number of elements in the sets, and without performing any comparison operations (see [Tar83] for the details). Note however that the size of two sets resulting from a split operation is initially unknown, as it is impossible to compute it in less than linear time. Thus, the first invocation of size() on such a set takes linear time, and not constant time.

The design is derived from the STL multiset class-template (see, e.g, [MS96]), where the main differences between the two classes are highlighted in the class definition above.

Next: Object
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 4.1. 23 October 2012.