CGAL 6.0  STL Extensions for CGAL

#include <CGAL/Multiset.h>
An instance s
of the parametrized data type Multiset
is a multiset of elements of type Type
, represented as a redblack tree (see [[3] Chapter 13 for an excellent introduction to redblack trees). The main difference between Multiset
and the STL std::multiset
is that the latter uses a lessthan functor with a Boolean return type, while our Multiset
class is parameterized by a comparison functor Compare
that returns the threevalued Comparison_result
(namely it returns either SMALLER
, EQUAL
, or LARGER
). It is thus possible to maintain the underlying redblack 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 threevalued comparison functor can lead to considerable decrease in the running times.
Moreover, Multiset
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
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
also allows for lookup of keys whose type may differ from Type
, as long as users supply a comparison functor CompareKey
, where CompareKey() (key, y)
returns the threevalued Comparison_result
(key
is the lookup key and y
is an element of type Type
). Indeed, it is very convenient to lookup 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 lookup, as done when using the std::multiset
class.
Multiset
introduces the catenate()
and split()
functions. The first function operates on s
and accepts a second set s2
, such that the maximum element in s
is not greater than the minimal element in s2
, and concatenates s2
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.Type  the type of the stored elements. 
Compare  the comparisonfunctor type. This type should provide the following operator for comparing two Type elements, namely: Comparison_result operator() (const Type& t1, const Type& t2) const; The CGAL::Compare<Type> functor is used by default. In this case, Type must support an equality operator (operator== ) and a lessthan operator (operator< ). 
Allocator  the allocator type. CGAL_ALLOCATOR is used by default. 
Implementation
Multiset
uses a proprietary implementation of a redblack tree datastructure. The redblack tree invariants guarantee that the height of a tree containing \( n\) elements is \(O(\log{n})\) (more precisely, it is bounded by \( 2 \log_{2}{n}\)). 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 [4] and [6] 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 [6] 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
classtemplate (see, e.g, [5]), where the main differences between the two classes are highlighted in the class definition above.
Types  
In compliance with STL, the types  
typedef unspecified_type  iterator 
typedef unspecified_type  const_iterator 
bidirectional iterators for the elements stored in the set.  
typedef unspecified_type  reverse_iterator 
typedef unspecified_type  const_reverse_iterator 
reverse bidirectional iterators for the elements stored in the set.  
Creation  
Multiset ()  
creates an an empty set s that uses a default comparison functor.  
Multiset (const Compare &comp)  
creates an an empty set s that uses the given comparison functor comp .  
template<class InputIterator >  
Multiset (InputIterator first, InputIterator last, const Compare &comp=Compare())  
creates a set s containing all elements in the range [first, last) , that uses the comparison functor comp .  
Multiset (const Multiset< Type, Compare, Allocator > &other)  
copy constructor.  
const Multiset< Type, Compare, Allocator > &  operator= (const Multiset< Type, Compare, Allocator > &other) 
assignment operator.  
void  swap (Multiset< Type, Compare, Allocator > &other) 
swaps the contents of s with those of the other set.  
Access Member Functions  
Compare  key_comp () const 
the comparison functor used.  
Compare  value_comp () const 
the comparison functor used (same as above).  
bool  empty () 
returns true if the set is empty, false otherwise.  
size_t  size () 
returns the number of elements stored in the set.  
size_t  max_size () 
returns the maximal number of elements the set can store (same as size() ).  
iterator  begin () 
returns an iterator pointing to the first element stored in the set (a const version is also available).  
iterator  end () 
returns an iterator pointing beyond the last element stored in the set (a const version is also available).  
reverse_iterator  rbegin () 
returns a reverse iterator pointing beyond the last element stored in the set (a const version is also available).  
reverse_iterator  rend () 
returns a reverse iterator pointing to the first element stored in the set (a const version is also available).  
Comparison Operations  
bool  operator== (const Multiset< Type, Compare, Allocator > &other) const 
returns true if the sequences of elements in the two sets are pairwise equal (using the comparison functor).  
bool  operator< (const Multiset< Type, Compare, Allocator > &other) const 
returns true if the element sequence in s is lexicographically smaller than the element sequence of other .  
Insertion Methods  
iterator  insert (const Type &x) 
inserts the element x into the set and returns an iterator pointing to the newly inserted element.  
template<class InputIterator >  
void  insert (InputIterator first, InputIterator last) 
inserts all elements in the range [first, last) into the set.  
iterator  insert (iterator position, const Type &x) 
inserts the element x with a given iterator used as a hint for the position of the new element.  
iterator  insert_before (iterator position, const Type &x) 
inserts the element x as the predecessor of the element at the given position.  
iterator  insert_after (iterator position, const Type &x) 
inserts the element x as the successor of the element at the given position.  
Removal Methods  
size_t  erase (const Type &x) 
erases all elements equivalent to x from the set and returns the number of erased elements.  
void  erase (iterator position) 
erases the element pointed by position .  
void  clear () 
clears the set (erases all stored elements).  
Lookup Methods  
All methods listed in this section can also accept a In this case, it is not necessary to supply a  
template<class Key , class CompareKey >  
iterator  find (const Key &key, const CompareKey &comp_key) 
searches for the an element equivalent to key in the set.  
template<class Key , class CompareKey >  
size_t  count (const Key &key, const CompareKey &comp_key) const 
returns the number of elements equivalent to key in the set.  
template<class Key , class CompareKey >  
iterator  lower_bound (const Key &key, const CompareKey &comp_key) 
returns an iterator pointing to the first element in the set that is not less than key .  
template<class Key , class CompareKey >  
iterator  upper_bound (const Key &key, const CompareKey &comp_key) 
returns an iterator pointing to the first element in the set that is greater than key .  
template<class Key , class CompareKey >  
std::pair< iterator, iterator >  equal_range (const Key &key, const 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 >  find_lower (const Key &key, const 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  replace (iterator position, const Type &x) 
replaces the element stored at the given position with x .  
void  swap (iterator pos1, iterator pos2) 
swaps places between the two elements given by pos1 and pos2 .  
void  catenate (Self &s_prime) 
concatenates all elements in s_prime into s and clears s_prime .  
template<class Key , class CompareKey >  
void  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.  
void  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()) .  
void CGAL::Multiset< Type, Compare, Allocator >::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.
s
is not greater than the minimal element in s_prime
. iterator CGAL::Multiset< Type, Compare, Allocator >::find  (  const Key &  key, 
const 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).
iterator CGAL::Multiset< Type, Compare, Allocator >::insert  (  iterator  position, 
const 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 CGAL::Multiset< Type, Compare, Allocator >::insert_after  (  iterator  position, 
const Type &  x  
) 
inserts the element x
as the successor of the element at the given position.
x
is not less than the element pointed by position
and not greater than its current successor. iterator CGAL::Multiset< Type, Compare, Allocator >::insert_before  (  iterator  position, 
const Type &  x  
) 
inserts the element x
as the predecessor of the element at the given position.
x
is not greater than the element pointed by position
and not less than its current predecessor. iterator CGAL::Multiset< Type, Compare, Allocator >::lower_bound  (  const Key &  key, 
const 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).
void CGAL::Multiset< Type, Compare, Allocator >::replace  (  iterator  position, 
const Type &  x  
) 
replaces the element stored at the given position with x
.
x
is not less that position
's predecessor and not greater than its successor. void CGAL::Multiset< Type, Compare, Allocator >::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())
.
s_prime
is initially empty. void CGAL::Multiset< Type, Compare, Allocator >::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.
s_prime
is initially empty. void CGAL::Multiset< Type, Compare, Allocator >::swap  (  iterator  pos1, 
iterator  pos2  
) 
swaps places between the two elements given by pos1
and pos2
.
pos1
and pos2
store equivalent elements. iterator CGAL::Multiset< Type, Compare, Allocator >::upper_bound  (  const Key &  key, 
const 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).
Compare CGAL::Multiset< Type, Compare, Allocator >::value_comp  (  )  const 
the comparison functor used (same as above).
Both functions have a nonconst version that return a reference to the comparison functor.