Sets

Time Complexity			Space Complexity
Access	Search	Insert / Delete	O(n)
N/A	O(1)	O(1)

Sets are like arrays (this page: Preferred Arrays), except they can contain no multiple objects. This is useful if you want to get information on unique data.

For instance, say we wanted to get the number of unique letters in the word "mississippi". There are a number of ways to do that - but the simplest way would be to iterate over the word and add every letter to a set, resulting in a set with just 'm', 'i', 's', and 'p'. Get the size of the set, and you’ve solved the problem in very few lines.

Sets are often used in combination with other data structures in complicated problems, just to take advantage of this trait.

C++

C#

Java

JavaScript

JavaScript ES6

Python

Swift

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

int main() {
    // Declaration
    unordered_set<int> numSet;

    // Add values
    numSet.insert(1);
    numSet.insert(2);
    numSet.insert(2); //ignored
    numSet.insert(3);
    numSet.insert(4);

    // Check for value
    cout << boolalpha;
    cout << "Contains 4: " << (numSet.find(4) != numSet.end()) << endl;

    // Get size
    cout << "size: " << (numSet.size()) << endl;

    // Remove Value
    numSet.erase(4);
    cout << "Removed 4" << endl;
    cout << "Contains 4: " << (numSet.find(4) != numSet.end()) << endl;

    // Accessing all values (no guarunteed order)
    unordered_set<int>::iterator it;
    for (it = numSet.begin(); it != numSet.end(); it++){
      cout << *it << endl;
    }

    // Check for subset
    unordered_set<int> superSet;
    for(int i = 1; i <= 10; i++)
      superSet.insert(i);
    bool subset = true;
    for(it = numSet.begin(); it != numSet.end(); it++){
      if(superSet.find(*it) == superSet.end()){
        subset = false;
        break;
      }
    }
    if(subset)
      cout << "Set is a subset of 1-10" << endl;
    else
      cout << "Set is not a subset of 1-10" << endl;
}

using System.Collections.Generic;
class Program {
  static void Main(string[] args) {
    // Declaration
    HashSet<int> set = new HashSet<int>();

    // Add values
    set.Add(1);
    set.Add(2);
    set.Add(2); // ignored
    set.Add(3);
    set.Add(4);

    // Check for value
    System.Console.WriteLine("Contains 4: " + set.Contains(4));

    // Get size
    System.Console.WriteLine("size: " + set.Count);

    // Remove value
    set.Remove(4);
    System.Console.WriteLine("Removed 4");
    System.Console.WriteLine("Contains 4: " + set.Contains(4));

    // Accessing all values (no guarunteed order)
    foreach(int number in set)
      System.Console.WriteLine(number);

    // Check for subset
    HashSet<int> superSet = new HashSet<int>();
    for(int i = 1; i <= 10; i++)
      superSet.Add(i);

    System.Console.WriteLine("Set is a subset of 1-10: " + set.IsSubsetOf(superSet));
  }
}

import java.util.*;
public class sets {
  public static void main(String[] args) {
    // Declaration
    Set<Integer> set = new HashSet<Integer>();

    // Add values
    set.add(1);
    set.add(2);
    set.add(2); // ignored
    set.add(3);
    set.add(4);

    // Check for value
    System.out.println("Contains 4: " + set.contains(4));

    // Get size
    System.out.println("size: " + set.size());

    // Remove value
    set.remove(4);
    System.out.println("Removed 4");
    System.out.println("Contains 4: " + set.contains(4));

    // Accessing all values
    for(Integer num : set)
      System.out.println(num);

    // Check for subset
    Set<Integer> superSet = new HashSet<Integer>();
    for(int i = 1; i <= 10; i++){
      superSet.add(i);
    }

    System.out.println("Set is a subset of 1-10: " + superSet.containsAll(set));
  }
}

// Declaration
var set = {};

// Add values
set[1] = true;
set[2] = true;
set[2] = true; // no effect
set[3] = true;
set[4] = true;

// Check for value
console.log("Contains 4: " + (4 in set));

// Get size
console.log("size: " + Object.keys(set).length);

// Remove value
delete set[4];
console.log("Removed 4");
console.log("Contains 4: " + (4 in set));


