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. More...
	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. More...
template<class InputIterator >
	In_place_list (InputIterator first, InputIterator last)
	introduces a list ipl with copies from the range [first,last). More...
	In_place_list (const T *first, const T *last)
	introduces a list ipl with copies from the range [first,last). More...
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. More...
void	destroy ()
	all items in ipl are deleted regardless of the bool parameter. More...

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

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. More...
bool	operator< (const In_place_list< T, bool > &ipl2) const
	compares in lexicographical order. More...

Access Member Functions
iterator	begin ()
	returns a mutable iterator referring to the first element in ipl. More...
const_iterator	begin () const
	returns a constant iterator referring to the first element in ipl. More...
iterator	end ()
	returns a mutable iterator which is the past-end-value of ipl. More...
const_iterator	end () const
	returns a constant iterator which is the past-end-value of ipl. More...
bool	empty () const
	returns true if ipl is empty. More...
size_type	size () const
	returns the number of items in list ipl. More...
size_type	max_size () const
	returns the maximum possible size of the list l. More...
T &	front ()
	returns the first item in list ipl. More...
T &	back ()
	returns the last item in list ipl. More...
allocator_type	get_allocator () const
	returns the allocator. More...

Insertion
void	push_front (T &)
	inserts an item in front of list ipl. More...
void	push_back (T &)
	inserts an item at the back of list ipl. More...
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. More...
void	insert (T *pos, size_type n, const T &t=T())
	inserts \( n\) copies of t in front of pos. More...
template<class InputIterator >
void	insert (iterator pos, InputIterator first, InputIterator last)
	inserts the range [first, last) in front of iterator pos. More...
template<class InputIterator >
void	insert (T *pos, InputIterator first, InputIterator last)
	inserts the range [first, last) in front of iterator pos. More...

Removal
void	pop_front ()
	removes the first item from list ipl. More...
void	pop_back ()
	removes the last item from list ipl. More...
void	erase (iterator pos)
	removes the item from list ipl, where pos refers to. More...
void	erase (T *pos)
	removes the item from list ipl, where pos refers to. More...
void	erase (iterator first, iterator last)
void	erase (T *first, T *last)
	removes the items in the range [first, last) from ipl. More...

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. More...
void	sort ()
	sorts the list ipl according to the operator< in time \( O(n \log n)\) where n = size(). More...

Member Typedef Documentation

allocator_type

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::allocator_type

const_iterator

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::const_iterator

const_reference

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::const_reference

const_reverse_iterator

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::const_reverse_iterator

difference_type

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::difference_type

iterator

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::iterator

reference

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::reference

reverse_iterator

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::reverse_iterator

size_type

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::size_type

value_type

template<typename T , bool >

typedef unspecified_type CGAL::In_place_list< T, bool >::value_type

Constructor & Destructor Documentation

In_place_list() [1/5]

template<typename T , bool >

CGAL::In_place_list< T, bool >::In_place_list

(

)

introduces an empty list ipl.

In_place_list() [2/5]

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.

In_place_list() [3/5]

template<typename T , bool >

CGAL::In_place_list< T, bool >::In_place_list	(	size_type	n,
		const T &	t = T()
	)

introduces a list ipl with n items, all initialized with copies of t.

In_place_list() [4/5]

template<typename T , bool >

template<class InputIterator >

CGAL::In_place_list< T, bool >::In_place_list	(	InputIterator	first,
		InputIterator	last
	)

introduces a list ipl with copies from the range [first,last).

In_place_list() [5/5]

template<typename T , bool >

CGAL::In_place_list< T, bool >::In_place_list	(	const T *	first,
		const T *	last
	)

introduces a list ipl with copies from the range [first,last).

Member Function Documentation

back()

template<typename T , bool >

T& CGAL::In_place_list< T, bool >::back

(

)

returns the last item in list ipl.

begin() [1/2]

template<typename T , bool >

iterator CGAL::In_place_list< T, bool >::begin

(

)

returns a mutable iterator referring to the first element in ipl.

begin() [2/2]

template<typename T , bool >

const_iterator CGAL::In_place_list< T, bool >::begin

