symlist Class Reference

[Index] [Hierarchy] [Headers]


list which can be reversed in O(1). More...

#include <GTL/symlist.h>

Template Form: template <class T> symlist

Public Members


Detailed Description

The problem with the STL class list - as with most doubly linked lists -- is that isn't possible to turn it in constant time, because each entry in the list contains next and prev pointer and turning the list means to switch these two in each element in the list. Another point is the splice operation in STL lists, which is constant time, but for the same reason as mentioned above it is not possible to splice a list in reverse order into another in constant time.

The problems arise from the fact that each element "knows" what its next and previous elements are. An element in a symlist only knows what its neighbors are, what is next and what previous depends on the direction of iteration. This of course imposes some overhead in iteration (one if-statement) but allows reversion and a splice in reversed order in constant time.


symlist() [public]

Creates empty symlist.

symlist(const symlist<T>& li) [public]

Makes the created list a copy of li.

Parameters:
li symlist.

symlist<T>& operator=(const symlist<T>& li) [public]

Assignes li to this list. Note: all elements in this list will be deleted.

Parameters:
li
Returns:
this list

~symlist() [public]

Destructor

bool empty() const [public]

Checks whether list is empty. Takes constant time.

Returns:
true iff list is empty

T& front() [public]

First element in list. Assumes that list ins't empty.

Returns:
first element.

T& back() [public]

Last element in list. Assumes that list ins't empty.

Returns:
last element.

iterator begin() [public]

Start iteration through elements of list

Returns:
start iterator

iterator end() [public]

End of iteration through elements of list

Returns:
end iterator

const_iterator begin() const [public]

Start iteration through elements of list

Returns:
start iterator

const_iterator end() const [public]

End of iteration through elements of list

Returns:
end iterator

iterator rbegin() [public]

Start iteration through element of list in reverse order

Returns:
start iterator

iterator rend() [public]

End of iteration through elements of list in reverse order

Returns:
end iterator

const_iterator rbegin() const [public]

Start iteration through element of list in reverse order

Returns:
start iterator

const_iterator rend() const [public]

End of iteration through elements of list in reverse order

Returns:
end iterator

iterator insert(iterator pos, const T& data) [public]

Inserts data before pos in list.

Parameters:
data element to be inserted
pos position
Returns:
position of insertion

void splice(iterator pos, iterator it) [public]

Inserts the element it points to before pos into this list. It is assumed that the element it refers lies in a different list. All iterators to elements in either of the two lists stay valid. Takes constant time.

Parameters:
pos position
it position of element to be inserted

void splice(iterator pos, iterator it, iterator end) [public]

Inserts the elements [it,end) refers to before pos into this list. It is assumed that [it,end) lies in a different list. All iterators to elements in either of the two lists stay valid. Takes constant time.

Parameters:
pos position
it position of one-past the last element to be inserted

iterator erase(iterator pos) [public]

Deletes element at position pos from list.

Parameters:
pos position to be deleted
Returns:
position of next element.

iterator erase(iterator it, iterator end) [public]

Deletes the elements [it, end) from list.

Parameters:
end one-past the last position to be deleted
it first position to be deleted
Returns:
position of next element.

void turn() [public]

Change the direction of list. Takes constant time.


Kdoc