Friedrich-Alexander-Universität Erlangen-Nürnberg  /   Technische Fakultät  /   Department Informatik
Queue< T, next_field > Template-Klassenreferenz

Die Klasse Queue realisiert eine einfach verkettete Liste von Objekten mit next Zeiger. Mehr ...

#include <queue.h>

Klassen

class  Iterator
 Ein Queue Iterator. Mehr ...
 

Öffentliche Methoden

 Queue ()
 Der Konstruktor initialisiert die Liste als leere Liste.
 
void enqueue (T *item)
 Das Listenelement item wird an das Ende der Liste angefügt. Mehr ...
 
T * dequeue ()
 Liefert das erste Element der Liste und entfernt es gleichzeitig aus dieser. Mehr ...
 
Iterator begin ()
 
Iterator end ()
 
T * remove (T *item, bool(*cmp)(T *, T *)=[](T *a, T *b) {return a==b;})
 Mit dieser Methode kann das angegebene Element item aus der Liste entfernt werden, unabhängig von seiner Position dort. Verglichen werden die Pointer-Adressen, optional kann eine Vergleichsfunktion angegeben werden. Die Standardvergleichsfunktion ist ein C++11 Lambda Ausdruck, der auf Pointer-Gleichheit prüft. Mehr ...
 
void insert_first (T *item)
 Fügt das item am Anfang der Liste ein. Mehr ...
 
void insert_after (T *old_item, T *new_item)
 Fügt das Element new_item hinter dem Element old_item in die Liste ein. Mehr ...
 
T * first ()
 Liefert das erste Element der Liste, ohne es zu entfernen. Mehr ...
 
T * next (T *o)
 Liefert das nächste Element der Liste für ein gegebenes Element.
 

Öffentliche, statische Methoden

static QueueLink< T > * get_node (T *o)
 Gibt einen Zeiger auf das QueueLink-Element innerhalb des Argument-Objektes zurück. Mehr ...
 

Ausführliche Beschreibung

template<typename T, QueueLink< T > T::* next_field = nullptr>
class Queue< T, next_field >

Die Klasse Queue realisiert eine einfach verkettete Liste von Objekten mit next Zeiger.

Objekte, die verkettet werden sollen, enthalten ein QueueLink<T>-Member, welches diese Liste identifiziert. Beispiel:

class Foo {
   QueueLink<Foo> next_foo;
}

Das next_foo Feld enthaelt dabei den Verkettungszeiger. Es lassen sich nun Listen mit dem next_foo Verkettungszeiger generieren und verwenden. Insbesondere können diese Queues in C++11 Range Ausdrücken verwendet werden.

Queue<Foo, &Foo::next_foo> list;
Foo a, b, c;

list.enqueue(&a);
list.enqueue(&b);
list.enqueue(&c);

for(Foo * elem : list) {
  // use elem
}

Wird eine Queue ohne Angabe eines expliziten Verkettungszeigers instanziiert, so muss die zu verkettende Klasse ein QueueLink<T>-Member mit dem Namen "queue_link" enthalten:

class Bar {
   QueueLink<Bar> queue_link;
}
Queue<Bar> list;

Zur Implementierung: tail verweist nicht, wie oft üblich, auf das letzte Element der Liste, sondern auf den next Zeiger des letzten Elements, bzw., solange die Liste noch leer ist, auf den head Zeiger der Liste. Dadurch muss beim Einfügen eines Elements an die Liste nicht überprüft werden, ob bereits Elemente in ihr enthalten sind. Beim Entfernen von Elementen kann auf die Fallunterscheidung allerdings nicht verzichtet werden.

Dokumentation der Elementfunktionen

◆ begin()

template<typename T, QueueLink< T > T::* next_field = nullptr>
Iterator Queue< T, next_field >::begin ( )
inline

Liefert einen Iterator auf den Beginn der Queue

◆ dequeue()

template<typename T, QueueLink< T > T::* next_field = nullptr>
T* Queue< T, next_field >::dequeue ( )
inline

Liefert das erste Element der Liste und entfernt es gleichzeitig aus dieser.

Rückgabe
entferntes Kopfelement oder 0 wenn die Liste leer ist.

◆ end()

template<typename T, QueueLink< T > T::* next_field = nullptr>
Iterator Queue< T, next_field >::end ( )
inline

Liefert einen End Iterator

◆ enqueue()

template<typename T, QueueLink< T > T::* next_field = nullptr>
void Queue< T, next_field >::enqueue ( T *  item)
inline

Das Listenelement item wird an das Ende der Liste angefügt.

Parameter
itemListenelement, welches angefügt werden soll.

◆ first()

template<typename T, QueueLink< T > T::* next_field = nullptr>
T* Queue< T, next_field >::first ( )
inline

Liefert das erste Element der Liste, ohne es zu entfernen.

Rückgabe
Erstes Element der Liste.

◆ get_node()

template<typename T, QueueLink< T > T::* next_field = nullptr>
static QueueLink<T>* Queue< T, next_field >::get_node ( T *  o)
inlinestatic

Gibt einen Zeiger auf das QueueLink-Element innerhalb des Argument-Objektes zurück.

Wir verwenden hier die "ungewöhnliche" Pointer-to-Member Funktionalität von C++. Ein PtM kann mit dem "->*" Operator auf ein Objekt der passenden Klasse angewendet werden, um Zugriff auf ein bestimmtes Feld zu bekommen.

◆ insert_after()

template<typename T, QueueLink< T > T::* next_field = nullptr>
void Queue< T, next_field >::insert_after ( T *  old_item,
T *  new_item 
)
inline

Fügt das Element new_item hinter dem Element old_item in die Liste ein.

Parameter
old_itemElement, nach dem eingefügt werden soll.
new_itemEinzufügendes Element.

◆ insert_first()

template<typename T, QueueLink< T > T::* next_field = nullptr>
void Queue< T, next_field >::insert_first ( T *  item)
inline

Fügt das item am Anfang der Liste ein.

Parameter
itemEinzufügendes Element.

◆ remove()

template<typename T, QueueLink< T > T::* next_field = nullptr>
T* Queue< T, next_field >::remove ( T *  item,
bool(*)(T *, T *)  cmp = [] (T* a, T* b) {return a == b;} 
)
inline

Mit dieser Methode kann das angegebene Element item aus der Liste entfernt werden, unabhängig von seiner Position dort. Verglichen werden die Pointer-Adressen, optional kann eine Vergleichsfunktion angegeben werden. Die Standardvergleichsfunktion ist ein C++11 Lambda Ausdruck, der auf Pointer-Gleichheit prüft.

Parameter
itemElement, welches entfernt werden soll.
cmpVergleichsfunktion.
Rückgabe
Gibt das entfernte Element zurück, 0 wenn keins entfernt wurde.

Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Datei: