CGAL 6.1 - STL Extensions for CGAL

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Compact_container< T, Allocator > Class Template Reference
Reference Manual » Compact Container

`#include <CGAL/Compact_container.h>`

## Definition

template<typename T, typename Allocator>
class CGAL::Compact_container< T, Allocator >

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 `nullptr` 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.
Compact_container< T, Allocator > & | operator= (const Compact_container< T, Allocator > &cc2)
| assignment.
void | swap (Compact_container< T, Allocator > &cc2)
| swaps the contents of `cc` and `cc2` in constant time complexity.
void | reserve (size_type value)
| if `value` is less than or equal to `capacity()`, this call has no effect.

## 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`.
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).
const T & | operator[] (size_type i) const
| returns the element at pos `i` in the container.
T & | operator[] (size_type i)
| returns the element at pos `i` in the container.
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.

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

## 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_dereferenceable (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.

## 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

## ◆ Compact_container()

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

## ◆ clear()

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.

## ◆ emplace()

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.

## ◆ is_used()

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()`

## ◆ max_size()

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.

## ◆ merge()

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

## ◆ operator=()

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.

## ◆ operator[]() [1/2]

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()`

## ◆ operator[]() [2/2]

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()`

## ◆ reserve()

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.

## ◆ swap()

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.