CxxUtils::pointer_list< NELT > Class Template Reference

A fast way to store a variable-sized collection of pointers. More...

#include <pointer_list.h>

Inheritance diagram for CxxUtils::pointer_list< NELT >:

Collaboration diagram for CxxUtils::pointer_list< NELT >:

Classes
class	allocator
	Allocator for pointer_list, specialized for NELT. More...
class	iterator
	Forward iterator over the list. More...

Public Types
typedef pointer_list_base::value_type	value_type
	Stored value type.
typedef allocator	pool_type

Public Member Functions
	pointer_list (pool_type &pool)
	Constructor. pool gives the allocator for this container.
iterator	begin ()
	Iterator at the beginning of the container.
iterator	end ()
	Iterator at the end of the container.
void	erase (iterator it)
	Erase one element. O(n)
void	push_back (value_type p)
	Add a new element to the end of the container. O(1)
size_t	size () const
	The current size of the container. O(1).
void	clear ()
	Erase the container.
bool	empty () const
	Test to see if the container is empty.

Protected Member Functions
void	firstblock ()
	Allocate the first block of the list.
void	nextblock ()
	Extend the list with another block.
list_block *	getblock ()
	Allocate a new block.

Protected Attributes
list_block *	m_head
	The first block in the list.
value_type *	m_insert
	The current insertion point in the list.
size_t	m_size
	The current list size.
allocator &	m_pool
	The list allocator.

Detailed Description

template<size_t NELT = 15>
class CxxUtils::pointer_list< NELT >

A fast way to store a variable-sized collection of pointers.

If you're growing a variable-sized collection of things, all the STL containers have some performance issues. A std::vector needs to reallocate and copy its data as it grows. The use of variable-sized allocations also means that one cannot use the very efficient fixed-size memory allocators. A std::list incurs a separate memory allocation for each element, and, if the elements are pointers, has a substantial size overhead.

The class here is a compromise, which builds a list consisting of fixed-size chunks.

The operations supported are rather limited. We support forward iteration, push_back, and erase (though the latter can have O(n) complexity).

For best performance, we use our own allocator, an instance of which gets passed to the pointer_list constructor. Memory is not freed until the allocator is destroyed.

This class is templated on the number of elements stored per block. This must be one less than a power of two.

Definition at line 240 of file pointer_list.h.

Member Typedef Documentation

pool_type

template<size_t NELT = 15>

typedef allocator CxxUtils::pointer_list< NELT >::pool_type

Definition at line 315 of file pointer_list.h.

value_type

template<size_t NELT = 15>

typedef pointer_list_base::value_type CxxUtils::pointer_list< NELT >::value_type

Stored value type.

Definition at line 245 of file pointer_list.h.

Constructor & Destructor Documentation

pointer_list()

template<size_t NELT = 15>

CxxUtils::pointer_list< NELT >::pointer_list

(

pool_type &

pool

)

Constructor. pool gives the allocator for this container.

Member Function Documentation

begin()

template<size_t NELT = 15>

iterator CxxUtils::pointer_list< NELT >::begin

(

)

Iterator at the beginning of the container.

clear()

void CxxUtils::pointer_list_base::clear ( )

inherited

Erase the container.

O(1). Note: doesn't free memory. Memory currently in use will be reused when the container is filled again.

Definition at line 89 of file pointer_list.cxx.

{
  if (m_head)
    m_insert = &m_head->m_data[0];
  m_size = 0;
}

empty()

bool CxxUtils::pointer_list_base::empty ( ) const

inherited

Test to see if the container is empty.

end()

template<size_t NELT = 15>

iterator CxxUtils::pointer_list< NELT >::end

(

)

Iterator at the end of the container.

erase()

template<size_t NELT = 15>

void CxxUtils::pointer_list< NELT >::erase

(

iterator

it

)

Erase one element. O(n)

firstblock()

void CxxUtils::pointer_list_base::firstblock ( )

protectedinherited

Allocate the first block of the list.

Definition at line 100 of file pointer_list.cxx.

{
  m_head = getblock();
  m_insert = &m_head->m_data[0];
}

getblock()

pointer_list_base::list_block * CxxUtils::pointer_list_base::getblock ( )

protectedinherited

Allocate a new block.

Definition at line 127 of file pointer_list.cxx.

{
  list_block* b = m_pool.allocate();
  size_t maxndx = m_pool.nelt();
 
  // Make sure only the last element has the sentinel bit set.
  std::fill (b->m_data, b->m_data + maxndx, value_type());
  b->m_data[maxndx] = 0;
 
  return b;
}

nextblock()

void CxxUtils::pointer_list_base::nextblock ( )

protectedinherited

Extend the list with another block.

m_insert should be at the end of the last block.

Definition at line 111 of file pointer_list.cxx.

{
  // There may be one already allocated.  Use it if so.
  list_block* newblock = 
    reinterpret_cast<list_block*> (*m_insert);
  if (!newblock) {
    newblock = getblock();
    *m_insert = newblock;
  }
  m_insert = &newblock->m_data[0];
}

push_back()

void CxxUtils::pointer_list_base::push_back ( value_type p )

inherited

Add a new element to the end of the container. O(1)

size()

size_t CxxUtils::pointer_list_base::size ( ) const

inherited

The current size of the container. O(1).

Member Data Documentation

m_head

list_block* CxxUtils::pointer_list_base::m_head

protectedinherited

The first block in the list.

Definition at line 191 of file pointer_list.h.

m_insert

value_type* CxxUtils::pointer_list_base::m_insert

protectedinherited

The current insertion point in the list.

Definition at line 194 of file pointer_list.h.

m_pool

allocator& CxxUtils::pointer_list_base::m_pool

protectedinherited

The list allocator.

Definition at line 200 of file pointer_list.h.

m_size

size_t CxxUtils::pointer_list_base::m_size

protectedinherited

The current list size.

Definition at line 197 of file pointer_list.h.

---

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

• pointer_list.h