List< T, member > Class Template Reference

Doubly-linked list template. More...

#include <list.hh>

Classes
class	const_iterator
	Const iterator type for List. More...
class	iterator
	Iterator type for List. More...

Public Types
typedef T *	pointer
typedef const T *	const_pointer
typedef size_t	size_type

Public Member Functions
	List ()
	Construct an empty list.
iterator	begin ()
	Return an iterator for the first element in the list.
const_iterator	begin () const
iterator	end ()
	Return an iterator for the end of the list.
const_iterator	end () const
bool	empty () const
	Return true iff size() == 0.
size_type	size () const
	Return the number of elements in the list.
pointer	front ()
	Return the first element in the list.
const_pointer	front () const
pointer	back ()
	Return the last element in the list.
const_pointer	back () const
void	push_front (pointer x)
	Insert a new element at the beginning of the list.
void	push_back (pointer x)
	Insert a new element at the end of the list.
void	pop_front ()
	Remove the element at the beginning of the list.
void	pop_back ()
	Remove the element at the end of the list.
void	insert (pointer pos, pointer x)
	Insert an element before pos.
iterator	insert (iterator it, pointer x)
	Insert an element before it.
template<typename InputIterator >
void	insert (iterator it, InputIterator first, InputIterator last)
	Insert the elements in [first, last) before it.
void	erase (pointer x)
	Remove x from the list.
iterator	erase (iterator it)
	Remove the element pointed to by it from the list.
iterator	erase (iterator first, iterator last)
	Remove the elements in [first, last) from the list.
void	clear ()
	Remove all elements from the list.
void	__clear ()
	Remove all elements from the list.
void	swap (List< T, member > &x)
	Exchange list contents with list x.
bool	isolated (const_pointer x)
	Check if x is isolated.
bool	contains (const_pointer x) const
	Check if x is a member of this list.

Detailed Description

template<typename T, List_member< T > T::* member>
class List< T, member >

Doubly-linked list template.

The List template, and its helper template List_member, implement a generic doubly-linked list. The list is intrusive in that the container does not manage space for its contents. The user provides space for contained elements, and must delete elements when they are no longer needed. (This is unlike Vector or HashTable, which manage space for their contents.) The main advantage of intrusive containers is that a single element can be on multiple lists.

Here's an example linked list of integers built using List and List_member.

#include <click/list.hh>
 
struct intlist_node {
    int value;
    List_member<intlist_node> link;
    intlist_node(int v)
        : value(v) {
    }
};
 
typedef List<intlist_node, &intlist_node::link> intlist;
 
void make_intlist(intlist &l, int begin, int end, int step) {
    for (int i = begin; i < end; i += step)
        l.push_back(new intlist_node(i));
    // Note that l does not manage its contents' memory!
    // Whoever destroys l should first delete its contents,
    // for example by calling trash_intlist(l).
}
 
void print_intlist(const intlist &l) {
    size_t n = 0;
    for (intlist::const_iterator it = l.begin(); it != l.end(); ++it, ++n)
        click_chatter("#%ld: %d\n", (long) n, it->value);
}
 
void trash_intlist(intlist &l) {
    while (!l.empty()) {
        intlist_node *n = l.front();
        l.pop_front();
        delete n;
    }
}
 
template <typename T>
void remove_every_other(T &list) {
    typename T::iterator it = list.begin();
    while (it != l.end()) {
        ++it;
        if (it != l.end())
            it = list.erase(it);
    }
}

Constructor & Destructor Documentation

List()

template<typename T , List_member< T > T::* member>

List< T, member >::List ( )

inline

Construct an empty list.

Member Function Documentation

begin() [1/2]

template<typename T , List_member< T > T::* member>

iterator List< T, member >::begin ( )

inline

Return an iterator for the first element in the list.

begin() [2/2]

template<typename T , List_member< T > T::* member>

const_iterator List< T, member >::begin ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

end() [1/2]

template<typename T , List_member< T > T::* member>

iterator List< T, member >::end ( )

inline

Return an iterator for the end of the list.

Invariant

end().live() == false

end() [2/2]

template<typename T , List_member< T > T::* member>

const_iterator List< T, member >::end ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

empty()

template<typename T , List_member< T > T::* member>

bool List< T, member >::empty ( ) const

inline

Return true iff size() == 0.

Note

