ROSE  0.11.145.0
Classes | Public Types | Public Member Functions | List of all members
Sawyer::Container::IndexedList< T, Alloc > Class Template Reference

Description

template<class T, class Alloc = DefaultAllocator>
class Sawyer::Container::IndexedList< T, Alloc >

Doubly-linked list with constant-time indexing.

This container is a hybrid of a doubly-linked list and a vector, having these features:

Element ID numbers are consecutive unsigned integers between zero (inclusive) and the size of the list (exclusive), and are convenient for indexing into lookup tables that the user keeps separate from the list itself. However, in order to meet the requirement the erasure is a constant-time operation, when an element is erased from the list, the element that had the largest ID number is given the ID of the element that was erased. In other words, ID numbers are not stable across erasure. This is actually not much different than using array indices as ID numbers and erasing an item from the middle of the array, except that the approach taken by IndexedList is contant rather than linear time.

Also, the order of ID numbers is not required to be identical to the order of the elements in the list. One may iterate over the elements in list order by using iterators, or iterate over the elements in ID order by using a simple "for" loop.

IndexedList<MyClass> list;
// Iteration in list order
for (MyClass::Iterator i=list.begin(); i!=list.end(); ++i)
std::cout <<"member #" <<i.id() <<" = " <<*i <<"\n";
// Iteration in ID order
for (size_t i=0; i<list.size(); ++i)
std::cout <<"member #" <<i <<" = " <<list[i] <<"\n";

This container, as with the rest of the library, uses CamelCase names for types and methods, where types begin with an upper-case letter and methods begin with a lower-case letter. This may be surprising for users accustomed to the STL naming scheme. For instance, iterators are named Iterator, ConstIterator, etc., rather than iterator, const_iterator, etc.

Definition at line 78 of file IndexedList.h.

#include <util/Sawyer/IndexedList.h>

Inheritance diagram for Sawyer::Container::IndexedList< T, Alloc >:
Inheritance graph
[legend]

Classes

class  ConstNodeIterator
 List const node bidirectional iterator. More...
 
class  ConstValueIterator
 List const value bidirectional iterator. More...
 
class  Node
 Combination user-defined value and ID number. More...
 
class  NodeIterator
 List node bidirectional iterator. More...
 
class  ValueIterator
 List value bidirectional iterator. More...
 

Public Types

typedef T Value
 Type of values stored in this container. More...
 
typedef Alloc Allocator
 Allocator for the storage nodes. More...
 

Public Member Functions

 IndexedList (const Allocator &allocator=Allocator())
 Default constructor. More...
 
 IndexedList (const IndexedList &other)
 Copy constructor. More...
 
