Regina Calculation Engine
Public Types | Public Member Functions
regina::NIndexedArray< Data, HashFcn, EqualTo > Class Template Reference

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

#include <utilities/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:
Exhaustively tested in the test suite.
Python:
Not present.
Deprecated:
Like everything else that relies on the non-standard STL/g++ extension classes hash_set and hash_map, NIndexedArray is scheduled to be removed from Regina in version 5.0. For a replacement, NMarkedVector does a similar job and is smaller and faster, though it requires modification of the data types stored in the array.

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>>
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>>
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>>
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>>
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>>
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 >::erase ( iterator  pos) [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  first,
iterator  last 
) [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:
valuethe object to remove from the array.
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:
valuethe 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>>
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>>
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>>
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>>
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>>
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 >::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 >::rend ( ) [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>>
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>>
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>>
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:
silenttrue 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-2012, The Regina development team
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).