This is a variant on a list that never invalidates iterators (unless, of course, the list ceases to exist). More...

#include <smart_list.hpp>

Classes
struct	const_iterator

struct	const_reverse_iterator

struct	iterator

class	iterator_base
	The base for the list's iterator classes. More...

struct	node_t
	Nodes in the smart list. More...

struct	reverse_iterator

Public Types
typedef Data	value_type

typedef value_type *	pointer

typedef value_type &	reference

typedef const value_type &	const_reference

typedef size_t	size_type

Public Member Functions
	smart_list ()

	smart_list (size_type n)
	Sized constructor. More...

	smart_list (size_type n, const value_type &d)
	Sized constructor with a value. More...

	smart_list (const smart_list &that)
	Copy constructor. More...

template<class InputIterator >
	smart_list (const InputIterator &f, const InputIterator &l)
	Constructor from a range. More...

	~smart_list ()

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

size_type	size () const
	The size of the list, not counting flagged nodes. More...

size_type	max_size () const

bool	empty () const
	Note: if empty() returns true, the list might still contain nodes flagged for deletion. More...

reference	front ()

const_reference	front () const

reference	back ()

const_reference	back () const

void	push_front (const value_type &d)

void	push_back (const value_type &d)

void	pop_front ()

void	pop_back ()

void	swap (smart_list &that)
	Swaps two lists. More...

void	clear ()

void	resize (size_type n)

void	resize (size_type n, const value_type &d)
	Resize the list. More...

void	splice (const iterator &pos, smart_list &L)
	Splice all of L into this before pos*. More...

void	splice (const iterator &pos, smart_list &L, const iterator &i)
	Splice the node i points to (assumed from L) into this before pos*. More...

void	splice (const iterator &pos, smart_list &L, const iterator &f, const iterator &l)
	Splice a range (assumed from L) into this before pos*. More...

void	remove (const value_type &value)
	Remove all nodes whose data equals value. More...

template<class Predicate >
void	remove_if (const Predicate &p)
	Remove all nodes whose data satisfies p. More...

void	unique ()

template<class BinaryPredicate >
void	unique (const BinaryPredicate p)
	Remove nodes equal (under p) to their immediate predecessor. More...

void	merge (smart_list &L)

template<class BinaryPredicate >
void	merge (smart_list &L, const BinaryPredicate &p)
	Merge L into *this, using p to determine order. More...

void	sort ()

template<class BinaryPredicate >
void	sort (const BinaryPredicate &p)
	Sort *this, using the order given by p. More...

Static Public Member Functions
static iterator	insert (const iterator &pos, const value_type &d)
	Insert a node before pos. More...

template<class InputIterator >
static void	insert (const iterator &pos, const InputIterator &f, const InputIterator &l)
	Insert a range before pos. More...

static void	insert (const iterator &pos, size_type n, const value_type &d)
	Insert n copies of d at pos. More...

static iterator	erase (const iterator &pos)
	Erase the node at pos. More...

static iterator	erase (const iterator &start, const iterator &stop)
	Erase a range of nodes. More...

Private Member Functions
smart_list &	operator= (const smart_list &)
	No implementation of operator=() since that would not preserve iterators. More...

Static Private Member Functions
static bool	flagged (const node_t &node)
	Returns true if node has been flagged for deletion. More...

static void	flag (const node_t &node)
	Flags node for deletion. More...

static node_t *	insert (node_t *const pos, const value_type &d)
	Low-level insertion. More...

static node_t *	check_erase (node_t *const pos)
	Low-level erasure. More...

static void	link (node_t *const pos, node_t &begin_link, node_t &end_link)
	Assuming the nodes from begin_link to end_link are linked, they will be inserted into this before pos*. More...

static void	unlink (node_t &begin_unlink, node_t &end_unlink)
	Assuming begin_unlink and end_unlink are nodes from this, with end_unlink* a successor of begin_unlink, that chain of nodes will be removed from *this. More...

static void	splice (node_t *const pos, node_t &f, node_t &l)
	Low-level splice of the chain from b to e (including b and e) to the spot before pos. More...

Private Attributes
node_t	root_
	Root of the list. More...

Friends
template<class Value , bool Reversed>
class	iterator_base

Detailed Description

template<class Data>
class utils::smart_list< Data >

This is a variant on a list that never invalidates iterators (unless, of course, the list ceases to exist).

In particular, an erase() will only flag an element for removal from the list. Flagged elements are ignored by list functions, but they still exist from the perspective of iterators that had pointed (and still point) to the element.

Assignment is incompatible with the goal of preserving iterators, so it is not implemented (declared private though, to emphasize that this is intentional).

The insert() and erase() members are static, as they do not require a reference to the list.

