CGAL 6.1 - STL Extensions for CGAL

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

`#include <CGAL/Concurrent_compact_container.h>`

## Definition

template<class T, class Allocator>
class CGAL::Concurrent_compact_container< T, Allocator >

An object of the class `Concurrent_compact_container` is a container of objects of type `T`, which allows to call `insert` and `erase` operations concurrently.

Other operations are not concurrency-safe. For example, one should not parse the container while others are modifying it. 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.

The objects stored in the `Concurrent_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::Concurrent_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)`.

## Types
typedef unspecified_type | value_type
typedef unspecified_type | allocator_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

## Creation
| Concurrent_compact_container (const Allocator &a=Allocator())
| introduces an empty container `ccc`, eventually specifying a particular allocator `a` as well.
template<class InputIterator >
| Concurrent_compact_container (InputIterator first, InputIterator last, const Allocator &a=Allocator())
| a container with copies from the range [`first,last`), eventually specifying a particular allocator.
| Concurrent_compact_container (const Concurrent_compact_container &ccc2)
| copy constructor.
Concurrent_compact_container & | operator= (const Concurrent_compact_container &ccc2)
| assignment.
void | swap (Self &ccc2)
| swaps the contents of `ccc` and `ccc2` in constant time complexity.

## Access Member Functions
bool | is_used (const_iterator pos) const
| returns true if the element `pos` is used (i.e. valid).
iterator | begin ()
| returns a mutable iterator referring to the first element in `ccc`.
const_iterator | begin () const
| returns a constant iterator referring to the first element in `ccc`.
iterator | end ()
| returns a mutable iterator which is the past-end-value of `ccc`.
const_iterator | end ()
| returns a constant iterator which is the past-end-value of `ccc`.
reverse_iterator | rbegin ()
| returns a mutable reverse iterator referring to the reverse beginning in `ccc`.
const_reverse_iterator | rbegin () const
| returns a constant reverse iterator referring to the reverse beginning in `ccc`.
reverse_iterator | rend ()
| returns a mutable reverse iterator which is the reverse past-end-value of `ccc`.
const_reverse_iterator | rend () const
| returns a constant reverse iterator which is the reverse past-end-value of `ccc`.
iterator | iterator_to (reference value) const
| returns an iterator which points to `value`.
const_iterator | iterator_to (const_reference value) const
| returns a constant iterator which points to `value`.
bool | empty () const
| returns `true` iff `ccc` is empty.
size_type | size () const
| returns the number of items in `ccc`.
size_type | max_size () const
| returns the maximum possible size of the container `ccc`.
size_type | capacity () const
| returns the total number of elements that `ccc` can hold without requiring reallocation.
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 a constant iterator which points to `value`.

## Insertion
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 `ccc`, and returns the iterator pointing to it.
iterator | insert (const T &t)
| inserts a copy of `t` in `ccc` and returns the iterator pointing to it.
template<class InputIterator >
void | insert (InputIterator first, InputIterator last)
| inserts the range [`first, last`) in `ccc`.
template<class InputIterator >
void | assign (InputIterator first, InputIterator last)
| erases all the elements of `ccc`, then inserts the range [`first, last`) in `ccc`.

## Removal
void | erase (iterator x)
| removes the item pointed by `pos` from `ccc`.
void | erase (iterator first, iterator last)
| removes the items from the range [`first, last`) from `ccc`.
void | clear ()
| all items in `ccc` 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 `[ccc.begin(), ccc.end()]` (`ccc.end()` included).
bool | owns_dereferencable (const_iterator pos)
| returns whether `pos` is in the range `[ccc.begin(), ccc.end())` (`ccc.end()` excluded).

## Merging
void | merge (Concurrent_compact_container< T, Allocator > &ccc2)
| adds the items of `ccc2` to the end of `ccc` and `ccc2` becomes empty.

## Comparison Operations
bool | operator== (const Concurrent_compact_container< T, Allocator > &ccc2) const
| test for equality: Two containers are equal, iff they have the same size and if their corresponding elements are equal.
bool | operator!= (const Concurrent_compact_container< T, Allocator > &ccc2) const
| test for inequality: returns `!(ccc == ccc2)`.
bool | operator< (const Concurrent_compact_container< T, Allocator > &ccc2) const
| compares in lexicographical order.
bool | operator> (const Concurrent_compact_container< T, Allocator > &ccc2) const
| returns `ccc2 < ccc`.
bool | operator<= (const Concurrent_compact_container< T, Allocator > &ccc2) const
| returns `!(ccc > ccc2)`.
bool | operator>= (const Concurrent_compact_container< T, Allocator > &ccc2) const
| returns `!(ccc < ccc2)`.

## Constructor & Destructor Documentation

## ◆ Concurrent_compact_container()

template<class T , class Allocator >

CGAL::Concurrent_compact_container< T, Allocator >::Concurrent_compact_container | ( | const Concurrent_compact_container< T, Allocator > & | ccc2 | ) |

copy constructor.

Each item in `ccc2` is copied. The allocator is copied. The iterator order is preserved.

## Member Function Documentation

## ◆ clear()

template<class T , class Allocator >

void CGAL::Concurrent_compact_container< T, Allocator >::clear | ( |  | ) |

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

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

## ◆ emplace()

template<class T , class Allocator >
template<class T1 >

iterator CGAL::Concurrent_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 `ccc`, and returns the iterator pointing to it.

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

## ◆ max_size()

template<class T , class Allocator >

size_type CGAL::Concurrent_compact_container< T, Allocator >::max_size | ( |  | ) | const

returns the maximum possible size of the container `ccc`.

This is the allocator's max_size value

## ◆ merge()

template<class T , class Allocator >

void CGAL::Concurrent_compact_container< T, Allocator >::merge | ( | Concurrent_compact_container< T, Allocator > & | ccc2 | ) |

adds the items of `ccc2` to the end of `ccc` and `ccc2` becomes empty.

The time complexity is \(O(ccc.capacity()-ccc.size())\).

Precondition
  `ccc2` must not be the same as `ccc`, and the allocators of `ccc` and `ccc2` must be compatible: `ccc.get_allocator() == ccc2.get_allocator()`.

## ◆ operator=()

template<class T , class Allocator >

Concurrent_compact_container & CGAL::Concurrent_compact_container< T, Allocator >::operator= | ( | const Concurrent_compact_container< T, Allocator > & | ccc2 | ) |

assignment.

Each item in `ccc2` is copied. The allocator is copied. Each item in `ccc` is deleted. The iterator order is preserved.

## ◆ size()

template<class T , class Allocator >

size_type CGAL::Concurrent_compact_container< T, Allocator >::size | ( |  | ) | const

returns the number of items in `ccc`.

Note: do not call this function while others are inserting/erasing elements

## ◆ swap()

template<class T , class Allocator >

void CGAL::Concurrent_compact_container< T, Allocator >::swap | ( | Self & | ccc2 | ) |

swaps the contents of `ccc` and `ccc2` in constant time complexity.

No exception is thrown.