template<class T2 , class Alloc2 >
 IndexedList (const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
 Copy constructor. More...
 
 IndexedList (size_t nElmts, const Value &val=Value(), const Allocator &allocator=Allocator())
 Filling constructor. More...
 
IndexedListoperator= (const IndexedList &other)
 Assignment from another list. More...
 
template<class T2 >
IndexedListoperator= (const IndexedList< T2 > &other)
 Assignment from another list. More...
 
const Allocatorallocator () const
 Allocator. More...
 
bool isEmpty () const
 Determines if this list is empty. More...
 
size_t size () const
 Number of elements in list. More...
 
IndexedListpushFront (const Value &value)
 Insert at the front of the list. More...
 
IndexedListpushBack (const Value &value)
 Insert at the back of the list. More...
 
NodeIterator insert (const ValueIterator &position, const Value &value)
 Insert element at position. More...
 
IndexedListinsert (const ValueIterator &position, size_t nElmts, const Value &value)
 Insert multiple copies at position. More...
 
template<class OtherValueIterator >
IndexedListinsertMultiple (const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
 Insert elements at position. More...
 
void clear ()
 Empties the list. More...
 
NodeIterator erase (size_t id)
 Erase one element. More...
 
NodeIterator eraseAt (const ValueIterator &position)
 Remove one element. More...
 
NodeIterator eraseAtMultiple (const boost::iterator_range< NodeIterator > &range)
 
NodeIterator eraseAtMultiple (const boost::iterator_range< ValueIterator > &range)
 
void dump (std::ostream &o) const
 
boost::iterator_range< NodeIteratornodes ()
 All elements. More...
 
boost::iterator_range< ConstNodeIteratornodes () const
 All elements. More...
 
boost::iterator_range< ValueIteratorvalues ()
 All elements. More...
 
boost::iterator_range< ConstValueIteratorvalues () const
 All elements. More...
 
size_t capacity () const
 Allocated capacity of the index. More...
 
void capacity (size_t n)
 Allocated capacity of the index. More...
 
NodeIterator find (size_t id)
 Lookup by ID. More...
 
ConstNodeIterator find (size_t id) const
 Lookup by ID. More...
 
NodefrontNode ()
 First element of list. More...
 
const NodefrontNode () const
 First element of list. More...
 
ValuefrontValue ()
 First element of list. More...
 
const ValuefrontValue () const
 First element of list. More...
 
NodebackNode ()
 Last element of list. More...
 
const NodebackNode () const
 Last element of list. More...
 
ValuebackValue ()
 Last element of list. More...
 
const ValuebackValue () const
 Last element of list. More...
 
NodeindexedNode (size_t id)
 Element reference by ID. More...
 
const NodeindexedNode (size_t id) const
 Element reference by ID. More...
 
ValueindexedValue (size_t id)
 Element reference by ID. More...
 
const ValueindexedValue (size_t id) const
 Element reference by ID. More...
 
Valueoperator[] (size_t id)
 Element reference by ID. More...
 
const Valueoperator[] (size_t id) const
 Element reference by ID. More...
 
Optional< ValuegetOptional (size_t id) const
 Element reference by ID. More...
 
ValuegetOrElse (size_t id, Value &dflt)
 Element reference by ID. More...
 
const ValuegetOrElse (size_t id, const Value &dflt) const
 Element reference by ID. More...
 
const ValuegetOrDefault (size_t id) const
 Element reference by ID. More...
 

Member Typedef Documentation

template<class T, class Alloc = DefaultAllocator>
typedef T Sawyer::Container::IndexedList< T, Alloc >::Value

Type of values stored in this container.

Definition at line 80 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
typedef Alloc Sawyer::Container::IndexedList< T, Alloc >::Allocator

Allocator for the storage nodes.

Definition at line 81 of file IndexedList.h.

Constructor & Destructor Documentation

template<class T, class Alloc = DefaultAllocator>
Sawyer::Container::IndexedList< T, Alloc >::IndexedList ( const Allocator allocator = Allocator())
inlineexplicit

Default constructor.

Create a new list which is empty.

Definition at line 363 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Sawyer::Container::IndexedList< T, Alloc >::IndexedList ( const IndexedList< T, Alloc > &  other)
inline

Copy constructor.

The newly constructed list's allocator is copy-constructed from the source list's allocator. For allocators that contain state (like pool allocators), this copies the settings but not the pools of allocated data.

Definition at line 370 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
template<class T2 , class Alloc2 >
Sawyer::Container::IndexedList< T, Alloc >::IndexedList ( const IndexedList< T2, Alloc2 > &  other,
const Allocator = Allocator() 
)
inline

Copy constructor.

Definition at line 377 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Sawyer::Container::IndexedList< T, Alloc >::IndexedList ( size_t  nElmts,
const Value val = Value(),
const Allocator allocator = Allocator() 
)
inlineexplicit

Filling constructor.

Constructs the list by inserting nElmts copies of val.

Definition at line 387 of file IndexedList.h.

Member Function Documentation

template<class T, class Alloc = DefaultAllocator>
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::operator= ( const IndexedList< T, Alloc > &  other)
inline

Assignment from another list.

Causes this list to look like the other list in that this list has copies of the nodes of the other list. However, the ID numbers in this list may be different than the ID numbers of the other list.

Definition at line 398 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
template<class T2 >
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::operator= ( const IndexedList< T2 > &  other)
inline

Assignment from another list.

Causes this list to look like the other list in that this list has copies of the nodes of the other list. However, the ID numbers in this list may be different than the ID numbers of the other list.

Definition at line 409 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
const Allocator& Sawyer::Container::IndexedList< T, Alloc >::allocator ( ) const
inline

Allocator.

Returns a reference to the allocator that's being used for elements of this list.

Definition at line 423 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
boost::iterator_range<NodeIterator> Sawyer::Container::IndexedList< T, Alloc >::nodes ( )
inline

All elements.

Returns an iterator range that references all nodes in the container in their list order.

Definition at line 437 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::operator=(), Sawyer::Container::IndexedList< Edge, Allocator >::pushBack(), and Sawyer::Container::IndexedList< Edge, Allocator >::pushFront().

template<class T, class Alloc = DefaultAllocator>
boost::iterator_range<ConstNodeIterator> Sawyer::Container::IndexedList< T, Alloc >::nodes ( ) const
inline

All elements.

Returns an iterator range that references all nodes in the container in their list order.

Definition at line 440 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
boost::iterator_range<ValueIterator> Sawyer::Container::IndexedList< T, Alloc >::values ( )
inline

All elements.

Returns an iterator range that references all nodes in the container in their list order.

Definition at line 443 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::IndexedList(), and Sawyer::Container::IndexedList< Edge, Allocator >::operator=().

template<class T, class Alloc = DefaultAllocator>
boost::iterator_range<ConstValueIterator> Sawyer::Container::IndexedList< T, Alloc >::values ( ) const
inline

All elements.

Returns an iterator range that references all nodes in the container in their list order.

Definition at line 446 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
bool Sawyer::Container::IndexedList< T, Alloc >::isEmpty ( ) const
inline

Determines if this list is empty.

Returns true only if this list contains no elements.

Definition at line 471 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::backNode(), Sawyer::Container::IndexedList< Edge, Allocator >::frontNode(), and Sawyer::Container::Stack< size_t >::isEmpty().

template<class T, class Alloc = DefaultAllocator>
size_t Sawyer::Container::IndexedList< T, Alloc >::size ( void  ) const
inline
template<class T, class Alloc = DefaultAllocator>
size_t Sawyer::Container::IndexedList< T, Alloc >::capacity ( ) const
inline

Allocated capacity of the index.

Each container maintains an index in order to achieve constant time lookup by node ID, and this method queries or changes the number of elements that the index is prepared to handle. If more elements are added to the index than it is prepared to handle, then a new index is created in linear time.

Definition at line 489 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
void Sawyer::Container::IndexedList< T, Alloc >::capacity ( size_t  n)
inline

Allocated capacity of the index.

Each container maintains an index in order to achieve constant time lookup by node ID, and this method queries or changes the number of elements that the index is prepared to handle. If more elements are added to the index than it is prepared to handle, then a new index is created in linear time.

Definition at line 492 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
NodeIterator Sawyer::Container::IndexedList< T, Alloc >::find ( size_t  id)
inline

Lookup by ID.

Returns a list iterator for the node with the specified ID number. The ID number must exist; i.e., it must be less than the number of elements in the list. This method executes in constant time.

Definition at line 509 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::erase().

template<class T, class Alloc = DefaultAllocator>
ConstNodeIterator Sawyer::Container::IndexedList< T, Alloc >::find ( size_t  id) const
inline

Lookup by ID.

Returns a list iterator for the node with the specified ID number. The ID number must exist; i.e., it must be less than the number of elements in the list. This method executes in constant time.

Definition at line 514 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Node& Sawyer::Container::IndexedList< T, Alloc >::frontNode ( )
inline

First element of list.

Returns a reference to the first element stored in this list. The list must not be empty.

Definition at line 532 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::frontValue().

template<class T, class Alloc = DefaultAllocator>
const Node& Sawyer::Container::IndexedList< T, Alloc >::frontNode ( ) const
inline

First element of list.

Returns a reference to the first element stored in this list. The list must not be empty.

Definition at line 536 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Value& Sawyer::Container::IndexedList< T, Alloc >::frontValue ( )
inline

First element of list.

Returns a reference to the first element stored in this list. The list must not be empty.

Definition at line 540 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::frontValue ( ) const
inline

First element of list.

Returns a reference to the first element stored in this list. The list must not be empty.

Definition at line 543 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Node& Sawyer::Container::IndexedList< T, Alloc >::backNode ( )
inline

Last element of list.

Returns a reference to the last element stored in this list. The list must not be empty.

Definition at line 553 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::backValue().

template<class T, class Alloc = DefaultAllocator>
const Node& Sawyer::Container::IndexedList< T, Alloc >::backNode ( ) const
inline

Last element of list.

Returns a reference to the last element stored in this list. The list must not be empty.

Definition at line 557 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Value& Sawyer::Container::IndexedList< T, Alloc >::backValue ( )
inline

Last element of list.

Returns a reference to the last element stored in this list. The list must not be empty.

Definition at line 561 of file IndexedList.h.

Referenced by Sawyer::Container::Stack< size_t >::top().

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::backValue ( ) const
inline

Last element of list.

Returns a reference to the last element stored in this list. The list must not be empty.

Definition at line 564 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Node& Sawyer::Container::IndexedList< T, Alloc >::indexedNode ( size_t  id)
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 575 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::indexedValue().

template<class T, class Alloc = DefaultAllocator>
const Node& Sawyer::Container::IndexedList< T, Alloc >::indexedNode ( size_t  id) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 580 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Value& Sawyer::Container::IndexedList< T, Alloc >::indexedValue ( size_t  id)
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 585 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::getOptional(), Sawyer::Container::IndexedList< Edge, Allocator >::getOrDefault(), Sawyer::Container::IndexedList< Edge, Allocator >::getOrElse(), and Sawyer::Container::IndexedList< Edge, Allocator >::operator[]().

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::indexedValue ( size_t  id) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 588 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Value& Sawyer::Container::IndexedList< T, Alloc >::operator[] ( size_t  id)
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 591 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::operator[] ( size_t  id) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 594 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Optional<Value> Sawyer::Container::IndexedList< T, Alloc >::getOptional ( size_t  id) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 598 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
Value& Sawyer::Container::IndexedList< T, Alloc >::getOrElse ( size_t  id,
Value dflt 
)
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 602 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::getOrElse ( size_t  id,
const Value dflt 
) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 605 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
const Value& Sawyer::Container::IndexedList< T, Alloc >::getOrDefault ( size_t  id) const
inline

Element reference by ID.

Returns a reference to the element with the specified ID number. The ID number must exist in this list. ID numbers are consecutive, beginning at zero.

Definition at line 609 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::pushFront ( const Value value)
inline

Insert at the front of the list.

Inserts a copy of the value at the beginning of the list. The new copy is given an ID number which one larger than the previously largest ID number in this list. No other element ID numbers are changed by this operation.

Definition at line 624 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::pushBack ( const Value value)
inline

Insert at the back of the list.

Inserts a copy of the value at the end of the list. The new copy is given an ID number which one larger than the previously largest ID number in this list. No other element ID numbers are changed by this operation.

Definition at line 633 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::IndexedList(), Sawyer::Container::Stack< size_t >::push(), and Sawyer::Container::Stack< size_t >::Stack().

template<class T, class Alloc = DefaultAllocator>
NodeIterator Sawyer::Container::IndexedList< T, Alloc >::insert ( const ValueIterator position,
const Value value 
)
inline

Insert element at position.

Inserts a copy of value at the indicated position in the list. The new copy is given an ID number which one larger than the previously largest ID number in this list. No other element ID numbers are changed by this operation.

Definition at line 642 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::insert(), Sawyer::Container::IndexedList< Edge, Allocator >::insertMultiple(), Sawyer::Container::IndexedList< Edge, Allocator >::operator=(), Sawyer::Container::IndexedList< Edge, Allocator >::pushBack(), and Sawyer::Container::IndexedList< Edge, Allocator >::pushFront().

template<class T, class Alloc = DefaultAllocator>
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::insert ( const ValueIterator position,
size_t  nElmts,
const Value value 
)
inline

Insert multiple copies at position.

Inserts nElmts copies of value at the indicated position. The new copies are given sequential ID numbers in the order they are inserted, with the first inserted element having an ID number which is one larger than the previously largest ID number in this list. No other element ID numbers are changed by this operation.

Definition at line 655 of file IndexedList.h.

template<class T, class Alloc = DefaultAllocator>
template<class OtherValueIterator >
IndexedList& Sawyer::Container::IndexedList< T, Alloc >::insertMultiple ( const ValueIterator position,
const boost::iterator_range< OtherValueIterator > &  range 
)
inline

Insert elements at position.

Inserts, at the indicated position, copies of the elements specified by the iterator range. The new copies are given sequential ID numbers in the order they are inserted, with the first inserted element having an ID number which is one larger than the previously largest ID number in this list. No other element ID numbers are changed by this operation.

Definition at line 668 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::operator=().

template<class T, class Alloc = DefaultAllocator>
void Sawyer::Container::IndexedList< T, Alloc >::clear ( )
inline

Empties the list.

Clears the list by removing all elements from it. This operation is linear time.

Definition at line 678 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::operator=().

template<class T, class Alloc = DefaultAllocator>
NodeIterator Sawyer::Container::IndexedList< T, Alloc >::erase ( size_t  id)
inline

Erase one element.

Erases the element having the specified ID. The ID number must exist in the list.

Definition at line 690 of file IndexedList.h.

Referenced by Sawyer::Container::Stack< size_t >::pop().

template<class T, class Alloc = DefaultAllocator>
NodeIterator Sawyer::Container::IndexedList< T, Alloc >::eraseAt ( const ValueIterator position)
inline

Remove one element.

Removes the element at the indicated position. The ID number of one other element (the one with the now highest ID) will be changed to fill the gap left by the erasure.

Definition at line 699 of file IndexedList.h.

Referenced by Sawyer::Container::IndexedList< Edge, Allocator >::erase().


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