Instead of being undefined, ++end() is equal to begin(), and –begin() is equal to end().

Definition at line 48 of file smart_list.hpp.

Member Typedef Documentation

template<class Data>

typedef const value_type& utils::smart_list< Data >::const_reference

Definition at line 185 of file smart_list.hpp.

template<class Data>

typedef value_type* utils::smart_list< Data >::pointer

Definition at line 183 of file smart_list.hpp.

template<class Data>

typedef value_type& utils::smart_list< Data >::reference

Definition at line 184 of file smart_list.hpp.

template<class Data>

typedef size_t utils::smart_list< Data >::size_type

Definition at line 186 of file smart_list.hpp.

template<class Data>

typedef Data utils::smart_list< Data >::value_type

Definition at line 182 of file smart_list.hpp.

Constructor & Destructor Documentation

template<class Data>

utils::smart_list< Data >::smart_list ( )

inline

Definition at line 236 of file smart_list.hpp.

template<class Data >

utils::smart_list< Data >::smart_list ( size_type n )

inline

Sized constructor.

Definition at line 330 of file smart_list.hpp.

References i, and utils::smart_list< Data >::push_back().

template<class Data >

utils::smart_list< Data >::smart_list	(	size_type	n,
		const value_type &	d
	)

inline

Sized constructor with a value.

Definition at line 337 of file smart_list.hpp.

References i, and utils::smart_list< Data >::push_back().

template<class Data >

utils::smart_list< Data >::smart_list ( const smart_list< Data > & that )

inline

Copy constructor.

Definition at line 344 of file smart_list.hpp.

References utils::smart_list< Data >::begin(), utils::smart_list< Data >::iterator_base< Value, Reversed >::derefable(), and utils::smart_list< Data >::push_back().

template<class Data >

template<class InputIterator >

utils::smart_list< Data >::smart_list	(	const InputIterator &	f,
		const InputIterator &	l
	)

inline

Constructor from a range.

Definition at line 352 of file smart_list.hpp.

References utils::smart_list< Data >::push_back().

template<class Data>

utils::smart_list< Data >::~smart_list ( )

inline

Definition at line 242 of file smart_list.hpp.

Member Function Documentation

template<class Data>

reference utils::smart_list< Data >::back ( )

inline

Definition at line 262 of file smart_list.hpp.

template<class Data>

const_reference utils::smart_list< Data >::back ( ) const

inline

Definition at line 263 of file smart_list.hpp.

template<class Data>

iterator utils::smart_list< Data >::begin ( )

inline

Definition at line 244 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::clear(), utils::smart_list< internal_ptr >::empty(), utils::smart_list< internal_ptr >::front(), utils::operator==(), utils::smart_list< internal_ptr >::pop_front(), and utils::smart_list< Data >::smart_list().

template<class Data>

const_iterator utils::smart_list< Data >::begin ( ) const

inline

Definition at line 246 of file smart_list.hpp.

template<class Data >

smart_list< Data >::node_t * utils::smart_list< Data >::check_erase ( node_t *const pos )

inlinestaticprivate

Low-level erasure.

The node will only be erased if its ref_count is 0. (So the caller must remove their reference before calling this.)

Returns: the next node in the list (could be a flagged node).

Definition at line 637 of file smart_list.hpp.

References utils::smart_list< Data >::node_t::next, pos, and utils::smart_list< Data >::node_t::ref_count.

Referenced by utils::smart_list< Data >::iterator_base< Value, Reversed >::unref().

template<class Data>

void utils::smart_list< Data >::clear ( )

inline

Definition at line 278 of file smart_list.hpp.

Referenced by game_events::handler_list::clear(), and utils::smart_list< internal_ptr >::~smart_list().

template<class Data>

bool utils::smart_list< Data >::empty ( ) const

inline

Note: if empty() returns true, the list might still contain nodes flagged for deletion.

Definition at line 257 of file smart_list.hpp.

template<class Data>

iterator utils::smart_list< Data >::end ( )

inline

Definition at line 245 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::clear(), utils::smart_list< internal_ptr >::empty(), utils::operator==(), and utils::smart_list< Data >::swap().

template<class Data>

const_iterator utils::smart_list< Data >::end ( ) const

inline

Definition at line 247 of file smart_list.hpp.

template<class Data >

smart_list< Data >::iterator utils::smart_list< Data >::erase ( const iterator & pos )

inlinestatic

Erase the node at pos.

Definition at line 411 of file smart_list.hpp.

References game_config::images::flag.

Referenced by utils::smart_list< internal_ptr >::clear(), utils::smart_list< internal_ptr >::pop_back(), and utils::smart_list< internal_ptr >::pop_front().

