\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.11 - STL Extensions for CGAL
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Compact_container< T, Allocator > Class Template Reference

#include <CGAL/Compact_container.h>

Definition

An object of the class Compact_container is a container of objects of type T.

This container 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.

The objects stored in the Compact_container can optionally store an "erase counter". If it exists, i.e. if the object is a model of the ObjectWithEraseCounter concept, each time an object is erased from the container, the erase counter of the object will be incremented. For example, this erase counter can be exploited using the CC_safe_handle helper class, so that one can know if a handle is still pointing to the same element. Note that this is meaningful only because the CGAL::Compact_container doesn't deallocate elements until the destruction or clear() of the container.

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

Related Functions

(Note that these are not member functions.)

template<class T , class A >
std::size_t hash_value (const Compact_container< T, A >::iterator i)
 returns a hash value for the pointee of i.
 

Types

typedef unspecified_type value_type
 
typedef unspecified_type reference
 
typedef unspecified_type const_reference
 
typedef unspecified_type pointer
 
typedef unspecified_type const_pointer
 
typedef unspecified_type size_type
 
typedef unspecified_type difference_type
 
typedef unspecified_type iterator
 
typedef unspecified_type const_iterator
 
typedef unspecified_type reverse_iterator
 
typedef unspecified_type const_reverse_iterator
 
typedef unspecified_type allocator_type
 

Creation

 Compact_container (const Allocator &a=Allocator())
 introduces an empty container cc, eventually specifying a particular allocator a as well.
 
template<class InputIterator >
 Compact_container (InputIterator first, InputIterator last, const Allocator &a=Allocator())
 a container with copies from the range [first,last), eventually specifying a particular allocator.
 
 Compact_container (const Compact_container< T, Allocator > &cc2)
 copy constructor. More...
 
Compact_container< T, Allocator > & operator= (const Compact_container< T, Allocator > &cc2)
 assignment. More...
 
void swap (Compact_container< T, Allocator > &cc2)
 swaps the contents of cc and cc2 in constant time complexity. More...
 
void reserve (size_type value)
 if value is less than or equal to capacity(), this call has no effect. More...
 

Access Member Functions

iterator begin ()
 returns a mutable iterator referring to the first element in cc.
 
const_iterator begin () const
 returns a constant iterator referring to the first element in cc.
 
iterator end ()
 returns a mutable iterator which is the past-end-value of cc.
 
const_iterator end () const
 returns a constant iterator which is the past-end-value of cc.
 
reverse_iterator rbegin ()
 
const_reverse_iterator rbegin () const
 
reverse_iterator rend ()
 
const_reverse_iterator rend () const
 
iterator iterator_to (reference value) const
 returns an iterator which points to value.
 
const_iterator iterator_to (const_reference value) const
 returns an iterator which points to value.
 
bool empty () const
 returns true iff cc is empty.
 
size_type size () const
 returns the number of items in cc.
 
size_type max_size () const
 returns the maximum possible size of the container cc. More...
 
size_type capacity () const
 returns the total number of elements that cc can hold without requiring reallocation.
 
bool is_used (const_iterator pos) const
 returns true if the element pos is used (i.e. valid).
 
bool is_used (size_type i) const
 returns true if the element at position i in the container is used (i.e. valid). More...
 
const T & operator[] (size_type i) const
 returns the element at pos i in the container. More...
 
T & operator[] (size_type i)
 returns the element at pos i in the container. More...
 
Allocator get_allocator () const
 returns the allocator.
 
static iterator s_iterator_to (reference value)
 returns an iterator which points to value;
 
static const_iterator s_iterator_to (const_reference value)
 returns an iterator which points to value;
 

Insertion

iterator insert (const T &t)
 inserts a copy of t in cc and returns the iterator pointing to it.
 
template<class InputIterator >
void insert (InputIterator first, InputIterator last)
 inserts the range [first, last) in cc.
 
template<class InputIterator >
void assign (InputIterator first, InputIterator last)
 erases all the elements of cc, then inserts the range [first, last) in cc.
 
template<class T1 >
iterator emplace (const T1 &t1)
 constructs an object of type T with the constructor that takes t1 as argument, inserts it in cc, and returns the iterator pointing to it. More...
 

Removal

void erase (iterator pos)
 removes the item pointed by pos from cc.
 
