What is the difference between C++ Map and Multimap
-
The multimap stores pairs of (key,value) where both key and value can appear several times
-
The map > will only store each value once for a specific key. To do that, it will have to be able to compare the values, not just the keys
-
A std::map is an associative container, that allows you to have a unique key associated with your type value
Example of Map in C++
<![CDATA[
#include <iostream>
#include <map>
using namespace std;
void mapFunction()
{
// how to declare map
std::map<std::string, int> myMap;
// how to insert into map
myMap.insert(std::pair<string,int>("key1", 39));
myMap.insert(std::pair<string,int>("key2", 10));
// how to search in a map
auto it = myMap.find("key1");
if (it != myMap.end())
std::cout<<"value for "<<it->first<<" is "<<it->second<<std::endl;
else
std::cout << "value not found" << std::endl;
}
int main()
{
mapFunction();
return 0;
}
]]>
Output
-
A std::multimap is equal to a std::map,
but your keys are not unique anymore. Therefore you can find a range of items instead of just find one unique item.
Example of Multimap in C++
<![CDATA[#include <iostream>
#include <map>
using namespace std;
void mapFunction()
{
// how to declare map
std::multimap<std::string, string> address;
// how to insert into multimap
// one person with two adresses
address.insert(std::pair<string,string>("Person1", "Chicago, IL, USA"));
address.insert(std::pair<string,string>("Person1", "Richmond, VA, USA"));
address.insert(std::pair<string,string>("Person2", "West Des Moines, IA, USA"));
// how to search in a multimapmap
auto it = address.find("Person1");
int count = address.count("Person1");
for(int i = 0; i< count; i++)
{
std::cout<<"Address of "<<it->first<<" is "<<it->second<<std::endl;
++it;
}
}
int main()
{
mapFunction();
return 0;
}
]]>
Output
- The std::set is like an std::map, but it is not storing a key associated to a value. It stores only the key type, and assures you that it is unique within the set.
- You also have the std::multiset, that follows the same pattern.
- All these containers provide an O(log(n)) access with their find / equal_range
- Because map containers do not allow for duplicate key values, the insertion operation checks for each element inserted whether another element exists already in the container with the same key value, if so, the element is not inserted and its mapped value is not changed in any way.
- With 1 TB of input, I would use neither. Most likely, you don't have enough RAM. Use some on disk data structure like B-tree.
[Project using Map & Multimap with Threads]