template<class Data >

smart_list< Data >::iterator utils::smart_list< Data >::erase	(	const iterator &	start,
		const iterator &	stop
	)

inlinestatic

Erase a range of nodes.

Definition at line 419 of file smart_list.hpp.

References game_config::images::flag.

template<class Data>

static void utils::smart_list< Data >::flag ( const node_t & node )

inlinestaticprivate

Flags node for deletion.

Definition at line 310 of file smart_list.hpp.

template<class Data>

static bool utils::smart_list< Data >::flagged ( const node_t & node )

inlinestaticprivate

Returns true if node has been flagged for deletion.

Definition at line 308 of file smart_list.hpp.

template<class Data>

reference utils::smart_list< Data >::front ( )

inline

Definition at line 260 of file smart_list.hpp.

template<class Data>

const_reference utils::smart_list< Data >::front ( ) const

inline

Definition at line 261 of file smart_list.hpp.

template<class Data >

smart_list< Data >::iterator utils::smart_list< Data >::insert	(	const iterator &	pos,
		const value_type &	d
	)

inlinestatic

Insert a node before pos.

Definition at line 386 of file smart_list.hpp.

References utf8::insert().

Referenced by utils::smart_list< internal_ptr >::push_back(), and utils::smart_list< internal_ptr >::push_front().

template<class Data >

template<class InputIterator >

void utils::smart_list< Data >::insert	(	const iterator &	pos,
		const InputIterator &	f,
		const InputIterator &	l
	)

inlinestatic

Insert a range before pos.

Definition at line 393 of file smart_list.hpp.

References utf8::insert().

template<class Data >

void utils::smart_list< Data >::insert	(	const iterator &	pos,
		size_type	n,
		const value_type &	d
	)

inlinestatic

Insert n copies of d at pos.

Definition at line 401 of file smart_list.hpp.

References i, and utf8::insert().

template<class Data >

smart_list< Data >::node_t * utils::smart_list< Data >::insert	(	node_t *const	pos,
		const value_type &	d
	)

inlinestaticprivate

Low-level insertion.

The insertion will occur before pos. Pass &root_ to append to the list.

Definition at line 621 of file smart_list.hpp.

template<class Data >

void utils::smart_list< Data >::link	(	node_t *const	pos,
		node_t &	begin_link,
		node_t &	end_link
	)

inlinestaticprivate

Assuming the nodes from begin_link to end_link are linked, they will be inserted into *this before pos.

(Pass &root_ to append to the list.) Note that *end_link is included in the insert; this is not exactly analogous to a range of iterators. This is a constant-time operation; reference counts are not updated.

Definition at line 665 of file smart_list.hpp.

References utils::smart_list< Data >::node_t::next, pos, and utils::smart_list< Data >::node_t::prev.

template<class Data>

size_type utils::smart_list< Data >::max_size ( ) const

inline

Definition at line 254 of file smart_list.hpp.

template<class Data>

void utils::smart_list< Data >::merge ( smart_list< Data > & L )

inline

Definition at line 295 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::merge().

template<class Data >

template<class BinaryPredicate >

void utils::smart_list< Data >::merge	(	smart_list< Data > &	L,
		const BinaryPredicate &	p
	)

inline

Merge L into *this, using p to determine order.

If both lists are sorted under p, then so is the merged list. This is stable; equivalent nodes retain their order, with nodes of *this considered to come before elements of L.

Definition at line 544 of file smart_list.hpp.

References utils::smart_list< Data >::node_t::dat_ptr, utils::smart_list< Data >::node_t::next, utils::smart_list< Data >::node_t::prev, and utils::smart_list< Data >::root_.

template<class Data>

smart_list& utils::smart_list< Data >::operator= ( const smart_list< Data > & )

private

No implementation of operator=() since that would not preserve iterators.

template<class Data>

void utils::smart_list< Data >::pop_back ( )

inline

Definition at line 267 of file smart_list.hpp.

template<class Data>

void utils::smart_list< Data >::pop_front ( )

inline

Definition at line 266 of file smart_list.hpp.

template<class Data>

void utils::smart_list< Data >::push_back ( const value_type & d )

inline

Definition at line 265 of file smart_list.hpp.

Referenced by game_events::handler_list::push_back(), and utils::smart_list< Data >::smart_list().

template<class Data>

void utils::smart_list< Data >::push_front ( const value_type & d )

inline

Definition at line 264 of file smart_list.hpp.

Referenced by game_events::handler_list::push_front().

template<class Data>

reverse_iterator utils::smart_list< Data >::rbegin ( )

inline

Definition at line 248 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::back(), and utils::smart_list< internal_ptr >::pop_back().

template<class Data>