Always O(1) time, whereas size() takes O(N) time.

size()

template<typename T , List_member< T > T::* member>

size_type List< T, member >::size ( ) const

inline

Return the number of elements in the list.

Note

Takes O(N) time, where N is the number of elements.

front() [1/2]

template<typename T , List_member< T > T::* member>

pointer List< T, member >::front ( )

inline

Return the first element in the list.

Returns a null pointer if the list is empty.

front() [2/2]

template<typename T , List_member< T > T::* member>

const_pointer List< T, member >::front ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

back() [1/2]

template<typename T , List_member< T > T::* member>

pointer List< T, member >::back ( )

inline

Return the last element in the list.

Returns a null pointer if the list is empty.

back() [2/2]

template<typename T , List_member< T > T::* member>

const_pointer List< T, member >::back ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

push_front()

template<typename T , List_member< T > T::* member>

void List< T, member >::push_front ( pointer  x )

inline

Insert a new element at the beginning of the list.

Parameters

x	new element

Precondition

isolated(x)

push_back()

template<typename T , List_member< T > T::* member>

void List< T, member >::push_back ( pointer  x )

inline

Insert a new element at the end of the list.

Parameters

x	new element

Precondition

isolated(x)

pop_front()

template<typename T , List_member< T > T::* member>

void List< T, member >::pop_front ( )

inline

Remove the element at the beginning of the list.

Precondition

!empty()

pop_back()

template<typename T , List_member< T > T::* member>

void List< T, member >::pop_back ( )

inline

Remove the element at the end of the list.

Precondition

!empty()

insert() [1/3]

template<typename T , List_member< T > T::* member>

void List< T, member >::insert ( pointer  pos, pointer  x  )

inline

Insert an element before pos.

Parameters

pos	position to insert (if null, insert at end of list)
x	new element

Precondition

(!pos || contains(pos)) && isolated(x)

insert() [2/3]

template<typename T , List_member< T > T::* member>

iterator List< T, member >::insert ( iterator  it, pointer  x  )

inline

Insert an element before it.

Parameters

it	position to insert
x	new element

Returns

an iterator pointing to x

Precondition

isolated(x)

insert() [3/3]

template<typename T , List_member< T > T::* member>

template<typename InputIterator >

void List< T, member >::insert ( iterator  it, InputIterator  first, InputIterator  last  )

inline

Insert the elements in [first, last) before it.

Parameters

it	position to insert
first	iterator to beginning of insertion sequence
last	iterator to end of insertion sequence

Precondition

isolated(x) for each x in [first, last)

erase() [1/3]

template<typename T , List_member< T > T::* member>

void List< T, member >::erase ( pointer  x )

inline

Remove x from the list.

Parameters

x	element to remove

Precondition

contains(x)

erase() [2/3]

template<typename T , List_member< T > T::* member>

iterator List< T, member >::erase ( iterator  it )

inline

Remove the element pointed to by it from the list.

Parameters

it	element to remove

Returns

iterator pointing to the element after the removed element

Precondition

it.live()

erase() [3/3]

template<typename T , List_member< T > T::* member>

iterator List< T, member >::erase ( iterator  first, iterator  last  )

inline

Remove the elements in [first, last) from the list.

Parameters

first	iterator to beginning of removal subsequence
last	iterator to end of removal subsequence

Returns

iterator pointing to the element after the removed subsequence

clear()

template<typename T , List_member< T > T::* member>

void List< T, member >::clear ( )

inline

Remove all elements from the list.

Note

Equivalent to erase(begin(), end()).

__clear()

template<typename T , List_member< T > T::* member>

void List< T, member >::__clear ( )

inline

Remove all elements from the list.

Unlike clear(), this function does not erase() any of the elements of this list: those elements' next() and prev() members remain unchanged.

swap()

template<typename T , List_member< T > T::* member>

void List< T, member >::swap ( List< T, member > &  x )

inline

Exchange list contents with list x.

isolated()

template<typename T , List_member< T > T::* member>

bool List< T, member >::isolated ( const_pointer  x )

inline

Check if x is isolated.

An isolated element is not a member of any list.

contains()

template<typename T , List_member< T > T::* member>

bool List< T, member >::contains ( const_pointer  x ) const

inline

Check if x is a member of this list.

---

The documentation for this class was generated from the following file:

• include/click/list.hh