Doubly linked lists (maintaining the length of the list). More...

#include <ogdf/basic/List.h>

Inheritance diagram for ogdf::List< E >:

Public Member Functions
	List ()
	Constructs an empty doubly linked list. More...

	List (const List< E > &L)
	Constructs a doubly linked list that is a copy of `L`. More...

	List (List< E > &&L) noexcept
	Constructs a doubly linked list containing the elements of `L` (move semantics). More...

	List (std::initializer_list< E > init)
	Constructs a doubly linked list containing the elements in `init`. More...

Access methods
These methods provide simple access without changing the list.
int	size () const
	Returns the number of elements in the list. More...

const ListPure< E > &	getListPure () const
	Conversion to const ListPure. More...

Operators
The following operators are provided by lists.
List< E > &	operator= (const List< E > &L)
	Assignment operator. More...

List< E > &	operator= (List< E > &&L)
	Assignment operator (move semantics). More...

bool	operator== (const List< E > &L) const
	Equality operator. More...

bool	operator!= (const List< E > &L) const
	Inequality operator. More...

Adding elements
These method add elements to the list.
iterator	pushFront (const E &x)
	Adds element `x` at the beginning of the list. More...

template<class... Args>
iterator	emplaceFront (Args &&... args)
	Adds a new element at the beginning of the list. More...

iterator	pushBack (const E &x)
	Adds element `x` at the end of the list. More...

template<class... Args>
iterator	emplaceBack (Args &&... args)
	Adds a new element at the end of the list. More...

iterator	insert (const E &x, iterator it, Direction dir=Direction::after)
	Inserts element `x` before or after `it`. More...

iterator	insertBefore (const E &x, iterator it)
	Inserts element `x` before `it`. More...

iterator	insertAfter (const E &x, iterator it)
	Inserts element `x` after `it`. More...

Removing elements
These method remove elements from the list.
void	popFront ()
	Removes the first element from the list. More...

E	popFrontRet ()
	Removes the first element from the list and returns it. More...

void	popBack ()
	Removes the last element from the list. More...

E	popBackRet ()
	Removes the last element from the list and returns it. More...

void	del (iterator it)
	Removes `it` from the list. More...

bool	removeFirst (const E &x)
	Removes the first occurrence of `x` (if any) from the list. More...

void	clear ()
	Removes all elements from the list. More...

Moving elements
The method allow to change the order of elements within the list, or to move elements to another list.
void	moveToFront (iterator it, List< E > &L2)
	Moves `it` to the begin of the list. More...

void	moveToBack (iterator it, List< E > &L2)
	Moves `it` to the end of the list. More...

void	moveToSucc (iterator it, List< E > &L2, iterator itBefore)
	Moves `it` after `itBefore`. More...

void	moveToPrec (iterator it, List< E > &L2, iterator itAfter)
	Moves `it` before `itAfter`. More...

void	conc (List< E > &L2)
	Appends `L2` to this list and makes `L2` empty. More...

void	concFront (List< E > &L2)
	Prepends `L2` to this list and makes `L2` empty. More...

void	swap (List< E > &other)
	Exchanges the contents of this list and `other` in constant time. More...

void	split (iterator it, List< E > &L1, List< E > &L2, Direction dir=Direction::before)
	Splits the list at element `it` into lists `L1` and `L2`. More...

Private Attributes
int	m_count
	The length of the list. More...

Detailed Description

template<class E>
class ogdf::List< E >

Doubly linked lists (maintaining the length of the list).

Use ogdf::ListConstIterator or ogdf::ListIterator in order to iterate over the list.

In contrast to ogdf::ListPure, instances of ogdf::List store the length of the list.

Template Parameters

E	is the data type stored in list elements.

Definition at line 42 of file List.h.

Constructor & Destructor Documentation

◆ List() [1/4]

template<class E >

ogdf::List< E >::List ( )

inline

Constructs an empty doubly linked list.

Definition at line 1454 of file List.h.

◆ List() [2/4]

template<class E >

ogdf::List< E >::List ( std::initializer_list< E > init )

inline

Constructs a doubly linked list containing the elements in init.

Definition at line 1457 of file List.h.

◆ List() [3/4]

template<class E >

