More Operations on Sorted Sets
Authors: Darren Yao, Benjamin Qi, Andrew Wang
Contributors: Aadit Ambadkar, Jeffrey Hu
Finding the next element smaller or larger than a specified key in a set, and using iterators with sets.
Resources | ||||
---|---|---|---|---|
IUSACO | module is based off this | |||
CP2 | see decription of BSTs and heaps |
In sets and maps where keys (or elements) are stored in sorted order, accessing
or removing the next key higher or lower than some input key k
is supported.
Keep in mind that insertion and deletion will take time for sorted sets, which is more than the average insertion and deletion for unordered sets, but less than the worst case insertion and deletion for unordered sets.
Using Iterators
In Bronze, we avoided discussion of any set operations involving iterators.
Resources | ||||
---|---|---|---|---|
CPH |
Sorted Sets
The sorted std::set
also supports:
lower_bound
: returns an iterator to the least element greater than or equal to some elementk
.upper_bound
: returns an iterator to the least element strictly greater than some elementk
.
set<int> s;s.insert(1); // [1]s.insert(14); // [1, 14]s.insert(9); // [1, 9, 14]s.insert(2); // [1, 2, 9, 14]cout << *s.upper_bound(7) << '\n'; // 9cout << *s.upper_bound(9) << '\n'; // 14cout << *s.lower_bound(5) << '\n'; // 9cout << *s.lower_bound(9) << '\n'; // 9cout << *s.begin() << '\n'; // 1auto it = s.end();cout << *(--it) << '\n'; // 14s.erase(s.upper_bound(6)); // [1, 2, 14]
Warning!
Suppose that we replace s.upper_bound(7)
with
upper_bound(begin(s),end(s),7)
, which was the syntax that we used for vectors
in the prerequisite module. This will still output the expected results, but its
time complexity is linear in the size of the set s
rather than logarithmic, so
make sure to avoid it!
One limitation of sorted sets is that we can't efficiently access the largest element in the set, or find the number of elements in the set greater than some arbitrary . In C++, these operations can be handled using a data structure called an order statistic tree.
Sorted Maps
The ordered map
also allows:
lower_bound
: returns the iterator pointing to the lowest entry not less than the specified keyupper_bound
: returns the iterator pointing to the lowest entry strictly greater than the specified key respectively.
map<int, int> m;m[3] = 5; // [(3, 5)]m[11] = 4; // [(3, 5); (11, 4)]m[10] = 491; // [(3, 5); (10, 491); (11, 4)]cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second<< '\n'; // 10 491cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second<< '\n'; // 11 4m.erase(11); // [(3, 5); (10, 491)]if (m.upper_bound(10) == m.end()) {cout << "end" << endl; // Prints end}
Multisets
A multiset is a sorted set that allows multiple copies of the same element.
In addition to all of the regular set operations,
- the
count()
method returns the number of times an element is present in the multiset. However, this method takes time linear in the number of matches so you shouldn't use it in a contest. - To remove a value once, use
ms.erase(ms.find(val))
. - To remove all occurrences of a value, use
ms.erase(val)
.
Warning!
Using ms.erase(val)
erases all instances of val
from the multiset. To remove one instance of val
, use ms.erase(ms.find(val))
!
multiset<int> ms;ms.insert(1); // [1]ms.insert(14); // [1, 14]ms.insert(9); // [1, 9, 14]ms.insert(2); // [1, 2, 9, 14]ms.insert(9); // [1, 2, 9, 9, 14]ms.insert(9); // [1, 2, 9, 9, 9, 14]cout << ms.count(4) << '\n'; // 0cout << ms.count(9) << '\n'; // 3cout << ms.count(14) << '\n'; // 1ms.erase(ms.find(9));cout << ms.count(9) << '\n'; // 2ms.erase(9);cout << ms.count(9) << '\n'; // 0
Priority Queues
Warning!
Priority queues are not implemented in the same way as sets and multisets, but they are included in this section because the operations that they perform can also be performed with sets.
Resources | ||||
---|---|---|---|---|
CSA |
A priority queue (or heap) supports the following operations: insertion of elements, deletion of the element considered highest priority, and retrieval of the highest priority element, all in time according to the number of elements in the priority queue. Priority queues are simpler and faster than sets, so you should use them instead whenever possible.
C++
priority_queue<int> pq;pq.push(7); // [7]pq.push(2); // [2, 7]pq.push(1); // [1, 2, 7]pq.push(5); // [1, 2, 5, 7]cout << pq.top() << endl; // 7pq.pop(); // [1, 2, 5]pq.pop(); // [1, 2]pq.push(6); // [1, 2, 6]
Introductory Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsSorted Set | |||
CF | Easy | Show TagsSorted Set | |||
CSES | Normal | Show TagsSorted Set | |||
CSES | Normal | Show TagsSorted Set |
Harder Example - Bit Inversions
Warning!
Problems marked as "Hard" or beyond in this module would likely be too difficult to appear on a USACO Silver contest.
Focus Problem – try your best to solve this problem before continuing!
View Internal SolutionSolution
We'll use iterators extensively.
Let the bit string be . In the set dif
, we store
all indices such that (including and ). If the
elements of dif
are , then the longest length is
equal to
We can store each of these differences in a multiset ret
; after each
inversion, we'll need to output the maximum element of ret
.
Inverting a bit at a 0-indexed position x
corresponds to inserting x
into
dif
if it not currently present or removing x
if it is, and then doing the
same with x+1
. Whenever we insert or remove an element of dif
, we should
update ret
accordingly.
#include <bits/stdc++.h>using namespace std;#define sz(x) (x).size()string s;int m;set<int> dif;multiset<int> ret;
Note that multiset has a high constant factor, so replacing ret
with a
priority queue and an array that stores the number of times each integer occurs
in the priority queue reduces the runtime by a factor of 2.
#include <bits/stdc++.h>using namespace std;#define sz(x) (int)(x).size()string s;int m;set<int> dif;priority_queue<int> ret;int cnt[200005];
Harder Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Silver | Normal | Show TagsSorted Set | |||
Silver | Normal | Show TagsSorted Set | |||
CF | Normal | Show TagsGreedy, Sorted Set, Sorting | |||
CF | Normal | Show TagsGreedy, Multiset, Sorting | |||
CF | Normal | Show TagsCoordinate Compression, Prefix Sums, Sorted Set, Sorting | |||
Gold | Hard | Show TagsLinked List, Sorted Set | |||
AC | Hard | Show TagsGreedy, Sorted Set | |||
CF | Hard | Show TagsBinary Search, Sorted Set | |||
CF | Very Hard | Show TagsSorted Set | |||
CF | Insane | Show TagsSorted Set |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!