SortedList< T, C, A > Class Template Reference

#include <elm/data/SortedList.h>

Classes
class	Iter

Public Types
typedef T	t
typedef SortedList< T, C, A >	self_t

Public Member Functions
	SortedList (void)
	SortedList (const SortedList< T, C, A > &l)
C &	comparator ()
const C &	comparator () const
A &	allocator ()
void	removeFirst (void)
void	removeLast (void)
int	count (void) const
bool	contains (const T &item) const
template<class CC >
bool	containsAll (const CC &c) const
bool	isEmpty (void) const
	operator bool (void) const
Iter	items (void) const
Iter	operator* (void) const
	operator Iter (void) const
Iter	begin (void) const
Iter	end (void) const
bool	equals (const SortedList< T > &l) const
bool	operator== (const SortedList< T > &l) const
bool	operator!= (const SortedList< T > &l) const
void	clear (void)
void	copy (const SortedList< T > &l)
void	add (const T &value)
template<class CC >
void	addAll (const CC &c)
void	remove (const T &item)
template<class CC >
void	removeAll (const CC &c)
void	remove (const Iter &iter)
SortedList< T > &	operator+= (const T &v)
SortedList< T > &	operator-= (const T &v)
const T &	first (void) const
const T &	last (void) const
Iter	find (const T &item, const Iter &iter) const
Iter	find (const T &item) const
T &	at (const Iter &i)
Iter	nth (int n) const
SortedList< T, C > &	operator= (const SortedList< T, C > &sl)
bool	operator& (const T &e) const
T &	operator[] (int k)
const T &	operator[] (int k) const

Protected Types
typedef List< T, CompareEquiv< C >, A >	list_t

Protected Member Functions
void	set (Iter i, const T &val)

Protected Attributes
list_t	list

Detailed Description

template<class T, class C = Comparator<T>, class A = DefaultAlloc>
class elm::SortedList< T, C, A >

This class provides a sorted list implementation using single-link lists (List). Elements are sorted in increasing order of the used comparator.

Its performances are not very good but the memory footprint is very low. Use it only for small collection of elements.

Performances

• adding an item: O(n) worst, O(n/2) average.
• looking/removing an item: O(n) worst, O(n/2) average.
• memory footprint: same as List.

Implemented concepts

elm::concept::Collection elm::concept::MutableCollection elm::concept::List

Parameters

T	Type of data stored in the list.
A	Adapter to access key part (must implement concept elm::concept::Adapter).
C	Comparator of the stored items (must implement the concept elm::concept::Comparator).

Author

C. Ballabriga

H. Cassé casse.nosp@m.@iri.nosp@m.t.fr

Member Typedef Documentation

list_t

typedef List<T, CompareEquiv<C>, A> list_t

protected

self_t

typedef SortedList<T, C, A> self_t

t

typedef T t

Constructor & Destructor Documentation

SortedList() [1/2]

SortedList ( void  )

inline

SortedList() [2/2]

SortedList ( const SortedList< T, C, A > &  l )

inline

Member Function Documentation

add()

void add ( const T &  value )

inline

Referenced by ListSet< T, C, A >::insert(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator+=(), and ListMap< string, Section * >::put().

addAll()

void addAll ( const CC &  c )

inline

allocator()

A& allocator ( )

inline

at()

T& at ( const Iter &  i )

inline

begin()

Iter begin ( void  ) const

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::equals(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find(), and ListSet< T, C, A >::subsetOf().

clear()

void clear ( void  )

inline

comparator() [1/2]

C& comparator ( )

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::add(), ListSet< T, C, A >::diff(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::equals(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find(), ListSet< T, C, A >::join(), ListSet< T, C, A >::meet(), and ListSet< T, C, A >::subsetOf().

comparator() [2/2]

const C& comparator ( ) const

inline

contains()

bool contains ( const T &  item ) const

inline

Referenced by ListMap< string, Section * >::contains(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::containsAll(), and ListSet< T, C, A >::insert().

containsAll()

bool containsAll ( const CC &  c ) const

inline

copy()

void copy ( const SortedList< T > &  l )

inline

count()

int count ( void  ) const

inline

Count the items in the list.

Returns

Item count.

Referenced by ListMap< string, Section * >::count().

end()

Iter end ( void  ) const

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::contains(), and SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find().

equals()

bool equals ( const SortedList< T > &  l ) const

inline

Referenced by ListMap< string, Section * >::equals(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator!=(), and SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator==().

find() [1/2]

Iter find ( const T &  item ) const

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find().

find() [2/2]

Iter find ( const T &  item, const Iter &  iter  ) const

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::contains().

first()

const T & first ( void  ) const

inline

Get the first item of the list.

Returns

First item.

Warning

It is an error to call this method if the list is empty.

isEmpty()

bool isEmpty ( void  ) const

inline

Test if the list is empty.

Returns

True if the list is empty, false else.

Referenced by ListMap< string, Section * >::isEmpty().

items()

Iter items ( void  ) const

inline

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::begin(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator Iter(), and SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator*().

last()

const T & last ( void  ) const

inline

Get the last item of the list. Remark that this method is really inefficient. Its working time is in O(n), n number of nodes in the list. Use it only with small list or revert to more powerful data structures.

Returns

Last item.

Warning

It is an error to call this method if the list is empty.

nth()

Iter nth ( int  n ) const

inline

operator bool()

operator bool ( void  ) const

inline

operator Iter()

operator Iter ( void  ) const

inline

operator!=()

bool operator!= ( const SortedList< T > &  l ) const

inline

operator&()

bool operator& ( const T &  e ) const

inline

operator*()

Iter operator* ( void  ) const

inline

operator+=()

SortedList<T>& operator+= ( const T &  v )

inline

operator-=()

SortedList<T>& operator-= ( const T &  v )

inline

operator=()

SortedList<T, C>& operator= ( const SortedList< T, C > &  sl )

inline

operator==()

bool operator== ( const SortedList< T > &  l ) const

inline

operator[]() [1/2]

T& operator[] ( int  k )

inline

operator[]() [2/2]

const T& operator[] ( int  k ) const

inline

remove() [1/2]

void remove ( const Iter &  iter )

inline

remove() [2/2]

void remove ( const T &  item )

inline

Remove the given item from the list or just one if the list contains many items equals to the given one. The item type T must support the equality / inequality operators.

Parameters

item	Item to remove.

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator-=(), ListSet< T, C, A >::operator-=(), and ListMap< string, Section * >::remove().

removeAll()

void removeAll ( const CC &  c )

inline

removeFirst()

void removeFirst ( void  )

inline

Remove the first item from the list.

Warning

It is an error to call this method if the list is empty.

removeLast()

void removeLast ( void  )

inline

Remove the last item from the list. Remark that this method is really inefficient. Its working time is in O(n), n number of nodes in the list. Use it only with small list or revert to more powerful data structures.

Warning

It is an error to call this method if the list is empty.

set()

void set ( Iter  i, const T &  val  )

inlineprotected

Referenced by ListMap< string, Section * >::put().

Member Data Documentation

list

list_t list

protected

Referenced by SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::add(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::addAll(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::allocator(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::at(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::clear(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::comparator(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::copy(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::count(), ListSet< T, C, A >::diff(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::first(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::isEmpty(), ListSet< T, C, A >::join(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::last(), ListSet< T, C, A >::meet(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator bool(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator&(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator=(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::operator[](), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::remove(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::removeAll(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::removeFirst(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::removeLast(), and SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::set().

---

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

• include/elm/data/SortedList.h
• src/data_SortedList.cpp