ogdf::List< E >::List ( const List< E > & L )

inline

Constructs a doubly linked list that is a copy of L.

Definition at line 1460 of file List.h.

◆ List() [4/4]

template<class E >

ogdf::List< E >::List ( List< E > && L )

inlinenoexcept

Constructs a doubly linked list containing the elements of L (move semantics).

The list L is empty afterwards.

Definition at line 1466 of file List.h.

Member Function Documentation

◆ clear()

template<class E >

void ogdf::List< E >::clear ( )

inline

Removes all elements from the list.

Definition at line 1616 of file List.h.

◆ conc()

template<class E >

void ogdf::List< E >::conc ( List< E > & L2 )

inline

Appends L2 to this list and makes L2 empty.

Definition at line 1657 of file List.h.

◆ concFront()

template<class E >

void ogdf::List< E >::concFront ( List< E > & L2 )

inline

Prepends L2 to this list and makes L2 empty.

Definition at line 1664 of file List.h.

◆ del()

template<class E >

void ogdf::List< E >::del ( iterator it )

inline

Removes it from the list.

Precondition: it points to an element in this list.

Definition at line 1601 of file List.h.

◆ emplaceBack()

template<class E >

template<class... Args>

iterator ogdf::List< E >::emplaceBack ( Args &&... args )

inline

Adds a new element at the end of the list.

The element is constructed in-place with exactly the same arguments args as supplied to the function.

Definition at line 1544 of file List.h.

◆ emplaceFront()

template<class E >

template<class... Args>

iterator ogdf::List< E >::emplaceFront ( Args &&... args )

inline

Adds a new element at the beginning of the list.

The element is constructed in-place with exactly the same arguments args as supplied to the function.

Definition at line 1531 of file List.h.

◆ getListPure()

template<class E >

const ListPure<E>& ogdf::List< E >::getListPure ( ) const

inline

Conversion to const ListPure.

Definition at line 1481 of file List.h.

◆ insert()

template<class E >

iterator ogdf::List< E >::insert	(	const E &	x,
		iterator	it,
		Direction	dir = `Direction::after`
	)

inline

Inserts element x before or after it.

Parameters

x	is the element to be inserted.
it	is a list iterator in this list.
dir	determines if `x` is inserted before or after `it`. Possible values are ogdf::before and ogdf::after.

Precondition: it points to an element in this list.

Definition at line 1550 of file List.h.

◆ insertAfter()

template<class E >

iterator ogdf::List< E >::insertAfter	(	const E &	x,
		iterator	it
	)

inline

Inserts element x after it.

Precondition: it points to an element in this list.

Definition at line 1562 of file List.h.

◆ insertBefore()

template<class E >

iterator ogdf::List< E >::insertBefore	(	const E &	x,
		iterator	it
	)

inline

Inserts element x before it.

Precondition: it points to an element in this list.

Definition at line 1556 of file List.h.

◆ moveToBack()

template<class E >

void ogdf::List< E >::moveToBack	(	iterator	it,
		List< E > &	L2
	)

inline

Moves it to the end of the list.

Precondition: it points to an element in this list.

Definition at line 1636 of file List.h.

◆ moveToFront()

template<class E >

void ogdf::List< E >::moveToFront	(	iterator	it,
		List< E > &	L2
	)

inline

Moves it to the begin of the list.

Precondition: it points to an element in this list.

Definition at line 1629 of file List.h.

◆ moveToPrec()

template<class E >

void ogdf::List< E >::moveToPrec	(	iterator	it,
		List< E > &	L2,
		iterator	itAfter
	)

inline

Moves it before itAfter.

Precondition: it and itAfter point to elements in this list.

Definition at line 1650 of file List.h.

◆ moveToSucc()

template<class E >

void ogdf::List< E >::moveToSucc	(	iterator	it,
		List< E > &	L2,
		iterator	itBefore
	)

inline

Moves it after itBefore.

Precondition: it and itBefore point to elements in this list.

Definition at line 1643 of file List.h.

◆ operator!=()

template<class E >

bool ogdf::List< E >::operator!= ( const List< E > & L ) const

inline

Inequality operator.

Definition at line 1514 of file List.h.

◆ operator=() [1/2]

template<class E >