const_reverse_iterator utils::smart_list< Data >::rbegin ( ) const

inline

Definition at line 250 of file smart_list.hpp.

template<class Data >

void utils::smart_list< Data >::remove ( const value_type & value )

inline

Remove all nodes whose data equals value.

Definition at line 489 of file smart_list.hpp.

References preferences::erase().

template<class Data >

template<class Predicate >

void utils::smart_list< Data >::remove_if ( const Predicate & p )

inline

Remove all nodes whose data satisfies p.

Definition at line 502 of file smart_list.hpp.

References preferences::erase().

template<class Data>

reverse_iterator utils::smart_list< Data >::rend ( )

inline

Definition at line 249 of file smart_list.hpp.

template<class Data>

const_reverse_iterator utils::smart_list< Data >::rend ( ) const

inline

Definition at line 251 of file smart_list.hpp.

template<class Data>

void utils::smart_list< Data >::resize ( size_type n )

inline

Definition at line 280 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::resize().

template<class Data >

void utils::smart_list< Data >::resize	(	size_type	n,
		const value_type &	d
	)

inline

Resize the list.

This does not count flagged nodes.

Definition at line 438 of file smart_list.hpp.

References preferences::erase(), and utf8::insert().

template<class Data >

smart_list< Data >::size_type utils::smart_list< Data >::size ( ) const

inline

The size of the list, not counting flagged nodes.

Definition at line 362 of file smart_list.hpp.

template<class Data>

void utils::smart_list< Data >::sort ( )

inline

Definition at line 299 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::sort().

template<class Data >

template<class BinaryPredicate >

void utils::smart_list< Data >::sort ( const BinaryPredicate & p )

inline

Sort *this, using the order given by p.

This is stable; equivalent nodes retain their order. This is an efficient sort, O(n lg n).

Definition at line 584 of file smart_list.hpp.

References i, utils::smart_list< Data >::node_t::next, and swap().

template<class Data >

void utils::smart_list< Data >::splice	(	const iterator &	pos,
		smart_list< Data > &	L
	)

inline

Splice all of L into *this before pos.

Definition at line 461 of file smart_list.hpp.

References utils::smart_list< Data >::node_t::next, utils::smart_list< Data >::node_t::prev, and utils::smart_list< Data >::root_.

Referenced by utils::smart_list< Data >::swap().

template<class Data >

void utils::smart_list< Data >::splice	(	const iterator &	pos,
		smart_list< Data > &	L,
		const iterator &	i
	)

inline

Splice the node i points to (assumed from L) into *this before pos.

Definition at line 468 of file smart_list.hpp.

References utils::smart_list< Data >::iterator_base< Value, Reversed >::derefable().

template<class Data >

void utils::smart_list< Data >::splice	(	const iterator &	pos,
		smart_list< Data > &	L,
		const iterator &	f,
		const iterator &	l
	)

inline

Splice a range (assumed from L) into *this before pos.

Definition at line 476 of file smart_list.hpp.

References utils::smart_list< Data >::iterator_base< Value, Reversed >::derefable().

template<class Data >

void utils::smart_list< Data >::splice	(	node_t *const	pos,
		node_t &	f,
		node_t &	l
	)

inlinestaticprivate

Low-level splice of the chain from b to e (including b and e) to the spot before pos.

Definition at line 700 of file smart_list.hpp.

template<class Data >

void utils::smart_list< Data >::swap ( smart_list< Data > & that )

inline

Swaps two lists.

Done in constant time, with no iterator invalidation.

Definition at line 373 of file smart_list.hpp.

References utils::smart_list< Data >::end(), and utils::smart_list< Data >::splice().

template<class Data>

void utils::smart_list< Data >::unique ( )

inline

Definition at line 291 of file smart_list.hpp.

Referenced by utils::smart_list< internal_ptr >::unique().

template<class Data >

template<class BinaryPredicate >

void utils::smart_list< Data >::unique ( const BinaryPredicate p )

inline

Remove nodes equal (under p) to their immediate predecessor.

Definition at line 516 of file smart_list.hpp.

References preferences::erase(), and prev.

template<class Data >

void utils::smart_list< Data >::unlink	(	node_t &	begin_unlink,
		node_t &	end_unlink
	)

inlinestaticprivate

Assuming begin_unlink and end_unlink are nodes from *this, with end_unlink a successor of begin_unlink, that chain of nodes will be removed from *this.

Ownership of the removed chain is transferred to the caller, who becomes repsonsible for not leaving the nodes in limbo. This is a constant-time operation; reference counts are not updated.

Definition at line 684 of file smart_list.hpp.

References utils::smart_list< Data >::node_t::next, and utils::smart_list< Data >::node_t::prev.