CGAL 5.4 - STL Extensions for CGAL
|
#include <CGAL/In_place_list.h>
An object of the class In_place_list
represents a sequence of items of type T
that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence.
The functionality is similar to the std::list<T>
in the STL.
The In_place_list
manages the items in place, i.e., inserted items are not copied. Two pointers of type T*
are expected to be reserved in T
for the list management. The base class In_place_list_base<T>
can be used to obtain such pointers.
The In_place_list
does not copy element items during insertion (unless otherwise stated for a function). On removal of an item or destruction of the list the items are not deleted by default. The second template parameter bool
is set to false
in this case. If the In_place_list
should take the responsibility for the stored objects the bool
parameter could be set to true
, in which case the list will delete removed items and will delete all remaining items on destruction. In any case, the destroy()
member function deletes all items. Note that these two possible versions of In_place_list
are not assignable to each other to avoid confusions between the different storage responsibilities.
Parameters
The full class name is In_place_list<T, bool managed = false, class Alloc = CGAL_ALLOCATOR(T)>
.
The parameter T
is supposed to have a default constructor, a copy constructor and an assignment operator. The copy constructor and the assignment may copy the pointers in T
for the list management, but they do not have to. The equality test and the relational order require the operators ==
and <
for T
respectively. These operators must not compare the pointers in T
.
Example
File STL_Extension/in_place_list_prog.cpp
Public Member Functions | |
In_place_list () | |
introduces an empty list ipl . | |
In_place_list (const list< T > &l1) | |
copy constructor. More... | |
In_place_list (size_type n, const T &t=T()) | |
introduces a list ipl with n items, all initialized with copies of t . | |
template<class InputIterator > | |
In_place_list (InputIterator first, InputIterator last) | |
introduces a list ipl with copies from the range [first,last ). | |
In_place_list (const T *first, const T *last) | |
introduces a list ipl with copies from the range [first,last ). | |
In_place_list< T, bool > & | operator= (const In_place_list< T, bool > &ipl2) |
assignment. More... | |
void | swap (const In_place_list< T, bool > &ipl2) |
swaps the contents of ipl with ipl2 . | |
void | destroy () |
all items in ipl are deleted regardless of the bool parameter. | |
Related Functions | |
(Note that these are not member functions.) | |
template<class T , bool > | |
std::size_t | hash_value (const In_place_list< T, bool >::iterator i) |
returns a hash value for the pointee of i . | |
template<class T , class bool > | |
std::size_t | hash_value (const In_place_list< T, bool >::const_iterator i) |
returns a hash value for the pointee of i . | |
Types | |
typedef unspecified_type | iterator |
typedef unspecified_type | const_iterator |
typedef unspecified_type | value_type |
typedef unspecified_type | reference |
typedef unspecified_type | const_reference |
typedef unspecified_type | size_type |
typedef unspecified_type | difference_type |
typedef unspecified_type | reverse_iterator |
typedef unspecified_type | const_reverse_iterator |
typedef unspecified_type | allocator_type |
Comparison Operations | |
bool | operator== (const In_place_list< T, bool > &ipl2) const |
test for equality: Two lists are equal, iff they have the same size and if their corresponding elements are equal. | |
bool | operator< (const In_place_list< T, bool > &ipl2) const |
compares in lexicographical order. | |
Access Member Functions | |
iterator | begin () |
returns a mutable iterator referring to the first element in ipl . | |
const_iterator | begin () const |
returns a constant iterator referring to the first element in ipl . | |
iterator | end () |
returns a mutable iterator which is the past-end-value of ipl . | |
const_iterator | end () const |
returns a constant iterator which is the past-end-value of ipl . | |
bool | empty () const |
returns true if ipl is empty. | |
size_type | size () const |
returns the number of items in list ipl . | |
size_type | max_size () const |
returns the maximum possible size of the list l . | |
T & | front () |
returns the first item in list ipl . | |
T & | back () |
returns the last item in list ipl . | |
allocator_type | get_allocator () const |
returns the allocator. | |
Insertion | |
void | push_front (T &) |
inserts an item in front of list ipl . | |
void | push_back (T &) |
inserts an item at the back of list ipl . | |
iterator | insert (iterator pos, T &t) |
inserts t in front of pos . More... | |
iterator | insert (T *pos, T &t) |
inserts t in front of pos . More... | |
void | insert (iterator pos, size_type n, const T &t=T()) |
inserts \( n\) copies of t in front of pos . | |
void | insert (T *pos, size_type n, const T &t=T()) |
inserts \( n\) copies of t in front of pos . | |
template<class InputIterator > | |
void | insert (iterator pos, InputIterator first, InputIterator last) |
inserts the range [first, last ) in front of iterator pos . | |
template<class InputIterator > | |
void | insert (T *pos, InputIterator first, InputIterator last) |
inserts the range [first, last ) in front of iterator pos . | |
Removal | |
void | pop_front () |
removes the first item from list ipl . | |
void | pop_back () |
removes the last item from list ipl . | |
void | erase (iterator pos) |
removes the item from list ipl , where pos refers to. | |
void | erase (T *pos) |
removes the item from list ipl , where pos refers to. | |
void | erase (iterator first, iterator last) |
void | erase (T *first, T *last) |
removes the items in the range [first, last ) from ipl . | |
Special List Operations | |
void | splice (iterator pos, In_place_list< T, bool > &x) |
void | splice (T *pos, In_place_list< T, bool > &ipl2) |
inserts the list ipl2 before position pos and ipl2 becomes empty. More... | |
void | splice (iterator pos, In_place_list< T, bool > &ipl2, iterator i) |
inserts the list ipl2 before position pos and ipl2 becomes empty. More... | |
void | splice (T *pos, In_place_list< T, bool > &ipl2, T *i) |
inserts an element pointed to by i from list ipl2 before position pos and removes the element from ipl . More... | |
void | splice (iterator pos, In_place_list< T, bool > &x, iterator first, iterator last) |
inserts an element pointed to by i from list ipl2 before position pos and removes the element from ipl . More... | |
void | splice (T *pos, In_place_list< T, bool > &x, T *first, T *last) |
inserts elements in the range [first, last ) before position pos and removes the elements from \( x\). More... | |
void | remove (const T &value) |
erases all elements \( e\) in the list ipl for which e == value . More... | |
void | unique () |
erases all but the first element from every consecutive group of equal elements in the list ipl . More... | |
void | merge (In_place_list< T, bool > &ipl2) |
merges the list ipl2 into the list ipl and ipl2 becomes empty. More... | |
void | reverse () |
reverses the order of the elements in ipl in linear time. | |
void | sort () |
sorts the list ipl according to the operator< in time \( O(n \log n)\) where n = size() . More... | |
CGAL::In_place_list< T, bool >::In_place_list | ( | const list< T > & | l1 | ) |
copy constructor.
Each item in l1
is copied.
iterator CGAL::In_place_list< T, bool >::insert | ( | iterator | pos, |
T & | t | ||
) |
inserts t
in front of pos
.
The return value points to the inserted item.
iterator CGAL::In_place_list< T, bool >::insert | ( | T * | pos, |
T & | t | ||
) |
inserts t
in front of pos
.
The return value points to the inserted item.
void CGAL::In_place_list< T, bool >::merge | ( | In_place_list< T, bool > & | ipl2 | ) |
merges the list ipl2
into the list ipl
and ipl2
becomes empty.
It is stable.
operator<
for the type T
. In_place_list<T,bool>& CGAL::In_place_list< T, bool >::operator= | ( | const In_place_list< T, bool > & | ipl2 | ) |
assignment.
Each item in ipl2
is copied. Each item in ipl
is deleted if the bool
parameter is true
.
void CGAL::In_place_list< T, bool >::remove | ( | const T & | value | ) |
erases all elements \( e\) in the list ipl
for which e == value
.
It is stable.
operator==
for the type T
. void CGAL::In_place_list< T, bool >::sort | ( | ) |
sorts the list ipl
according to the operator<
in time \( O(n \log n)\) where n = size()
.
It is stable.
operator<
for the type T
. void CGAL::In_place_list< T, bool >::splice | ( | T * | pos, |
In_place_list< T, bool > & | ipl2 | ||
) |
inserts the list ipl2
before position pos
and ipl2
becomes empty.
It takes constant time.
(& ipl) != (& ipl2)
. void CGAL::In_place_list< T, bool >::splice | ( | iterator | pos, |
In_place_list< T, bool > & | ipl2, | ||
iterator | i | ||
) |
inserts the list ipl2
before position pos
and ipl2
becomes empty.
It takes constant time.
(& ipl) != (& ipl2)
. void CGAL::In_place_list< T, bool >::splice | ( | T * | pos, |
In_place_list< T, bool > & | ipl2, | ||
T * | i | ||
) |
inserts an element pointed to by i
from list ipl2
before position pos
and removes the element from ipl
.
It takes constant time. i
is a valid dereferenceable iterator of ipl2
. The result is unchanged if pos == i
or pos == ++i
.
void CGAL::In_place_list< T, bool >::splice | ( | iterator | pos, |
In_place_list< T, bool > & | x, | ||
iterator | first, | ||
iterator | last | ||
) |
inserts an element pointed to by i
from list ipl2
before position pos
and removes the element from ipl
.
It takes constant time. i
is a valid dereferenceable iterator of ipl2
. The result is unchanged if pos == i
or pos == ++i
.
void CGAL::In_place_list< T, bool >::splice | ( | T * | pos, |
In_place_list< T, bool > & | x, | ||
T * | first, | ||
T * | last | ||
) |
inserts elements in the range [first, last
) before position pos
and removes the elements from \( x\).
It takes constant time if &x == &
l
; otherwise, it takes linear time. [first, last
) is a valid range in \( x\).
pos
is not in the range [first, last
). void CGAL::In_place_list< T, bool >::unique | ( | ) |
erases all but the first element from every consecutive group of equal elements in the list ipl
.
operator==
for the type T
.