(

)

const

returns a constant iterator referring to the first element in ipl.

destroy()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::destroy

(

)

all items in ipl are deleted regardless of the bool parameter.

empty()

template<typename T , bool >

bool CGAL::In_place_list< T, bool >::empty

(

)

const

returns true if ipl is empty.

end() [1/2]

template<typename T , bool >

iterator CGAL::In_place_list< T, bool >::end

(

)

returns a mutable iterator which is the past-end-value of ipl.

end() [2/2]

template<typename T , bool >

const_iterator CGAL::In_place_list< T, bool >::end

(

)

const

returns a constant iterator which is the past-end-value of ipl.

erase() [1/4]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::erase	(	iterator	first,
		iterator	last
	)

erase() [2/4]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::erase

(

iterator

pos

)

removes the item from list ipl, where pos refers to.

erase() [3/4]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::erase	(	T *	first,
		T *	last
	)

removes the items in the range [first, last) from ipl.

erase() [4/4]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::erase

(

T *

pos

)

removes the item from list ipl, where pos refers to.

front()

template<typename T , bool >

T& CGAL::In_place_list< T, bool >::front

(

)

returns the first item in list ipl.

get_allocator()

template<typename T , bool >

allocator_type CGAL::In_place_list< T, bool >::get_allocator

(

)

const

returns the allocator.

insert() [1/6]

template<typename T , bool >

template<class InputIterator >

void CGAL::In_place_list< T, bool >::insert	(	iterator	pos,
		InputIterator	first,
		InputIterator	last
	)

inserts the range [first, last) in front of iterator pos.

insert() [2/6]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::insert	(	iterator	pos,
		size_type	n,
		const T &	t = T()
	)

inserts \( n\) copies of t in front of pos.

insert() [3/6]

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() [4/6]

template<typename T , bool >

template<class InputIterator >

void CGAL::In_place_list< T, bool >::insert	(	T *	pos,
		InputIterator	first,
		InputIterator	last
	)

inserts the range [first, last) in front of iterator pos.

insert() [5/6]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::insert	(	T *	pos,
		size_type	n,
		const T &	t = T()
	)

inserts \( n\) copies of t in front of pos.

insert() [6/6]

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.

max_size()

template<typename T , bool >

size_type CGAL::In_place_list< T, bool >::max_size

(

)

const

returns the maximum possible size of the list l.

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 increasingly sorted. A suitable operator< for the type T.

operator<()

template<typename T , bool >

bool CGAL::In_place_list< T, bool >::operator<

(

const In_place_list< T, bool > &

ipl2

)

const

compares in lexicographical order.

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.

operator==()

template<typename T , bool >

bool CGAL::In_place_list< T, 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.

pop_back()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::pop_back

(

)

removes the last item from list ipl.

pop_front()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::pop_front

(

)

removes the first item from list ipl.

push_back()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::push_back

(

T &

)

inserts an item at the back of list ipl.

push_front()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::push_front

(

T &

)

inserts an item in front of list ipl.

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.

reverse()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::reverse

(

)

reverses the order of the elements in ipl in linear time.

size()

template<typename T , bool >

size_type CGAL::In_place_list< T, bool >::size

(

)

const

returns the number of items in list ipl.

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/6]

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/6]

template<typename T , bool >

void CGAL::In_place_list< T, bool >::splice	(	iterator	pos,
		In_place_list< T, bool > &	x
	)

splice() [3/6]

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() [4/6]

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() [5/6]

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() [6/6]

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

swap()

template<typename T , bool >

void CGAL::In_place_list< T, bool >::swap

(

const In_place_list< T, bool > &

ipl2

)

swaps the contents of ipl with ipl2.

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.

Friends And Related Function Documentation

hash_value() [1/2]

template<class T , class bool >

std::size_t hash_value ( const In_place_list< T, bool >::const_iterator  i )

related

returns a hash value for the pointee of i.

hash_value() [2/2]

template<class T , bool >

std::size_t hash_value ( const In_place_list< T, bool >::iterator  i )

related

returns a hash value for the pointee of i.