Set vs Map containers in C++

This article is to discuss the difference between a set and a map which are both containers in the Standard Template Library in C++.

TLDR

The map container stores unique key-value pairs in a sorted order, while a set container, which is like a specialized version of the map stores unique keys only, where the key is identical to the value it maps to.

Set container

• A set is a sorted associated container of unique elements
• Each element can occur only once, so duplicates are not allowed in sets
• Elements are always stored in sorted order
• Some other versions of sets are:

• unordered_set that doesn't store values in a particular order
• multiset that allows storing of non-unique values

Map container

• A map is also a sorted associated container that contains key-value pairs with unique keys
• Elements in a map are sorted by order of the unique keys
• Two variations of a map are unordered_map and multimap similar to that of sets

Differences

Implementation

• Sets and Maps are usually internally implemented as Red-Black Trees which are balanced binary search trees
• Both sets and maps have a key and value, the key is used to index into the container
• The set::value_type of the set is same as the key for a set
• The map::value_type is a std::pair that of the key and value
• A set can be made to function like a map by creating a set of pairs as, std::set<std::pair<int, int> which is similar to std::map<int, int>, although the map would be preferred as aggregation by keys and sorting would be implemented more efficiently

Operations

• In a set container, alteration of values is not permitted but insertion and deletions are allowed
• In a map container, however, the key type cannot be altered but the value of associated keys can be changed as needed
• For both containers:
  • Insertion takes log(n) (Logarithmic in the size of the container) time complexity
  • Deletion has constant amortized time complexity
  • Lookup is logarithmic in the size of the container

Application

• Set

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> departments;
    departments.insert("CSE");
    departments.insert("ECE");
    departments.insert("EEE");
    // duplicate element is not inserted
    departments.insert("CSE");
    
    std::cout << "Elements in the set are:\n";
    for(std::string ele: departments) {
           std::cout << ele << "\n";
    }
}

• Map

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> grades;
    grades["akhil"] = 100;
    grades["keerthi"] = 89;
    grades["vishal"] =  77;

    // we can modify keerthi's grade
    grades["keerthi"] = 93;

    std::cout << "The students grades are:\n\n";
    for(auto student: grades) {
        std::cout << "key: " << student.first <<
            " value: " << student.second << "\n";
    }
}

When to choose set vs map

• If you are looking for a lookup table to map keys to values, with these keys being unique, then the map is the container of choice
• If the need is for just storing unique keys with no associated values and ordering matters, set is preferred
• If the ordering of the container doesn't matter and the focus is on faster lookup times the unordered versions are proffered as they have faster lookup times (constant time for the average case)

Quiz

Hope you learnt something new through this short article! Here's a small quiz to test your application based knowledge!