Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

regina::NIndexedArray< Data, HashFcn, EqualTo > Class Template Reference
[General Utility Classes]

A dynamically resizable array of objects of type T with fast random access and fast object-to-index lookup. More...

#include <nindexedarray.h>

List of all members.

Public Types

typedef ObjectArray::value_type value_type
 See the C++ standard.
typedef ObjectArray::pointer pointer
 See the C++ standard.
typedef ObjectArray::const_reference const_reference
 See the C++ standard.
typedef ObjectArray::size_type size_type
 See the C++ standard.
typedef ObjectArray::difference_type difference_type
 See the C++ standard.
typedef ObjectArray::const_iterator iterator
 See the C++ standard.
typedef ObjectArray::const_iterator const_iterator
 See the C++ standard.
typedef ObjectArray::const_reverse_iterator reverse_iterator
 See the C++ standard.
typedef ObjectArray::const_reverse_iterator const_reverse_iterator
 See the C++ standard.

Public Member Functions

 NIndexedArray ()
 See the C++ standard.
 NIndexedArray (size_type n)
 See the C++ standard.
 NIndexedArray (size_type n, const Data &t)
 See the C++ standard.
 NIndexedArray (const NIndexedArray< Data, HashFcn, EqualTo > &array)
 See the C++ standard.
template<class InputIterator>
 NIndexedArray (InputIterator first, InputIterator last)
 See the C++ standard.
 ~NIndexedArray ()
 See the C++ standard.
iterator begin ()
 See the C++ standard.
iterator end ()
 See the C++ standard.
const_iterator begin () const
 See the C++ standard.
const_iterator end () const
 See the C++ standard.
reverse_iterator rbegin ()
 See the C++ standard.
reverse_iterator rend ()
 See the C++ standard.
const_reverse_iterator rbegin () const
 See the C++ standard.
const_reverse_iterator rend () const
 See the C++ standard.
size_type size () const
 See the C++ standard.
size_type max_size () const
 See the C++ standard.
bool empty () const
 See the C++ standard.
const_reference operator[] (size_type n) const
 See the C++ standard.
NIndexedArray< Data, HashFcn > & operator= (const NIndexedArray< Data, HashFcn, EqualTo > &array)
 See the C++ standard.
const_reference front () const
 See the C++ standard.
const_reference back () const
 See the C++ standard.
void push_back (const Data &item)
 See the C++ standard.
void pop_back ()
 See the C++ standard.
void swap (NIndexedArray< Data, HashFcn > &array)
 See the C++ standard.
iterator insert (iterator pos, const Data &x)
 See the C++ standard.
template<class InputIterator>
void insert (iterator pos, InputIterator first, InputIterator last)
 See the C++ standard.
void insert (iterator pos, size_type n, const Data &x)
 See the C++ standard.
iterator erase (iterator pos)
 See the C++ standard.
iterator erase (iterator first, iterator last)
 See the C++ standard.
void clear ()
 See the C++ standard.
void resize (size_type n)
 See the C++ standard.
void resize (size_type n, const Data &t)
 See the C++ standard.
difference_type index (const_reference value) const
 Finds the index of the given value in the array.
void erase (const_reference value)
 Erases all copies of the given object from the array.
bool validate (bool silent=false) const
 Checks the structural integrity of this array.


Detailed Description

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
class regina::NIndexedArray< Data, HashFcn, EqualTo >

A dynamically resizable array of objects of type T with fast random access and fast object-to-index lookup.

The fast object-to-index lookup is achieved by using a hashed dictionary mapping objects to array indices. See routine index() for further details.

This class satisfies all of the requirements of a random access container and a back insertion sequence in the C++ standard, with the exception that once an object has been inserted into the container it cannot be modified. Thus all routines returning a reference instead of a const_reference have been removed, and type iterator is the same as type const_iterator (and similarly for reverse iterators).

Additional routines beyond the C++ standard requirements include index(), erase(const_reference) and validate().

Template parameter HashFcn will be used to generate hash values for array elements. Template parameter EqualTo will be used to compare array elements when looking up the corresponding array index.

Precondition:
Template parameter HashFcn satisfies the requirements of a hash function (with argument type Data) according to the Standard Template Library.

Test:
Test suite contains thorough tests.
Python:
Not present.


