Set vs Map : How to choose a right associative container ?

In this article we will discuss how set and map are different and what factors we need to keep in mind while choosing right associative container.

Let’s start from set,

Set :

  • Set is an associative container which we need to store unique elements.
  • It always keeps the elements in sorted order.
  • Internally it maintains a balanced binary search tree of elements. Therefore when we search an element inside the set then it takes only log(n) complexity to search it.

Important Point about set – Once added then cannot change i.e.

Each element added inside the set is const i.e. you cannot modify that element, because if you could, then it would hamper set’s internal data structure i.e. it will lose its internal balanced binary search tree property and results in undefined behavior.

[showads ad=inside_post]

Let’s understand by example,

Create a set to store unique names of Departments and then try to change one,

#include <iostream>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <string>

void example1()
{
	std::set<std::string> setOfDepartments;

	setOfDepartments.insert("First");
	setOfDepartments.insert("Second");
	setOfDepartments.insert("Third");
	std::for_each(setOfDepartments.begin(), setOfDepartments.end(), [](std::string elem){
											std::cout<<(elem)<<" , ";
											});

	// Now Try to change the element

	 std::set<std::string>::iterator it = setOfDepartments.find("Second");
	 if(it != setOfDepartments.end())
	 {
		 std::cout << std::endl<< *it;
		 //*it = "Fourth"; // NOT ALLOWED
	 }

}
int main()
{
	Example1();
	return 0;
}

In above example you cannot change the element through iterator because here our complete element which we have added in SET is a key and you cannot modify any key inside the SET.
But what if want to associate some Value with this key and want to change that associated value at run time. Then we need something other than SET and that’s it MAP.

Map:

  • Map is a associative container that is used to store key-value pair of elements with unique keys.
  • It always keeps the inserted pairs in sorted order based on the key.
  • Internally it maintains a balanced binary search tree to store keys. Therefore when searching key inside the map takes only log(n) complexity.
  • We cannot modify the key of any inserted pair in map.
  • We can modify the value associated with a key in any inserted pair in map.

Let’s understand by example,

Create a map of Departments and No of Employee count. Then search a Department and change its associated no of employee count.

#include <iostream>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <string>

void example2()
{
	// Map of Department and Employee count in that Department
	std::map<std::string, int > mapOfDepEmpCount;

	mapOfDepEmpCount.insert(std::make_pair("First", 0));
	mapOfDepEmpCount.insert(std::make_pair("Second", 0));
	mapOfDepEmpCount.insert(std::make_pair("Third", 0));

	std::map<std::string, int >::iterator it = mapOfDepEmpCount.find("Second");
	 if(it != mapOfDepEmpCount.end())
	 {
		 std::cout << std::endl << "Department = "<< it->first << " :: No. Of Employees = " << it->second << std::endl;
		 // You can change the value associated with the key
		 it->second = 10;
		 //it->first = "sss"; // You cannot chage the key
	 }

	 it = mapOfDepEmpCount.find("Second");
	 if(it != mapOfDepEmpCount.end())
	 {
		 std::cout << std::endl << "Department = "<< it->first << " :: No. Of Employees = " << it->second << std::endl;

	 }

}

int main()
{
	example2();
	return 0;
}

When to choose SET and when MAP?

So, if you want to maintain a data structure of unique keys only without any associated value that plan to modify in future then use set. If you want to modify any element in set then erase it and then insert the new one.
Whereas, use map if you want to maintain a data structure of unique keys and some associated value with each key that you want to change in future.

4 thoughts on “Set vs Map : How to choose a right associative container ?”

  1. Pingback: C++ : Map Tutorial Part 1: Usage Detail with examples – thisPointer.com

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top