STL Extensions for CGAL

*Michael Hoffmann, Lutz Kettner, and Sylvain Pion*

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, 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 .

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 pointered 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.

*CGAL::In_place_list<T,bool>*

*CGAL::In_place_list_base<T>*

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.

*CGAL::Compact_container<T, Allocator>*

*CGAL::Compact_container_traits<T>*

*CGAL::Compact_container_base*

*CGAL::copy_n*

*CGAL::min_max_element*

*CGAL::min_element_if*

*CGAL::max_element_if*

*CGAL::predecessor*

*CGAL::successor*

*CGAL::Emptyset_iterator*

*CGAL::Oneset_iterator<T>*

*CGAL::Insert_iterator<Container>*

*CGAL::Counting_iterator<Iterator, Value>*

*CGAL::N_step_adaptor<I,int N>*

*CGAL::Filter_iterator<Iterator, Predicate>*

*CGAL::Join_input_iterator_1<Iterator, Creator>*

*CGAL::Inverse_index<IC>*

*CGAL::Random_access_adaptor<IC>*

*CGAL::Random_access_value_adaptor<IC,T>*

The standard library contains some adaptors for binding functors, that is fixing one argument of a functor to a specific value thereby creating a new functor that takes one argument less than the original functor. Also, though non-standard, some STL implementations (such as SGI) provide adaptors to compose function objects. Unfortunately, these bind and compose adaptors are limited to unary and binary functors only, and these functors must not be overloaded.

Since there are a number of functors in CGAL that take more than two arguments, and since functors may also be overloaded, i.e., accept several different sets of arguments, we have to define our own adaptors to be used with CGAL functors.

*CGAL::swap_1*

*CGAL::swap_2*

*CGAL::swap_3*

*CGAL::swap_4*

*CGAL::bind_1*

*CGAL::bind_2*

*CGAL::bind_3*

*CGAL::bind_4*

*CGAL::bind_5*

*CGAL::compose*

*CGAL::compose_shared*

*CGAL::Swap<F,i>*

*CGAL::Bind<F,A,i>*

*CGAL::Compose<F0,F1,F2,F3>*

*CGAL::Compose_shared<F0,F1,F2,F3>*

*AdaptableFunctor*

*CGAL::Arity_tag<int>*

*CGAL::Arity_traits<F>*

*CGAL::Set_arity<F,a>*

*CGAL::set_arity_0*

*CGAL::set_arity_1*

*CGAL::set_arity_2*

*CGAL::set_arity_3*

*CGAL::set_arity_4*

*CGAL::set_arity_5*

*CGAL::Identity<Value>*

*CGAL::Dereference<Value>*

*CGAL::Get_address<Value>*

*CGAL::Cast_function_object<Arg, Result>*

*CGAL::Project_vertex<Node>*

*CGAL::Project_facet<Node>*

*CGAL::Project_point<Node>*

*CGAL::Project_normal<Node>*

*CGAL::Project_plane<Node>*

*CGAL::Project_next<Node>*

*CGAL::Project_prev<Node>*

*CGAL::Project_next_opposite<Node>*

*CGAL::Project_opposite_prev<Node>*

*CGAL::Creator_1<Arg, Result>*

*CGAL::Creator_2<Arg1, Arg2, Result>*

*CGAL::Creator_3<Arg1, Arg2, Arg3, Result>*

*CGAL::Creator_4<Arg1, Arg2, Arg3, Arg4, Result>*

*CGAL::Creator_5<Arg1, Arg2, Arg3, Arg4, Arg5, Result>*

*CGAL::Creator_uniform_2<Arg, Result>*

*CGAL::Creator_uniform_3<Arg, Result>*

*CGAL::Creator_uniform_4<Arg, Result>*

*CGAL::Creator_uniform_5<Arg, Result>*

*CGAL::Creator_uniform_6<Arg, Result>*

*CGAL::Creator_uniform_7<Arg, Result>*

*CGAL::Creator_uniform_8<Arg, Result>*

*CGAL::Creator_uniform_9<Arg, Result>*

*CGAL::Creator_uniform_d<Arg, Result>*

Next chapter: Handles and Circulators

The CGAL Project .
Tue, December 21, 2004 .