Hash Table Container. More...
#include <rhashcontainer.h>
Public Member Functions | |
RHashContainer (size_t s, size_t m, size_t i=0) | |
size_t | GetNb (void) const |
RCursor< cHash > | GetCursor (void) const |
const cHash * | operator[] (size_t hash) const |
cHash * | operator[] (size_t hash) |
void | Clear (void) |
template<class TUse > | |
size_t | GetIndex (const TUse &tag, size_t &hash, bool &find) const |
template<class TUse > | |
bool | IsIn (const TUse &tag, bool sortkey=true) const |
template<class TUse > | |
C * | GetPtr (const TUse &tag, bool sortkey=true) const |
template<class TUse > | |
C * | GetInsertPtr (const TUse &tag, bool sortkey=true) |
void | InsertPtr (C *ins, bool del=false) |
void | InsertPtrAt (C *ins, size_t hash, size_t idx, bool del=false) |
template<class TUse > | |
void | DeletePtr (const TUse &tag, bool sortkey=true, bool del=bAlloc) |
virtual | ~RHashContainer (void) |
Private Types | |
typedef RContainer< C, bAlloc, true > | cHash |
Private Attributes | |
RContainer< cHash, true, false > | Hash |
Detailed Description
template<class C, bool bAlloc>
class R::RHashContainer< C, bAlloc >
Hash Table Container.
The RHashContainer provides a class to manage a container of elements (class C) with a hash table of a given fixed size. Each element must have a key (such an unique name), but the hash code must not be unique. The container can be responsible for the deallocation of the elements (bAlloc).
In practice, a table of the given size is allocated, each row representing a possible hash code. For each hash code, a container is maintained to manage elements sharing the same hash code.
- Template Parameters
-
C The class of the element to be contained. bAlloc Specify if the elements are deallocated by the container.
To make the necessary comparisons, the container uses methods of the class representing the elements (class C). These methods have the signature:
Look at R::RString and R::RCString for example of implementations.
The TUse represent a class or a structure used for the comparisons. The Compare method are working like the strcmp function from the standard C/C++ library. The result returned specifies if the tag precedes (>0), is the same (0) or is after (<0) the element used. The HashCode methods return the hash index of the given argument.
Here is an example of a container with a hash table managing instances of the class MyElement:
Member Typedef Documentation
|
private |
Constructor & Destructor Documentation
RHashContainer | ( | size_t | s, |
size_t | m, | ||
size_t | i = 0 |
||
) |
Constructor of the container. In practice, the sizes should be used with caution. If the size of the hash table is small in comparison with the number of elements, the initial sizes of the individual array should be larger.
- Parameters
-
s Size of the hash table. The hash codes of the elements must be in the range [0,s-1]. m Initial size of the array for a given hash code. i Incremental size of the array for a given hash code. If null value, the size is set to the half of the initial size.
|
virtual |
Destruct the hash container.
Member Function Documentation
size_t GetNb | ( | void | ) | const |
Get the number of elements in the container.
Get a cursor over the hash table.
- Returns
- a R::RCursor.
const cHash* operator[] | ( | size_t | hash | ) | const |
Get a pointer to the elements of a given hash code (Only read).
- Parameters
-
hash Hash code of the elements to get.
- Returns
- the pointer or 0 if the index is outside the scope of the container.
cHash* operator[] | ( | size_t | hash | ) |
Get a pointer to the elements of a given hash code (Read/Write).
- Parameters
-
hash Hash code of the element to get.
- Returns
- the pointer or 0 if the index is outside the scope of the container.
void Clear | ( | void | ) |
Clear the container.
size_t GetIndex | ( | const TUse & | tag, |
size_t & | hash, | ||
bool & | find | ||
) | const |
This function returns the index of an element represented by tag in an array corresponding to a particular hash code.
- Template Parameters
-
TUse The type of tag, the container uses the Compare(TUse &) member function of the elements.
- Parameters
-
tag The tag used. hash Hash code of the tag (set by the method) find If the element represented by tag exist, find is set to true (set by the method).
- Returns
- index of the element if it exists or the index where is has to inserted.
bool IsIn | ( | const TUse & | tag, |
bool | sortkey = true |
||
) | const |
Look if a certain element is in the container.
- Template Parameters
-
TUse The type of tag, the container uses the Compare(TUse &) member function of the elements.
- Parameters
-
tag The tag used. sortkey The tag represents the sorting key. The default value depends if the container is ordered (true) or not (false).
- Returns
- true if the element is in the container.
C* GetPtr | ( | const TUse & | tag, |
bool | sortkey = true |
||
) | const |
Get a pointer to a certain element in the container.
- Template Parameters
-
TUse The type of tag, the container uses the Compare(TUse &) member function of the elements.
- Parameters
-
tag The tag used. sortkey The tag represents the sorting key. The default value depends if the container is ordered (true) or not (false).
- Returns
- the pointer or 0 if the element is not in the container.
C* GetInsertPtr | ( | const TUse & | tag, |
bool | sortkey = true |
||
) |
Get a pointer to a certain element in the container. If the element doesn't exist, the container creates it by using the constructor with TUse as parameter.
- Template Parameters
-
TUse The type of tag, the container uses the Compare(TUse &) member function of the elements.
- Parameters
-
tag The tag used. sortkey The tag represents the sorting key. The default value depends if the container is ordered (true) or not (false).
- Returns
- a pointer to the element of the container.
void InsertPtr | ( | C * | ins, |
bool | del = false |
||
) |
Insert an element in the container. If the corresponding index is already used, the previously inserted element is removed from the container (and destroy if the container is responsible for the allocation).
- Parameters
-
ins A pointer to the element to insert. del Specify if a similar existing element must be deleted or shifted.
void InsertPtrAt | ( | C * | ins, |
size_t | hash, | ||
size_t | idx, | ||
bool | del = false |
||
) |
Insert an element in the container at a given index of a given hash code. If the corresponding index is already used, the previously inserted element is removed from the container (and destroy if the container is responsible for the allocation).
This method should be used very carefully (in general with the GetIndex method) because the container can then disfunction.
- Parameters
-
ins A pointer to the element to insert. hash Hash code of the element to insert. index Index of the element to insert. del Specify if a similar existing element must be deleted or shifted.
void DeletePtr | ( | const TUse & | tag, |
bool | sortkey = true , |
||
bool | del = bAlloc |
||
) |
Delete an element from the container.
- Template Parameters
-
TUse The type of tag, the container uses the Compare(TUse &) member function of the elements.
- Parameters
-
tag The tag used. sortkey The tag represents the sorting key. The default value depends if the container is ordered (true) or not (false). del Specify if the object must deleted or not. By default, the element is destruct if the container is responsible of the deallocation.
Field Documentation
|
private |
This container represents the hash table of the elements.