Chapter 72
STL Extensions for CGAL

Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Ron Wein

Table of Contents

72.1 Doubly-Connected List Managing Items in Place
72.2 Compact Container
72.3 Multiset with Extended Functionality
72.4 Polymorphic Object
72.5 Uncertainty Management
72.6 Complexity tags and policies
72.7 Default Arguments in Template Parameter Lists

Cgal is designed in the spirit of the generic programming paradigm to work together with the Standard Template Library (STL) [C++98, Aus98]. This chapter documents non-geometric STL-like components that are not provided in the STL standard but in Cgal: a doubly-connected list managing items in place (where inserted items are not copied), a compact container, a multi-set class that uses three-valued comparisons and offers additional functionality, generic algorithms, iterators, functor adaptors for binding and swapping arguments and for composition, functors for projection and creation and adaptor classes around iterators and circulators. See also circulators in Chapter 75. A class storing polymorphic objects is also provided, as well as a class to manage the uncertainty of some values. Finally, tags and policy classes to specify complexity trade-offs of data-structures, and a class which helps specifying that the default types in template parameter lists are desired is also provided.

72.1   Doubly-Connected List Managing Items in Place

The class In_place_list<T,bool> manages a sequence of items in place in a doubly-connected list. Its goals are the flexible handling of memory management and performance optimization. The item type has to provide the two necessary pointers &T::next_link and &T::prev_link. One possibility to obtain these pointers is to inherit them from the base class In_place_list_base<T>.

The class In_place_list<T,bool> is a container quite similar to STL containers, with the advantage that it is able to handle the stored elements by reference instead of copying them. It is possible to delete an element only knowing its address and no iterator to it. This used to simplify mutually pointed data structures like a halfedge data structure for planar maps or polyhedral surfaces (the current design does not need this anymore). The usual iterators are also available.

72.2   Compact Container

The class Compact_container<T, Allocator> is an STL like container which provides a very compact storage for its elements. It achieves this goal by requiring T to provide access to a pointer in it, which is going to be used by Compact_container<T, Allocator> for its internal management. The traits class Compact_container_traits<T> specifies the way to access that pointer. The class Compact_container_base can be used as a base class to provide the pointer, although in this case you do not get the most compact representation. The values that this pointer can have during valid use of the object are valid pointer values to 4 bytes aligned objects (i.e., the two least significant bits of the pointer need to be zero when the object is constructed). Another interesting property of this container is that iterators are not invalidated during insert or erase operations.

The main deviation from the STL container concept is that the ++ and -- operators of the iterator do not have a constant time complexity in all cases. The actual complexity is related to the maximum size that the container has had during its life time compared to its current size, because the iterator has to go over the "erased" elements as well, so the bad case is when the container used to contain lots of elements, but now has far less. In this case, we suggest to do a copy of the container in order to "defragment" the internal representation.

This container has been developed in order to efficiently handle large data structures like the triangulation and halfedge data structures. It can probably be useful for other kinds of graphs as well.

72.3   Multiset with Extended Functionality

The class Multiset<Type,Compare,Allocator> represents 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). It differs from the STL's multiset class-template mainly due to the fact that it is parameterized by a comparison functor Compare that returns the three-valued Comparison_result (namely it returns either SMALLER, EQUAL, or LARGER), rather than a less functor returning bool. Thus, it is possible to maintain the underlying red-black tree with less invocations of the comparison functor, which can considerably decrease running times, especially when comparing elements of type Type is an expensive operation.

Multiset<Type,Compare,Allocator> also 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.

The interface of Multiset<Type,Compare,Allocator> is in general derived from std::multiset. However, it extends the interface by offering some additional operations, such as: inserting of an element into the set given its exact position (and not just using an insertion hint); looking up keys whose type may differ from Type, as long as users supply a comparison functor CompareKey, between the keys and set elements; and catenating and splitting sets.

72.4   Polymorphic Object

The class Object can store an object of whatever other type. It can be used by a function to return objects of different types. A mechanism to extract the stored object based on its type is also provided. This class is similar to boost::any.

72.5   Uncertainty Management

The class Uncertain<T> represents a range of values of type T. T is allowed to stand for bool, or Cgal's enumeration types Sign, Comparison_result, Orientation, Oriented_side, Bounded_side and Angle.

The idea is that sometimes you are not sure of the result of a function, and you would like to communicate that to the caller. Uncertain<T> allows just that. It also provides functions to naturally extend the Boolean operations for Uncertain<bool> for example.

Uncertain<T> is used in Cgal as the return type of geometric predicates when the number type used is interval arithmetic like Interval_nt. End users typically do not see it as it is hidden in the implementation of the filtered predicates provided by the various filtered kernels, but it is important that providers of predicates that are meant to be filtered by Filtered_predicate, know about it.

It can also be used in other contexts as well, as it is a general tool.

72.6   Complexity tags and policies

Some data structures and algorithms can be implemented with different complexity trade-offs between memory usage and time complexity. Cgal provides the tags Fast and Compact which can be used to select between those variants. For example, the Location_policy class is parameterized by these tags and allows to specify the complexity of point location (currently in Delaunay_triangulation_3 only). Convenient typedefs Fast_location and Compact_location are also provided.

72.7   Default Arguments in Template Parameter Lists

In C++, it is possible to specify defaults at the end of a template parameter list. Specifying that one wishes to use the default is simply done by omitting it. This is however possible only at the end of the list. CGAL::Default provides a simple mechanism that performs something equivalent anywhere in the sequence.