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 access timeundordered_set
uses Hash Table with 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 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