Elgrint::MHash<T> class

Declared in MHash.h

Description

Linear unordered collection with exceptionally fast insertions and removals.

MHash

Base class: Collection

Template parameters:

Name Description
T

The type of any value in the hash.

Details: The T type must have a public copy constructor, destructor, default constructor, and the comparison operator==. Also, the MNum HashNumerator(const T&) function must be defined for T (it defines a relation from T to MNum, which is used internally by the hashing function). See HashNumerator for more details. All these conditions are already satisfied by all built-in and atomic types (except for bool), and also by MChar and MString. This should be enough for vast majority of conceivable usage scenarios. If not, then these conditions are easily expanded to other types.

Remarks:

Classes:

Name Description
CIter The constant iterator of MHash. Equivalent to its base class (does not define any new members).

Mutators:

Name Description
insert(x) Inserts a copy of x into the hash.
remove(x) Removes an element that is equal to x (if it exists) from the hash.

Revealers:

Name Description
has(x) Returns true iff the hash contains a value that is equal to x. Average time complexity is O(1).

Details

MHash is an implementation of a hash table data structure. A hash table allows items to be inserted, located, and removed in O(1) time on average (see Complexity). This is accomplished using a special hash function, which "shuffles" the items in the table in a certain way. However, this also means that the order of items is irrelevant and can change profoundly on any insert/remove operation.

'MHash' does not use the standard "hash buckets" structure - all items are kept in the table itself. This makes MHash much more efficient, because there is only one memory allocation for all items. However, this efficiency depends on the size of the item. It is best to keep items small, not some huge structs. The items need to be physically moved frequently, so they need to support an efficient copying. All Elgrint collections can serve as MHash items, thanks to the fast copy mechanism, providing that an efficient HashNumerator is defined for them (by default HashNumerator is defined only for MString collection).

The items are inserted and removed using insert and remove methods respectively. The Boolean has revealer shows whether a given value exists in the hash. However, in most cases an iterator is a more useful revealer. MHash only has a constant iterator (CIter).

Let us know

Please Contact us to report any errors on this page, or to suggest any improvements.

Miranor Home | About Miranor | About Elgrint | Create account | Login | Account settings | Contact Us | Privacy Policy | Site map

© Copyright 2014 by Miranor. All rights reserved. By using this site you agree to the Terms of Use.

Page last updated on August 10th, 2014.