Abstract Data Type

Set (Programming)

A set is an abstract data type that maintains a collection of elements.

• A Map is pretty similar, but it stores key-value pairs instead of just values.
• See Set Theory for mathematical definition.

C++ Implementation

C++ standard library contains two set implementations:

• set which is ordered based on Self-Balancing Binary Search Tree with $O(\log n)$ access time
• undordered_set uses Hash Table with $O(1)$ time on average

IMPORTANT: All elements in set are distinct and have a count of either 0 or 1. If you want multiple counts, use a multiset. → Multiset

set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << "\n"; // 1
cout << s.count(4) << "\n"; // 0
s.erase(3);
s.insert(4);
cout << s.count(3) << "\n"; // 0
cout << s.count(4) << "\n"; // 1

A set can be used mostly like a vector, but it is not possible to access the elements using the [] notation.

set s = {2,5,6,8}; 
cout << s.size() << "\n"; // 4 
for (auto x : s) { 
	cout << x << "\n"; 
}

Using sets for search: Since a set is a tree, you can do search in $O(\log n)$ time. I actually needed this to solve: https://dmoj.ca/problem/ccc15s3. I passed 29/30 cases except one because of TLE…

you need to do something like

set<int>::iterator it;
 
s.insert(1);
s.insert(2);
s.insert(4);
 
/*PAY ATTENTION HERE: 
- For lower bound, If it finds, it points to that element, but if not, it points to the closest element above.
- However, for upper bound, it ALWAYS points to the next closest element
 
In general, always use lower_bound()
*/
 
it = s.lower_bound(3); // Points to 2
it = s.upper_bound(3); // ALWAYS Points to 4
it = s.upper_bound(2); // Points to 4
 
 
 
// To print the value, you need to dereference it
cout   << *it << endl;

Multiset

multiset s; 
s.insert(5); 
s.insert(5); 
s.insert(5); 
cout << s.count(5) << "\n"; // 3 

The function erase removes all instances of an element from a multiset:

s.erase(5); 
cout << s.count(5) << "\n"; // 0 

Often, only one instance should be removed, which can be done as follows:

s.erase(s.find(5)); 
cout << s.count(5) << "\n"; // 2

Python

Unordered Set

set_a = set()
set_a.add(2)
set_a.add(5)
print(3 in set_a) # False
print(2 in set_a) # True
 
set_a.remove(2)
print(2 in set_a) # False

Ordered Set (using SortedSet)

from sortedcontainers import SortedSet
 
# Create a SortedSet
sorted_set = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])
sorted_set.add(5)
 
print("Iterating over the SortedSet:")
for item in sorted_set:
    print(item)
 
# Check if a specific value is in the SortedSet
value_to_check = 5
if value_to_check in sorted_set:
    print(f"\nValue {value_to_check} is in the SortedSet.")
else:
    print(f"\nValue {value_to_check} is not in the SortedSet.")