List<E>& ogdf::List< E >::operator= ( const List< E > & L )

inline

Assignment operator.

Definition at line 1491 of file List.h.

◆ operator=() [2/2]

template<class E >

List<E>& ogdf::List< E >::operator= ( List< E > && L )

inline

Assignment operator (move semantics).

The list L is empty afterwards.

Definition at line 1501 of file List.h.

◆ operator==()

template<class E >

bool ogdf::List< E >::operator== ( const List< E > & L ) const

inline

Equality operator.

Definition at line 1509 of file List.h.

◆ popBack()

template<class E >

void ogdf::List< E >::popBack ( )

inline

Removes the last element from the list.

Precondition: The list is not empty!

Definition at line 1588 of file List.h.

◆ popBackRet()

template<class E >

E ogdf::List< E >::popBackRet ( )

inline

Removes the last element from the list and returns it.

Precondition: The list is not empty!

Definition at line 1594 of file List.h.

◆ popFront()

template<class E >

void ogdf::List< E >::popFront ( )

inline

Removes the first element from the list.

Precondition: The list is not empty!

Definition at line 1575 of file List.h.

◆ popFrontRet()

template<class E >

E ogdf::List< E >::popFrontRet ( )

inline

Removes the first element from the list and returns it.

Precondition: The list is not empty!

Definition at line 1581 of file List.h.

◆ pushBack()

template<class E >

iterator ogdf::List< E >::pushBack ( const E & x )

inline

Adds element x at the end of the list.

Definition at line 1537 of file List.h.

◆ pushFront()

template<class E >

iterator ogdf::List< E >::pushFront ( const E & x )

inline

Adds element x at the beginning of the list.

Definition at line 1524 of file List.h.

◆ removeFirst()

template<class E >

bool ogdf::List< E >::removeFirst ( const E & x )

inline

Removes the first occurrence of x (if any) from the list.

If the list contains x several times, only the first element containing x is removed.

Returns: true if one element has been removed, false otherwise.

Definition at line 1607 of file List.h.

◆ size()

template<class E >

int ogdf::List< E >::size ( ) const

inline

Returns the number of elements in the list.

This method has constant runtime (in contrast to ListPure::size()), since the list maintains the current size.

Definition at line 1478 of file List.h.

◆ split()

template<class E >

void ogdf::List< E >::split	(	iterator	it,
		List< E > &	L1,
		List< E > &	L2,
		Direction	dir = `Direction::before`
	)

inline

Splits the list at element it into lists L1 and L2.

If it is not a null pointer and L = x1,...,x{k-1}, it,x_{k+1},xn, then L1 = x1,...,x{k-1} and L2 = it,x{k+1},...,xn if dir = Direction::before. If it is a null pointer, then L1 is made empty and L2 = L. Finally L is made empty if it is not identical to L1 or L2.

Precondition: it points to an element in this list.

Definition at line 1677 of file List.h.

◆ swap()

template<class E >

void ogdf::List< E >::swap ( List< E > & other )

inline

Exchanges the contents of this list and other in constant time.

Definition at line 1671 of file List.h.

Member Data Documentation

◆ m_count

template<class E >

int ogdf::List< E >::m_count

private

The length of the list.

Definition at line 1442 of file List.h.

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

include/ogdf/basic/List.h

OpenGraph DrawingFramework

Public Member Functions

Private Attributes

Detailed Description

template<class E> class ogdf::List< E >

Constructor & Destructor Documentation

◆ List() [1/4]

◆ List() [2/4]

◆ List() [3/4]

◆ List() [4/4]

Member Function Documentation

◆ clear()

◆ conc()

◆ concFront()

◆ del()

◆ emplaceBack()

◆ emplaceFront()

◆ getListPure()

◆ insert()

◆ insertAfter()

◆ insertBefore()

◆ moveToBack()

◆ moveToFront()

◆ moveToPrec()

◆ moveToSucc()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ popBack()

◆ popBackRet()

◆ popFront()

◆ popFrontRet()

◆ pushBack()

◆ pushFront()

◆ removeFirst()

◆ size()

◆ split()

◆ swap()

Member Data Documentation

◆ m_count

Open
Graph Drawing
Framework

template<class E>
class ogdf::List< E >