Introduction to Sets & Maps

C++

The operations on a C++ set include:

• insert, which adds an element to the set if not already present.
• erase, which deletes an element if it exists.
• count, which returns 1 if the set contains the element and 0 if it doesn't.

set<int> s;
s.insert(1); // [1]
s.insert(4); // [1, 4]
s.insert(2); // [1, 2, 4]
s.insert(1); // [1, 2, 4]
// the add method did nothing because 1 was already in the set
cout << s.count(1) << endl; // 1
s.erase(1); // [2, 4]
cout << s.count(5) << endl; // 0
s.erase(0); // [2, 4]

Java

The operations on a TreeSet are add, which adds an element to the set if not already present, remove, which deletes an element if it exists, and contains, which checks whether the set contains that element.

Set<Integer> set = new TreeSet<Integer>();
set.add(1); // [1]
set.add(4); // [1, 4]
set.add(2); // [1, 2, 4]
set.add(1); // [1, 2, 4]
// the add method did nothing because 1 was already in the set
System.out.println(set.contains(1)); // true
set.remove(1); // [2, 4]
System.out.println(set.contains(5)); // false
set.remove(0); // [2, 4]

Python

The built in python unsorted set supports:

• add(): Adds element to set
• remove(): Removes element from set
• x in set: Checks if element x is in the set

set = set()
set.add(1) # [1]
set.add(4) # [1, 4]
set.add(2) # [1, 4, 2]
set.add(1) # [1, 4, 2]
# the add method did nothing because 1 was already in the set
print(1 in set) # True
set.remove(1) # [4, 2]
print(5 in set) # False
set.remove(0); # [4, 2]

C++

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;
    cin >> n;

    set<int> distinctNumbers;

Java

// Source: Daniel

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class DistinctNumbers {

Python

n = int(input())
nums = [int(x) for x in input().split()]
distinctNumbers = set(nums)
print(len(distinctNumbers))

C++

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;
    cin >> n;

    int A[n];

Java

import java.io.*;
import java.util.*;

public class DistinctNumbers {

   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      int[] arr = new int[n];

Python

n = int(input())
arr = [int(x) for x in input().split()]
arr = sorted(arr)

ans = 1
for i in range(n - 1):
    if arr[i] != arr[i + 1]:
        ans += 1

print(ans)

C++

In a C++ map m:

• the m[key] = value operator assigns a value to a key and places the key and value pair into the map. The operator m[key] returns the value associated with the key. If the key is not present in the map, then m[key] is set to 0.
• The count(key) method returns the number of times the key is in the map (which is either one or zero), and therefore checks whether a key exists in the map.
• Lastly, erase(key) removes the map entry associated with the specified key.

map<int, int> m;
m[1] = 5; // [(1, 5)]
m[3] = 14; // [(1, 5); (3, 14)]
m[2] = 7; // [(1, 5); (2, 7); (3, 14)]
m[0] = -1; // [(0, -1); (1, 5); (2, 7); (3, 14)]
m.erase(2); // [(0, -1); (1, 5); (3, 14)]
cout << m[1] << '\n'; // 5
cout << m.count(7) << '\n' ; // 0
cout << m.count(1) << '\n' ; // 1

Java

In a TreeMap, the put(key, value) method assigns a value to a key and places the key and value pair into the map. The get(key) method returns the value associated with the key. The containsKey(key) method checks whether a key exists in the map. Lastly, remove(key) removes the map entry associated with the specified key. All of these operations are $O(1)$, but again, due to the hashing, this has a high constant factor.

Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(1, 5); // [(1, 5)]
map.put(3, 14); // [(1, 5); (3, 14)]
map.put(2, 7); // [(1, 5); (2, 7); (3, 14)]
map.remove(2); // [(1, 5); (3, 14)]
System.out.println(map.get(1)); // 5
System.out.println(map.containsKey(7)); // false
System.out.println(map.containsKey(1)); // true

Python

Colloquially, maps are referred to as dicts in python. They act as hash maps, so they actually have $O(1)$ insertion, deletion, and searches.

dict = {}
dict[1] = 5 # [(1, 5)]
dict[3] = 14 # [(1, 5); (3, 14)]
dict[2] = 7 # [(1, 5); (2, 7); (3, 14)]
del dict[2] # [(1, 5); (3, 14)]
print(dict[1]) # 5
print(7 in dict.keys()) # False
print(1 in dict.keys()) # True

C++

To iterate over maps, you can use a for loop.

for (pair<int,int> x : m) {
    cout << x.first << " " << x.second << '\n';
}
for (auto x : m) {
    cout << x.first << " " << x.second << '\n';
}

/* both output the following:
0 -1
1 5

The map stores pairs in the form {key, value}. The auto keyword suffices to iterate over any type of pair. You can use these pairs normally, as introduced in this module.

Additionally, you can pass by reference when iterating over a map, like this:

for (auto& x : m) {
    x.second = 3;
}
for (pair<int,int> x : m) {
    cout << x.first << " " << x.second << '\n';
}

/*
0 3
1 3

This allows you to modify the values of the pairs stored in the map.

Java

To iterate over maps, you can use a for loop over the keys.

for (int k : m.keySet()){
    System.out.println(k + " " + m.get(k));
}

Python

To iterate over dicts, you can use a for loop over the keys of the dict.

for key in dict.keys():
    print(f'{key} {dict[key]}')