CGAL::In_place_list< T, bool > Class Template Reference

#include <CGAL/In_place_list.h>

Definition

template<typename T, bool>
class CGAL::In_place_list< T, bool >

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.
	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.
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.
iterator	insert (T *pos, T &t)
	inserts t in front of pos.
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.
void	splice (iterator pos, In_place_list< T, bool > &ipl2, iterator i)
	inserts the list ipl2 before position pos and ipl2 becomes empty.
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.
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.
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\).
void	remove (const T &value)
	erases all elements \( e\) in the list ipl for which e == value.
void	unique ()
	erases all but the first element from every consecutive group of equal elements in the list ipl.
void	merge (In_place_list< T, bool > &ipl2)
	merges the list ipl2 into the list ipl and ipl2 becomes empty.
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().

Constructor & Destructor Documentation

In_place_list()

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

insert() [1/2]

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.

insert() [2/2]

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.

merge()

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 sorted in increasing order by means of a suitable operator< for the type T.

operator=()

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.

remove()

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.

sort()

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.

splice() [1/5]

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

splice() [2/5]

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.

splice() [3/5]

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

splice() [4/5]

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.

splice() [5/5]

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

unique()

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.