Hash tables are structures that allow you to search elements using a key. In my recent publication, I am using the data structure that was named "Voxel Hashing" to test the efficiency of hash table while voxelizing/interpreting full-waveform LiDAR data for 3D polygonal mesh creation [1]. This approach is the one selected to be used on the open source software DASOS [2] since it does not store empty voxels and even though it was not the fastest in the processes of 3D polygonal mesh creation, it is able to find the value of a voxel at constant time O(n) using the Hash function. The C++ implementation of the unordered_multimap is used and this blog post explains how to use it.
Unordered_multimap:
As mentioned before, it is used for quick search and it allows you to save more than one values with the same key, while unordered_map doesn't. How does it work? Simply, for every key there is a bucket where all the values associated with that key are saved.
So, unordered_multimap is in the same header file with unordered_map, so the header file that need to be included is:
#include < unordered_map >
To create a map you need to define the type of the two components of the map. For example:
std::unordered_multimap < unsigned int , std::string > myMap;
if you would like to give initial values in the map you can do it as follow:
// this gives the initial values to the constructor
std::unordered_multimap < unsigned int , std::string > myMap ({{100,"a"},{120,"b"}});
// while the following on initialises the map and then adds the values
std::unordered_multimap < unsigned int , std::string > myMap ={{100,"a"},{120,"b"}};
If you would like to add items you can do it using the command "emplace":
// add more elements myMap.emplace(100,"c"); myMap.emplace(100,"d"); myMap.emplace(200,"e");
You may like to loop through all its elements as follow:
//loop through all its elements
std::cout << "These are all the elements saved into the map:\n";
for (auto& x: myMap)
{
std::cout << "(" << x.first << " , " << x.second << ")\n";
}
And in my opinion the most important feature is to be able to loop through all the elements with the same key. Here is an example of how you may do it:
// print all the elements with Key = 100
unsigned int key = 100;
std::cout << "These are all the elements with key value: " << key << "\n";
auto itsElements = myMap.equal_range(key);
for (auto it = itsElements.first; it != itsElements.second; ++it)
{
std::cout << "(" << it->first << " , " << it->second << ")\n";
}
By the end, another small useful feature is the ability to query the unordered_multimap and get the number of elements that exists with the same key. This is achieved using the command count() as follow:
To sum up here is the entire program, which defines an unordered_multimap with some initial values, adds 3 more elements, prints all the elements inside the map and finally prints all the elements with key 100.
// counts how many entries exist with the same key std::cout << "There are " << myMap.count(key) << " entries with key equal to " << key << "\n";
To sum up here is the entire program, which defines an unordered_multimap with some initial values, adds 3 more elements, prints all the elements inside the map and finally prints all the elements with key 100.
#include < iostream >
#include < unordered_map >
int main(int /*argc*/, char **/*argv*/)
{
// define and initialise map
std::unordered_multimap < unsigned int , std::string > myMap ({{100,"a"},{120,"b"}});
// add more elements
myMap.emplace(100,"c");
myMap.emplace(100,"d");
myMap.emplace(200,"e");
//loop through all its elements
std::cout << "These are all the elements saved into the map:\n";
for (auto& x: myMap)
{
std::cout << "(" << x.first << " , " << x.second << ")\n";
}
// print all the elements with Key = 100
unsigned int key = 100;
std::cout << "These are all the elements with key value: " << key << "\n";
auto itsElements = myMap.equal_range(key);
for (auto it = itsElements.first; it != itsElements.second; ++it)
{
std::cout << "(" << it->first << " , " << it->second << ")\n";
}
// counts how many entries exist with the same key
std::cout << "There are " << myMap.count(key) << " entries with key equal to " << key << "\n";
return 0;
}
And the output of the program is the following:
These are all the elements saved into the map: (200 , e) (100 , d) (100 , c) (100 , a) (120 , b) These are all the elements with key value: 100 (100 , d) (100 , c) (100 , a) There are 3 entries with key equal to 100
References
[1] Miltiadou, M.; Campbell, N.D.F.; Cosker, D.; Grant, M.G. A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation. Remote Sens. 2021, 13, 559. https://doi.org/10.3390/rs13040559
[2] Miltiadou, M., Grant, M. G., Campbell, N. D., Warren, M., Clewley, D., & Hadjimitsis, D. G. (2019, June). Open source software DASOS: Efficient accumulation, analysis, and visualisation of full-waveform lidar. In Seventh International Conference on Remote Sensing and Geoinformation of the Environment (RSCy2019) (Vol. 11174, p. 111741M). International Society for Optics and Photonics.
