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