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

Definition

Public Member Functions

Related Functions

Types

Comparison Operations

Access Member Functions

Insertion

Removal

Special List Operations

Constructor & Destructor Documentation

Member Function Documentation