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 developped 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>.
#include <CGAL/Compact_container.h>
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).
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
| |||
introduces an empty container, eventually specifying a particular
allocator a as well.
| |||
| |||
| |||
a container with copies from the range [first,last), eventually
specifying a particular allocator.
| |||
| |||
copy constructor. Each item in cc is copied. The allocator
is copied. The iterator order is preserved.
|
| ||
| assignment. Each item in cc is copied. The allocator is copied. Each item in c is deleted. The iterator order is preserved. | |
|
| swaps the contents of c and cc in constant time complexity. No exception is thrown. |
|
| inserts a copy of t in c and returns the iterator pointing to it. |
| ||
|
| |
inserts the range [first, last) in c. | ||
| ||
|
| |
erases all the elements of c, then inserts the range [first, last) in c. | ||
| ||
|
| |
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. The same constructor exists for up to nine arguments. |