CGAL 4.7 - STL Extensions for CGAL: CGAL::In_place_list< T, bool > Class Template Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - STL Extensions for CGAL

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Public Member Functions | Related Functions
CGAL::In_place_list< T, bool > Class Template Reference
Doubly-Connected List Managing Items in Place

`#include <CGAL/In_place_list.h>`

## Definition

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

#include <cassert>
#include <algorithm>
#include <CGAL/In_place_list.h>
using CGAL::In_place_list_base;
struct item : public In_place_list_base<item> {
int key;
item() {}
item( const item& i) : In_place_list_base<item>(i), key(i.key) {}
item( int i) : key(i) {}
bool operator== (const item& i) const { return key == i.key;}
bool operator!= (const item& i) const { return ! (*this == i);}
bool operator== (int i) const { return key == i;}
bool operator!= (int i) const { return ! (*this == i);}
bool operator< (const item& i) const { return key < i.key;}
};
int main() {
typedef CGAL::In_place_list<item,true> List;
List l;
item* p = new item(1);
l.push_back(*p);
l.push_back(*new item(2));
l.push_front(*new item(3));
l.push_front(*new item(4));
l.push_front(*new item(2));
List::iterator i = l.begin();
++i;
l.insert(i, *new item(5));
l.insert(p, *new item(5));
int a[7] = {2,5,4,3,5,1,2};
bool ok = std::equal(l.begin(), l.end(), a);
assert(ok);
l.sort();
l.unique();
assert(l.size() == 5);
int b[5] = {1,2,3,4,5};
ok = std::equal(l.begin(), l.end(), b);
assert(ok);
return 0;
}

Examples:
  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...

## Constructor & Destructor Documentation

template<typename T , bool >

CGAL::In_place_list< T, bool >::In_place_list | ( | const list< T > & | l1) |  |

copy constructor.

Each item in `l1` is copied.

## Member Function Documentation

template<typename T , bool >

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.

template<typename T , bool >

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.

template<typename T , bool >

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.

Precondition
  Both lists are increasingly sorted. A suitable `operator<` for the type `T`.

template<typename T , bool >

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

template<typename T , bool >

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.

Precondition
  a suitable `operator==` for the type `T`.

template<typename T , bool >

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.

Precondition
  a suitable `operator<` for the type `T`.

template<typename T , bool >

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.

Precondition
  `(& ipl) != (& ipl2)`.

template<typename T , bool >

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.

Precondition
  `(& ipl) != (& ipl2)`.

template<typename T , bool >

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

template<typename T , bool >

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

template<typename T , bool >

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\).

Precondition
  `pos` is not in the range [`first, last`).

template<typename T , bool >

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

Precondition
  a suitable `operator==` for the type `T`.