void erase (iterator first, iterator last)
 removes the items from the range [first, last) from cc.
 
void clear ()
 all items in cc are deleted, and the memory is deallocated. More...
 

Ownership testing

The following functions are mostly helpful for efficient debugging, since their complexity is \( O(\sqrt{\mathrm{c.capacity()}})\).

bool owns (const_iterator pos)
 returns whether pos is in the range [cc.begin(), cc.end()] (cc.end() included).
 
bool owns_dereferencable (const_iterator pos)
 returns whether pos is in the range [cc.begin(), cc.end())(cc.end()` excluded).
 

Merging

void merge (Compact_container< T, Allocator > &cc)
 adds the items of cc2 to the end of cc and cc2 becomes empty. More...
 

Comparison Operations

bool operator== (const Compact_container< T, Allocator > &cc) const
 test for equality: Two containers are equal, iff they have the same size and if their corresponding elements are equal.
 
bool operator!= (const Compact_container< T, Allocator > &cc) const
 test for inequality: returns !(c == cc).
 
bool operator< (const Compact_container< T, Allocator > &cc2) const
 compares in lexicographical order.
 
bool operator> (const Compact_container< T, Allocator > &cc2) const
 returns cc2 <cc.
 
bool operator<= (const Compact_container< T, Allocator > &cc2) const
 returns !(cc > cc2).
 
bool operator>= (const Compact_container< T, Allocator > &cc2) const
 returns !(cc < cc2).
 

Constructor & Destructor Documentation

template<typename T , typename Allocator >
CGAL::Compact_container< T, Allocator >::Compact_container ( const Compact_container< T, Allocator > &  cc2)

copy constructor.

Each item in cc2 is copied. The allocator is copied. The iterator order is preserved.

Member Function Documentation

template<typename T , typename Allocator >
void CGAL::Compact_container< T, Allocator >::clear ( )

all items in cc are deleted, and the memory is deallocated.

After this call, cc is in the same state as if just default constructed.

template<typename T , typename Allocator >
template<class T1 >
iterator CGAL::Compact_container< T, Allocator >::emplace ( const T1 &  t1)

constructs an object of type T with the constructor that takes t1 as argument, inserts it in cc, and returns the iterator pointing to it.

Overloads of this member function are defined that take additional arguments, up to 9.

template<typename T , typename Allocator >
bool CGAL::Compact_container< T, Allocator >::is_used ( size_type  i) const

returns true if the element at position i in the container is used (i.e. valid).

Precondition
\( 0 \leq \) i \( < \) capacity()
template<typename T , typename Allocator >
size_type CGAL::Compact_container< T, Allocator >::max_size ( ) const

returns the maximum possible size of the container cc.

This is the allocator's max_size value.

template<typename T , typename Allocator >
void CGAL::Compact_container< T, Allocator >::merge ( Compact_container< T, Allocator > &  cc)

adds the items of cc2 to the end of cc and cc2 becomes empty.

The time complexity is O(cc.capacity()-cc.size()).

Precondition
cc2 must not be the same as cc, and the allocators of cc and cc2 must be compatible: cc.get_allocator() == cc2.get_allocator().
template<typename T , typename Allocator >
Compact_container<T, Allocator>& CGAL::Compact_container< T, Allocator >::operator= ( const Compact_container< T, Allocator > &  cc2)

assignment.

Each item in cc2 is copied. The allocator is copied. Each item in c is deleted. The iterator order is preserved.

template<typename T , typename Allocator >
const T& CGAL::Compact_container< T, Allocator >::operator[] ( size_type  i) const

returns the element at pos i in the container.

Precondition
is_used(i) == true and \( 0 \leq \) i \( < \) capacity()
template<typename T , typename Allocator >
T& CGAL::Compact_container< T, Allocator >::operator[] ( size_type  i)

returns the element at pos i in the container.

Precondition
is_used(i) == true and \( 0 \leq \) i \( < \) capacity()
template<typename T , typename Allocator >
void CGAL::Compact_container< T, Allocator >::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.

template<typename T , typename Allocator >
void CGAL::Compact_container< T, Allocator >::swap ( Compact_container< T, Allocator > &  cc2)

swaps the contents of cc and cc2 in constant time complexity.

No exception is thrown.