Library containing an implementation for a bidirectional map using C++ 11 standard.
Table of contents :
This library required at least C++ 11 standard
Below, list of required dependencies:
| Dependencies | VCPKG package | Comments |
|---|---|---|
| Google Tests | gtest |
Only needed to run unit-tests |
Dependency manager VCPKG is not mandatory, this is only a note to be able to list needed packages
This library can be use as an embedded library in a subdirectory of your project (like a git submodule for example) :
- In the root CMakeLists, add instructions:
add_subdirectory(Bimap) # Or if library is put in a folder "dependencies" : add_subdirectory(dependencies/Bimap)- In the application/library CMakeLists, add instructions:
# Link needed libraries
target_link_libraries(${PROJECT_NAME} PRIVATE bimap)This library can also be used as a single header-only library by directly use file: lib/bimap.h
Class cmap::Bimap<KeyType, ValueType> implements an interface similar to std::map where you can make a reverse lookup. Every key has only one value and every value corresponds to exactly one key.
Usage example:
#include "bimap.h"
#include <iostream>
void printBimap(const std::string &comment, const cmap::Bimap<int, std::string> &bimap)
{
std::cout << comment << ": ";
for(auto it = bimap.cbegin(); it != bimap.cend(); ++it){
std::cout << "[" << it->first << "] = " << it->second << "; ";
}
std::cout << std::endl;
}
int main()
{
/* Create a map of three (int, string) pairs */
cmap::Bimap<int, std::string> mapNbsToStrs =
{
{1, "ONE"},
{2, "TWO"},
{3, "THREE"}
};
printBimap("1) Initial map", mapNbsToStrs);
/* Search items */
std::cout << "2a) Search by key [2]: " << mapNbsToStrs.getValue(2) << std::endl;
std::cout << "2b) Search by value [\"TWO\"]: " << mapNbsToStrs.getKey("TWO") << std::endl;
/* Add item */
mapNbsToStrs.insert(4, "FOUR");
printBimap("3) Add item", mapNbsToStrs);
/* Remove item */
mapNbsToStrs.erase(3);
printBimap("4) Remove item", mapNbsToStrs);
/* Clear map */
mapNbsToStrs.clear();
std::cout << std::boolalpha << "5) Map is empty: " << mapNbsToStrs.empty() << std::endl;
return 0;
}Will output:
1) Initial map: [1] = ONE; [2] = TWO; [3] = THREE;
2a) Search by key [2]: TWO
2b) Search by value ["TWO"]: 2
3) Add item: [1] = ONE; [2] = TWO; [3] = THREE; [4] = FOUR;
4) Remove item: [1] = ONE; [2] = TWO; [4] = FOUR;
5) Map is empty: trueImplementation of this bimap is pretty simple: we use two std::map. For each entries added to <key, value> map, we also insert item in the second map <value, key>.
This allow to reduce complexity when searching by keys, complexity decrease from O(n) to O(log(n)).
This comes with a cost: memory usage is doubled, so use this class only when you really need it.
If you need to reduce search complexity and don't need an ordered map, you can use std::unordered_map instead (which will decrease search complexity to O(1)).
Simply replace those aliases definitions inside Bimap class:
using _ContainerKey = std::map<TypeKey, TypeValue>;
using _ContainerValue = std::map<TypeValue, TypeKey>;If your project already have a dependency to Boost libraries, it will be beter to use class Boost.Bimap instead of this class.
All methods has been documented with Doxygen utility, documentation can be generated by using:
# Run documentation generation
doxygen ./Doxyfile
# Under Windows OS, maybe doxygen is not added to the $PATH
"C:\Program Files\doxygen\bin\doxygen.exe" ./DoxyfileNote: You can also load the Doxyfile into Doxywizard (Doxygen GUI) and run generation.
This library is licensed under MIT license.