\( \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.4 - STL Extensions for CGAL
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::In_place_list< T, bool > Class Template Reference

#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>
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() {
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.
 

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.