Lesson 5

Greetings, aspiring coders! Today, we're going to delve deep into the complexities of data structures, specifically the ** std::set** from the C++ Standard Template Library (STL), and explore how to handle queries efficiently. This is a common problem, often encountered in numerous data science and algorithmic problems. So let's gear up to unravel the mysteries of

`std::set`

operations and get our hands dirty with some interactive problem-solving!Before delving into the task, let's understand what a `std::set`

is and why we would use it. `std::set`

is a data structure in the C++ STL that stores unique elements while maintaining sorted order.

Advantages of using `std::set`

:

- Extracting minimum (using
`*set.begin()`

) or maximum (using`*(--set.end())`

) values will be a constant time operation, i.e., $O(1)$ as they are always at the start or end of the set. - Achieving sorted order after every insertion or deletion happens automatically with
`std::set`

, and the operations have a logarithmic time complexity $O(\log N)$.

Understanding these operations can help us utilize `std::set`

efficiently for our problem.

The `std::set`

data structure includes useful functions called `std::lower_bound`

and `std::upper_bound`

.

The `std::lower_bound`

function finds the first element in a sorted range that is not less than a given value. If the element already exists in the set, the iterator points to the element itself.

For example:
If we have a `std::set`

as `{1, 2, 4, 6, 8}`

, `set.lower_bound(4)`

will return an iterator pointing to 4, as 4 exists in the set.

Similarly, the `std::upper_bound`

function finds the first element in a sorted range that is greater than a given value.

Here is an example of how you would use `std::lower_bound`

and `std::upper_bound`

on a `std::set`

:

C++`1#include <iostream> 2#include <set> 3 4int main() { 5 std::set<int> sorted_set = {1, 2, 4, 6, 8}; 6 auto it1 = sorted_set.lower_bound(4); 7 auto it2 = sorted_set.upper_bound(4); 8 9 std::cout << *it1 << " " << (it2 != sorted_set.end() ? std::to_string(*it2) : "end") << std::endl; // Output: 4 6 10 return 0; 11}`

We are tasked with designing a C++ function named `process_queries()`

, that can process a series of distinct requests or queries efficiently. The queries comprise a list of two integers — type of operation and the operand.

There are three types of operations we'll handle:

- Adding an integer to the set (operation type 0)
- Removing an integer from the set (operation type 1). Whenever this operation is invoked, we can guarantee that the integer exists in the set.
- Finding the smallest integer that is greater than or equal to a given value (operation type 2).

The function should return the current size of the set when the operation type is 0 or 1, and the smallest possible integer when the operation type is 2. If such an integer does not exist, the function should return `-1`

.

Given a list of queries:

C++`1std::vector<std::pair<int, int>> queries = { 2 {0, 10}, 3 {2, 10}, 4 {0, 20}, 5 {1, 10}, 6 {2, 10} 7};`

The function should return: `[1, 10, 2, 1, 20]`

To start, we'll initialize our `std::set`

from the C++ STL. We'll also create an empty vector labeled `results`

to store the outputs for each request.

C++`1#include <iostream> 2#include <set> 3#include <vector> 4 5std::vector<int> process_queries(const std::vector<std::pair<int, int>>& queries) { 6 std::set<int> sorted_set; 7 std::vector<int> results;`

Next, we utilize a `for`

loop to traverse through all the queries. For an operation type of 0 or 1, we either add or remove the provided value from our set. Subsequently, we append the size of the current set to `results`

.

C++`1#include <iostream> 2#include <set> 3#include <vector> 4 5std::vector<int> process_queries(const std::vector<std::pair<int, int>>& queries) { 6 std::set<int> sorted_set; 7 std::vector<int> results; 8 9 for (const auto& query : queries) { 10 int operation = query.first; 11 int value = query.second; 12 13 if (operation == 0) { 14 sorted_set.insert(value); 15 } else if (operation == 1) { 16 sorted_set.erase(value); 17 } 18 19 results.push_back(sorted_set.size()); 20 } 21 return results; 22}`

Lastly, when the operation type is 2, we need to find the minimum bound, i.e., the smallest value greater than or equal to our provided value in the set. We perform this using the `std::set::lower_bound`

operation. If such a value does not exist, we append `-1`

to `results`

.

C++`1#include <iostream> 2#include <set> 3#include <vector> 4 5std::vector<int> process_queries(const std::vector<std::pair<int, int>>& queries) { 6 std::set<int> sorted_set; 7 std::vector<int> results; 8 9 for (const auto& query : queries) { 10 int operation = query.first; 11 int value = query.second; 12 13 if (operation == 0) { 14 sorted_set.insert(value); 15 results.push_back(sorted_set.size()); 16 } else if (operation == 1) { 17 sorted_set.erase(value); 18 results.push_back(sorted_set.size()); 19 } else if (operation == 2) { 20 auto it = sorted_set.lower_bound(value); 21 if (it != sorted_set.end()) { 22 results.push_back(*it); 23 } else { 24 results.push_back(-1); 25 } 26 } 27 } 28 return results; 29} 30 31int main() { 32 std::vector<std::pair<int, int>> queries = { 33 {0, 10}, 34 {2, 10}, 35 {0, 20}, 36 {1, 10}, 37 {2, 10} 38 }; 39 40 std::vector<int> result = process_queries(queries); 41 for (int res : result) { 42 std::cout << res << " "; 43 } // Output: 1 10 2 1 20 44 return 0; 45}`

Well done! You've successfully navigated the complexities of `std::set`

operations and developed an understanding of how to handle various types of queries efficiently using C++. Resolving the problem involved incorporating C++ STL data structures, conditional statements, and understanding binary search within a sorted set.

The next step in your learning journey involves tackling similar challenges on your own using the concepts that you've just learned. Be sure to review this lesson as needed, and always remember: practice and apply these concepts. Happy coding!