CGAL 5.4 - STL Extensions for CGAL
|
#include <CGAL/Concurrent_compact_container.h>
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. More... | |
Concurrent_compact_container & | operator= (const Concurrent_compact_container &ccc2) |
assignment. More... | |
void | swap (Self &ccc2) |
swaps the contents of ccc and ccc2 in constant time complexity. More... | |
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 . More... | |
size_type | max_size () const |
returns the maximum possible size of the container ccc . More... | |
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. More... | |
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. 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 [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. More... | |
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) . | |
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.
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.
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.
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
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()
).
ccc2
must not be the same as ccc
, and the allocators of ccc
and ccc2
must be compatible: ccc.get_allocator() == ccc2.get_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_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
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.