map and set with real complexity numbers

Ordered trees versus hash tables, and how to pick the right one under a time limit.

12 min read · Lesson 4 of 6 · Pro

Two problems, two containers

set answers "have I seen this before?" It stores unique values with no duplicates.

map answers "what value goes with this key?" It stores key-value pairs, keys unique.

Both come in two flavours, and choosing wrongly is a common reason a correct solution times out.

set: unique values

C++

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);              // duplicate, ignored

    cout << s.size() << "\n";  // 3

    for (int x : s) cout << x << " ";
    cout << "\n";              // 10 30 40, always sorted

The rest of this lesson is Pro

The free lessons of C++ and STL Essentials finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.