Hashing ArraysThe data type h_array can be used to store objects of an arbitrary type I together with an associated key of a hashed type K , i.e., K has an eqality operator and a hash function.ExampleThe following program reads a sequence of strings and counts the multiplicity of each string in anh_array. To use the h_array
with keys of type string a hash function needs to be defined. It
returns the first character of the string or 0 if the string is empty.
#include <LEDA/core/string.h>
#include <LEDA/core/h_array.h>
using namespace leda;
namespace leda {
int Hash(const string& x)
{
return (x.length()> 0)?x[0]:0;
}
};
int main()
{
h_array<string,int> N(0);
//objects of type int, keys of type string default value is 0
string s;
do {
std::cout << "Input string ('stop' terminates loop): ";std::cin >> s;
N[s]++;
} while (s!=string("stop"));
forall_defined(s,N) std::cout << s << " " << N[s] << std::endl;
return 0;
}
Strengths
Disadvantages
TipsUseh_array if you have an appropriate hash function and the
interface of is sufficient for your purposes. Otherwise consider using one
of the related data types. |
See also:Data types with key of linearly ordered type: Data type with key of type pointer, item, or int: Maps Manual Entries: |