hudson::SmallList< Item > Class Template Reference

#include <SmallList.h>

Inheritance diagram for hudson::SmallList< Item >:

List of all members.

Public Types
typedef Item	value_type
typedef Item &	reference
typedef const Item &	const_reference
Public Member Functions
	SmallList ()
	~SmallList ()
	SmallList (const SmallList &other)
SmallList &	operator= (const SmallList &other)
bool	empty () const
void	clear ()
template<class ItemCtorArg>
void	push_front (const ItemCtorArg &arg)
void	push_front ()
void	pop_front ()
const Item &	front () const
Item &	front ()
iterator	begin ()
iterator	end ()
template<class ItemCtorArg>
iterator	insert (iterator it, const ItemCtorArg &arg)
iterator	insert (iterator it)
iterator	erase (iterator it)
const_iterator	begin () const
const_iterator	end () const
void	swap (SmallList &other)
void	reverse ()
void	merge (SmallList &other)
void	unique ()
Classes
class	const_iterator
class	iterator
struct	Node

---

Detailed Description

template<class Item>
class hudson::SmallList< Item >

A list with premium on being small. We achieve this in four ways:

• no tail pointer
• no size counter
• singly-linked
• use SmallMemoryPool for the nodes, which has no malloc overhead (unless the payload is very large).

To implement constant-time insert/erase with a singly-linked list, the iterator class has a prev field. Note that end() is constant time, but we don't have a tail pointer. Therefore, insert(end()) is linear time. However, if we have an iterator that walked all the way to the end(), its prev is valid, so insert(it) is constant time even if it == end() is true -- but only if we walked it from begin() to end().

To reduce temptations, size() and *_back() are not declared.

Every insert function has a no-arg version that allows inserting elements that do not have copy constructors. Of course, these must have default constructors.

---

Member Typedef Documentation

template<class Item> typedef const Item& hudson::SmallList< Item >::const_reference

template<class Item> typedef Item& hudson::SmallList< Item >::reference

template<class Item> typedef Item hudson::SmallList< Item >::value_type

---

Constructor & Destructor Documentation

template<class Item> hudson::SmallList< Item >::SmallList (   )  [inline]

template<class Item> hudson::SmallList< Item >::~SmallList (   )  [inline]

template<class Item> hudson::SmallList< Item >::SmallList (  const SmallList< Item > &  other  )  [inline]

Must have a copy ctor for Item

---

Member Function Documentation

template<class Item> const_iterator hudson::SmallList< Item >::begin (   )  const [inline]

template<class Item> iterator hudson::SmallList< Item >::begin (   )  [inline]

template<class Item> void hudson::SmallList< Item >::clear (   )  [inline]

template<class Item> bool hudson::SmallList< Item >::empty (   )  const [inline]

template<class Item> const_iterator hudson::SmallList< Item >::end (   )  const [inline]

template<class Item> iterator hudson::SmallList< Item >::end (   )  [inline]

template<class Item> iterator hudson::SmallList< Item >::erase (  iterator  it  )  [inline]

template<class Item> Item& hudson::SmallList< Item >::front (   )  [inline]

template<class Item> const Item& hudson::SmallList< Item >::front (   )  const [inline]

template<class Item> iterator hudson::SmallList< Item >::insert (  iterator  it  )  [inline]

template<class Item> template<class ItemCtorArg> iterator hudson::SmallList< Item >::insert (  iterator  it, const ItemCtorArg &  arg )  [inline]

template<class Item> void hudson::SmallList< Item >::merge (  SmallList< Item > &  other  )  [inline]

Merge two lists; fundamental operation in merge sort. The argument is destroyed, and the current list modified in place. No items are copied: we just steal nodes.

template<class Item> SmallList& hudson::SmallList< Item >::operator= (  const SmallList< Item > &  other  )  [inline]

Must have a copy ctor for Item

template<class Item> void hudson::SmallList< Item >::pop_front (   )  [inline]

template<class Item> void hudson::SmallList< Item >::push_front (   )  [inline]

template<class Item> template<class ItemCtorArg> void hudson::SmallList< Item >::push_front (  const ItemCtorArg &  arg  )  [inline]

template<class Item> void hudson::SmallList< Item >::reverse (   )  [inline]

Reverse in linear time, but with no copying.

template<class Item> void hudson::SmallList< Item >::swap (  SmallList< Item > &  other  )  [inline]

Constant-time swap.

template<class Item> void hudson::SmallList< Item >::unique (   )  [inline]

Remove duplicates from the list.

---

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

• utilities/SmallList.h

---