Member Typedef Documentation

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::const_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::const_iterator
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::const_reference regina::NIndexedArray< Data, HashFcn, EqualTo >::const_reference
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::const_reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::const_reverse_iterator
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::difference_type regina::NIndexedArray< Data, HashFcn, EqualTo >::difference_type
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::const_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::iterator
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::pointer regina::NIndexedArray< Data, HashFcn, EqualTo >::pointer
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::const_reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::reverse_iterator
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::size_type regina::NIndexedArray< Data, HashFcn, EqualTo >::size_type
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
typedef ObjectArray::value_type regina::NIndexedArray< Data, HashFcn, EqualTo >::value_type
 

See the C++ standard.


Constructor & Destructor Documentation

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
regina::NIndexedArray< Data, HashFcn, EqualTo >::NIndexedArray  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
regina::NIndexedArray< Data, HashFcn, EqualTo >::NIndexedArray size_type  n  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
regina::NIndexedArray< Data, HashFcn, EqualTo >::NIndexedArray size_type  n,
const Data &  t
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
regina::NIndexedArray< Data, HashFcn, EqualTo >::NIndexedArray const NIndexedArray< Data, HashFcn, EqualTo > &  array  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
template<class InputIterator>
regina::NIndexedArray< Data, HashFcn, EqualTo >::NIndexedArray InputIterator  first,
InputIterator  last
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
regina::NIndexedArray< Data, HashFcn, EqualTo >::~NIndexedArray  )  [inline]
 

See the C++ standard.


Member Function Documentation

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_reference regina::NIndexedArray< Data, HashFcn, EqualTo >::back  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::begin  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::begin  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::clear  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
bool regina::NIndexedArray< Data, HashFcn, EqualTo >::empty  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::end  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::end  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::erase const_reference  value  )  [inline]
 

Erases all copies of the given object from the array.

This routine is made quite fast through use of the internal hashed dictionary.

Parameters:
value the object to remove from the array.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::erase iterator  first,
iterator  last
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::erase iterator  pos  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_reference regina::NIndexedArray< Data, HashFcn, EqualTo >::front  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
difference_type regina::NIndexedArray< Data, HashFcn, EqualTo >::index const_reference  value  )  const [inline]
 

Finds the index of the given value in the array.

This routine is made quite fast through use of the internal hashed dictionary.

If the given value is stored more than once in the array, one of its indices will be returned but there is no guarantee as to which of these indices it will be.

Parameters:
value the object to search for in the array.
Returns:
the corresponding array index, or -1 if the given object does not exist in the array.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::insert iterator  pos,
size_type  n,
const Data &  x
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
template<class InputIterator>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::insert iterator  pos,
InputIterator  first,
InputIterator  last
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::insert iterator  pos,
const Data &  x
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
size_type regina::NIndexedArray< Data, HashFcn, EqualTo >::max_size  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
NIndexedArray<Data, HashFcn>& regina::NIndexedArray< Data, HashFcn, EqualTo >::operator= const NIndexedArray< Data, HashFcn, EqualTo > &  array  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_reference regina::NIndexedArray< Data, HashFcn, EqualTo >::operator[] size_type  n  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::pop_back  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::push_back const Data &  item  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::rbegin  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::rbegin  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
const_reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::rend  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
reverse_iterator regina::NIndexedArray< Data, HashFcn, EqualTo >::rend  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::resize size_type  n,
const Data &  t
[inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::resize size_type  n  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
size_type regina::NIndexedArray< Data, HashFcn, EqualTo >::size  )  const [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
void regina::NIndexedArray< Data, HashFcn, EqualTo >::swap NIndexedArray< Data, HashFcn > &  array  )  [inline]
 

See the C++ standard.

template<class Data, class HashFcn = stdhash::hash<Data>, class EqualTo = std::equal_to<Data>>
bool regina::NIndexedArray< Data, HashFcn, EqualTo >::validate bool  silent = false  )  const [inline]
 

Checks the structural integrity of this array.

The internal hashed dictionary is compared with the internal array to ensure they are consistent with one another.

Any inconsistencies are written to standard error (unless parameter silent is passed as true).

Parameters:
silent true if error reporting should be suppressed, or false (the default) if errors should be reported to standard error as described above. Either way, the return value can still be used to determine if any inconsistencies were discovered.
Returns:
true if no problems were found, or false if any inconsistencies were discovered.


The documentation for this class was generated from the following file:
Copyright © 1999-2004, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).