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

CGAL::Compact_container<T, Allocator>

Definition

An object of the class Compact_container<T, Allocator> is a container of objects of type T. It matches all the standard requirements for reversible containers, except that the complexity of its iterator increment and decrement operations is not always guaranteed to be amortized constant time.

This container is not a standard sequence nor associative container, which means the elements are stored in no particular order, and it is not possible to specify a particular place in the iterator sequence where to insert new objects. However, all dereferenceable iterators are still valid after calls to insert() and erase(), except those that have been erased (it behaves similarly to std::list).

The main feature of this container is that it is very memory efficient : its memory size is N*sizeof(T)+o(N), where N is the maximum size that the container has had in its past history, its capacity() (the memory of erased elements is not deallocated until destruction of the container or a call to clear()). This container has been developed in order to store large graph-like data structures like the triangulation and the halfedge data structures.

It supports bidirectional iterators and allows a constant time amortized insert() operation. You cannot specify where to insert new objects (i.e. you don't know where they will end up in the iterator sequence, although insert() returns an iterator pointing to the newly inserted object). You can erase any element with a constant time complexity.

Summary of the differences with std::list : it is more compact in memory since it doesn't store two additional pointers for the iterator needs. It doesn't deallocate elements until the destruction or clear() of the container. The iterator does not have constant amortized time complexity for the increment and decrement operations in all cases, only when not too many elements have not been freed (i.e. when the size() is close to the capacity()). Iterating from begin() to end() takes O(capacity()) time, not size(). In the case where the container has a small size() compared to its capacity(), we advise to "defragment the memory" by copying the container if the iterator performance is needed.

The iterators themselves can be used as T, they provide the necessary functions to be used by Compact_container_traits<T>. Moreover, they also provide a default constructor value which is not singular : it is copyable, comparable, and guaranteed to be unique under comparison (like NULL for pointers). This makes them suitable for use in geometric graphs like handles to vertices in triangulations.

In addition, in a way inspired from the Boost.Intrusive containers, it is possible to construct iterators from references to values in containers using the iterator_to and s_iterator_to functions.

#include <CGAL/Compact_container.h>

Parameters

The parameter T is required to have a copy constructor and an assignment operator. It also needs to provide access to an internal pointer via Compact_container_traits<T>.

The equality test and the relational order require the operators == and < for T respectively.

The parameter Allocator has to match the standard allocator requirements, with value type T. This parameter has the default value CGAL_ALLOCATOR(T).

Types

Compact_container<T, Allocator>::value_type
Compact_container<T, Allocator>::reference
Compact_container<T, Allocator>::const_reference
Compact_container<T, Allocator>::pointer
Compact_container<T, Allocator>::const_pointer
Compact_container<T, Allocator>::size_type
Compact_container<T, Allocator>::difference_type

Compact_container<T, Allocator>::iterator
Compact_container<T, Allocator>::const_iterator
Compact_container<T, Allocator>::reverse_iterator
Compact_container<T, Allocator>::const_reverse_iterator

Compact_container<T, Allocator>::allocator_type

Creation

Compact_container<T, Allocator> c ( Allocator a = Allocator());
introduces an empty container, eventually specifying a particular allocator a as well.


template <class InputIterator>
Compact_container<T, Allocator> c ( InputIterator first, InputIterator last, Allocator a = Allocator());
a container with copies from the range [first,last), eventually specifying a particular allocator.


Compact_container<T, Allocator> c ( cc);
copy constructor. Each item in cc is copied. The allocator is copied. The iterator order is preserved.

Compact_container<T, Allocator> & c = cc assignment. Each item in cc is copied. The allocator is copied. Each item in c is deleted. The iterator order is preserved.

void c.swap ( &cc) swaps the contents of c and cc in constant time complexity. No exception is thrown.

void c.reserve ( size_type value) if value is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for allocation of additional memory so that then capacity() is greater than or equal to value. size() is unchanged.

Access Member Functions

iterator c.begin () returns a mutable iterator referring to the first element in c.
const_iterator c.begin () const returns a constant iterator referring to the first element in c.
iterator c.end () returns a mutable iterator which is the past-end-value of c.
const_iterator c.end () const returns a constant iterator which is the past-end-value of c.

reverse_iterator c.rbegin ()
const_reverse_iterator c.rbegin () const
reverse_iterator c.rend ()
const_reverse_iterator c.rend () const

iterator c.iterator_to ( reference value) const
returns an iterator which points to value;
const_iterator c.iterator_to ( const_reference value) const
returns an iterator which points to value;

static iterator c.s_iterator_to ( reference value)
returns an iterator which points to value;
static const_iterator c.s_iterator_to ( const_reference value)
returns an iterator which points to value;

bool c.empty () returns true iff c is empty.
size_type c.size () returns the number of items in c.
size_type c.max_size () returns the maximum possible size of the container c.
size_type c.capacity () returns the total number of elements that c can hold without requiring reallocation.

Allocator c.get_allocator () returns the allocator.

Insertion

iterator c.insert ( T t) inserts a copy of t in c and returns the iterator pointing to it.

template <class InputIterator>
void c.insert ( InputIterator first, InputIterator last)
inserts the range [first, last) in c.

template <class InputIterator>
void c.assign ( InputIterator first, InputIterator last)
erases all the elements of c, then inserts the range [first, last) in c.

template < class T1 >
iterator c.emplace ( T1 t1) constructs an object of type T with the constructor that takes t1 as argument, inserts it in c, and returns the iterator pointing to it. Overloads of this member function are defined that take additional arguments, up to 9.

Removal

void c.erase ( iterator pos) removes the item pointed by pos from c.

void c.erase ( iterator first, iterator last)
removes the items from the range [first, last) from c.

void c.clear () all items in c are deleted, and the memory is deallocated. After this call, c is in the same state as if just default constructed.

Ownership testing

The following functions are mostly helpful for efficient debugging, since their complexity is O(√c.capacity()).

bool c.owns ( const_iterator pos) returns whether pos is in the range [c.begin(), c.end()] (c.end() included).

bool c.owns_dereferencable ( const_iterator pos)
returns whether pos is in the range [c.begin(), c.end()) (c.end() excluded).

Merging

void c.merge ( &cc) adds the items of cc to the end of c and cc becomes empty. The time complexity is O(c.capacity()-c.size()).
Precondition: cc must not be the same as c, and the allocators of c and cc need to be compatible : c.get_allocator() == cc.get_allocator().

Comparison Operations

bool c == cc test for equality: Two containers are equal, iff they have the same size and if their corresponding elements are equal.

bool c != cc test for inequality: returns !(c == cc).

bool c < cc compares in lexicographical order.

bool c > cc returns cc < c.

bool c <= cc returns !(c > cc).

bool c >= cc returns !(c < cc).

Next: Multiset<Type,Compare,Allocator>
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 4.0.1. 2 July 2012.