// Accessing all values
Object.keys(set).forEach( function(key){
    console.log(key);
});

// Check for subset
var superSet = {};
for(var i = 1; i <= 10; i++)
  superSet[i] = true;

function checkSubset(set, superSet){
  Object.keys(set).forEach( function(key){
    if(!(key in superSet))
      return false;
  });
  return true;
}

console.log("set is a subset of superSet: " + checkSubset(set, superSet));

// Declaration
var set = new Set();

// Add values
set.add(1);
set.add(2);
set.add(2); // no effect
set.add(3);
set.add(4);

// Check for value
console.log("Contains 4: " + set.has(4));

// Get size
console.log("size: " + set.size);

// Remove value
set.delete(4);
console.log("Removed 4");
console.log("Contains 4: " + (4 in set));

// Accessing all values
set.forEach( function(value){
    console.log(value);
});

// Check for subset
var superSet = new Set();
for(var i = 1; i <= 10; i++)
  superSet.add(i);

function subSet(set, superSet){
  set.forEach( function(value){
    if(!superSet.has(value))
      return false;
  });
  return true;
}

console.log("set is a subset of superSet: " + subSet(set, superSet));

# Declaration
exampleSet = set()

exampleSet.add(1)
exampleSet.add(2)
exampleSet.add(2) # no effect
exampleSet.add(3)
exampleSet.add(4)

# Check for value
print("Contains 4: " + str(4 in exampleSet))

# Check size
print("size: " + str(len(exampleSet)))

# Remove value
exampleSet.remove(4)
print("Removed 4")
print("Contains 4: " + str(4 in exampleSet))

# Accessing all values
for value in exampleSet:
  print(value)

# Check for subset
superSet = set()
for i in range(1, 10):
  superSet.add(i)

print("set is a subset of superSet: " + str(exampleSet.issubset(superSet)))

// Declaration
var exampleSet = Set<Int>()

// Add values
exampleSet.insert(1)
exampleSet.insert(2)
exampleSet.insert(2) // no effect
exampleSet.insert(3)
exampleSet.insert(4)

// Check for value
print("Contains 4: " + String(exampleSet.contains(4)))

// Get size
print("size: " + String(exampleSet.count))

// Remove value
exampleSet.remove(4)
print("Removed 4")
print("Contains 4: " + String(exampleSet.contains(4)))

// Accessing all values
for value in exampleSet {
  print(value)
}

// Check for subset
var superSet = Set<Int>()
for i in 1...10 {
  superSet.insert(i)
}

print("set is a subset of superSet: " + String(exampleSet.isSubset(of: superSet)))

Notes

C++

C#

Java

JavaScript

JavaScript ES6

Python

Swift

The import statement #include <unordered_set> should be used for sets.

It should be noted that almost any type (including custom types) can be used for the values of a set, but using custom types for the values requires your own hash function, which is a mess in itself. C++ defined types, however, are usually fine.

boolalpha is passed to cout to change 1 and 0 boolean outputs to true and false.

The .find() function results in the dict.end() pointer if there is no value, so that’s why they can be compared with != to check if the value is there.

This uses an “iterator” pointer to iterate over the set, used in the standard library.

The import statement using System.Collections.Generic; should be used.

Sets are referred to as “Hashsets” in C#.

The import statement import java.util.*; should be used.

In Java, Set is the interface and the preferred class is a HashSet, which needs the type of variables it’s holding defined in <> (angle brackets).

A “range-based” for loop is used. This gives you each value in an array / container. It has the syntax

for(typeOfVar yourVar : someContainer)

//do stuff with "yourVar"

JavaScript didn’t have “sets” before ES6. In the case you need to use an old version of JavaScript, you can use Dictionaries that have booleans as values, which are practically the same as sets.

See the page on dictionaries for implementation details: Dictionaries.

There’s also a function here that checks for a subset - it should be self explanatory (return false if there isn’t a value in the superSet, return true otherwise).

This is the syntax introduced in ES6 for proper sets.

There’s also a function here that checks for a subset - it should be self explanatory (return false if there isn’t a value in the superSet, return true otherwise).

Python needs things cast to str to concatenate (join) strings, if you’re wondering about the output statements.

Swift needs things cast to String to concatenate (join) strings, if you’re wondering about the output statements.