All about Pair in Set STL C++ — Part1
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. Elements are stored in sorted order.
The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.
Set is generally slower than unordered_set contianer to access individual elements and it is implemented using BST (Binary Search Tree). It could be Red-Black Tree.
Useful links are
Set in C++ Standard Template Library (STL) — GeeksforGeeks https://cplusplus.com/reference/set/set/
This article will talk about mostly on 3 APIs — find, upper_bound and lower_bound
find() — Searches container for an element equivalent to value and return the iterator. If it is not found, otherwise it returns an iterator to set::end. This iterator can be used to find index as well as to erase the element from the list. In case of pair, it will check all values in pair. If first one matches, it will try to match 2nd one. Tim complexity -
- Time complexity log(n)
Two elements of a set are considered to be equivalent if the container’s comparison object returns false reflexively (i.e., no matter the order in which the elements are passed as arguments).
Example: Find Operation
Sorted pair: (0,0) (0,1) (1,0) (1,1) (1,2) (1,3) (2,7) (4,4) (5,4) (7,2) (8,9)
Found output of (1,1) is (1,1) // Display matching using default comparator
Not found (5,5) // Did not find exact matching pair
Not found (5,6)
Not found (1,4)
Not found (6,6)
Not found (6,7)
Not found (8,10)
Not found (1,12)
Found output of (1,2) is (1,2) // Display matching using default comparator
upper_bound(): Returns an iterator pointing to the first element in the range [first, last) who’s value is upper bound of given ‘val’ or ‘key’.
But, in set of pairs upper_bound for pair (x, y) will return iterator pointing to the position of pair who’s first value is greater than or equals x. Check 2 condition for finding upper bound.
- If first values are same, then it will return an iterator pointing to the position of pair whose 2nd value is greater than y.
- If above-mentioned criteria are not met, it returns an iterator which points to end of the set (next to last pair of set).
Example: Upper Bound
Found upper bound (1,1) is (1,2) // If 1st element match, it checks 2nd high
Found upper bound (5,5) is (7,2)
Found upper bound (5,6) is (7,2)
Found upper bound (4,4) is (5,4)
Found upper bound (1,4) is (2,7)
Found upper bound (6,6) is (7,2)
Found upper bound (6,7) is (7,2)
Not found
Not found
Found upper bound (2,6) is (2,7)
Found upper bound (7,9) is (8,9)
Not found
lower_bound(): Returns the element in range [first, last) which is equivalent to key passed in the parameter. If the key is not present in the ordered set, then the function should return the element which is greater than given ‘val’ or ‘key’.
But, in set of pairs lower_bound for pair (x, y) will return iterator pointing to the position of pair who's first value is equals to or greater than x. Check 2 condition for finding lower bound.
- If first values are same, then it will return an iterator pointing to the position of pair whose 2nd value is equal to or greater than y.
- If above-mentioned criteria are not met, it returns an iterator which points to end of the set (next to last pair of set).
Example: Lower Bound
Found lower bound (1,1) is (1,1) // Return exact match if found.
Found lower bound (5,5) is (7,2)
Found lower bound (5,6) is (7,2)
Found lower bound (4,4) is (4,4)
Found lower bound (1,4) is (2,7)
Found lower bound (6,6) is (7,2)
Found lower bound (6,7) is (7,2)
Not found
Not found
Found lower bound (2,6) is (2,7)
Found lower bound (7,9) is (8,9)
Not found
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Complete Code
#include<iostream>
#include<set>
using namespace std;
set<pair<int, int>> PairList = { {1, 0}, {1, 1}, {0, 0}, {0,1}, {1,2},
{1, 3}, {1, 1}, {5, 4}, {4, 4}, {7, 2}, {2, 7}, {8, 9} };
int find_key(pair<int, int> pair_val) {
auto it = PairList.find(pair_val);
if (it != PairList.end()) {
cout << “Found output of “ << ‘(‘ << pair_val.first << ‘,’ << pair_val.second
<<’)’ << “ is “;
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << endl;
return distance(PairList.begin(), it);
}
else {
cout << “Not found “ << ‘(‘ << pair_val.first << ‘,’ << pair_val.second
<< ‘)’;
}
cout << endl;
return 0;
}
int find_lower_bound(pair<int, int> pair_val) {
auto it = PairList.lower_bound(pair_val);
if (it != PairList.end()) {
cout << “Found lower bound “ << ‘(‘ << pair_val.first << ‘,’ << pair_val.second
<< ‘)’ << “ is “;
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’<<endl;
return distance(PairList.begin(), it);
}
else {
cout << “Not found”;
}
cout << endl;
return -1;
}
int find_upper_bound(pair<int, int> pair_val) {
auto it = PairList.upper_bound(pair_val);
if (it != PairList.end()) {
cout << “Found upper bound “ << ‘(‘ << pair_val.first << ‘,’ << pair_val.second
<< ‘)’ << “ is “;
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ <<endl;
return distance(PairList.begin(), it);
}
else {
cout << “Not found”;
}
cout << endl;
return -1;
}
void display_inserted_pair() {
cout << endl;
cout << “Initial Sorted Pair List” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
auto it = PairList.insert({ 3, 2 });
auto val = it.first;
cout << “Inserted 1st element” <<’(‘<< val->first << ‘,’ << val->second << ‘)’ <<endl;
cout << “After insertion Sorted Pair List” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << ‘,’ << “ “;
cout << endl;
}
void display_erased_pair() {
cout << endl;
cout << “Initial Sorted Pair List” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
auto it = PairList.find({ 3, 2 });
cout << “Erased element “ << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << endl;
PairList.erase(it);
cout << “After Erased Sorted Pair List” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
}
void display_next_pair() {
cout << endl;
cout << “Sorted pair” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
auto it = PairList.find({ 2, 7});
if (next(it) != PairList.end()) {
cout << “Next element “ << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ is “;
cout << ‘(‘ << next(it)->first << ‘,’ << (++it)->second << ‘)’ << endl;
}
}
void display_prev_pair() {
cout << endl;
cout << “Sorted pair” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
auto it = PairList.find({ 2, 7 });
if (prev(it) != PairList.end()) {
cout << “Prev element “ << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ is “;
cout << ‘(‘ << prev(it)->first << ‘,’ << ( — it)->second << ‘)’ << endl;
}
}
void display_pair() {
cout << “Sorted pair” << endl;
for (auto it = PairList.begin(); it != PairList.end(); ++it)
cout << ‘(‘ << it->first << ‘,’ << it->second << ‘)’ << “ “;
cout << endl;
cout << “Find Operation” << endl;
find_key({ 1, 1 });
find_key({ 5, 5 });
find_key({ 5, 6 });
find_key({ 1, 4 });
find_key({ 6, 6 });
find_key({ 6, 7 });
find_key({ 8, 10 });
find_key({ 1, 12 });
find_key({ 1, 2 });
cout << endl;
cout << “Lower Bound Operation” << endl;
find_lower_bound({ 1, 1 });
find_lower_bound({ 5, 5 });
find_lower_bound({ 5, 6 });
find_lower_bound({ 4, 4 });
find_lower_bound({ 1, 4 });
find_lower_bound({ 6, 6 });
find_lower_bound({ 6, 7 });
find_lower_bound({ 8, 10 });
find_lower_bound({ 9, 9 });
find_lower_bound({ 2, 6 });
find_lower_bound({ 7, 9 });
find_lower_bound({ 8, 10 });
cout << endl;
cout << “Upper Bound Operation” << endl;
find_upper_bound({ 1, 1 });
find_upper_bound({ 5, 5 });
find_upper_bound({ 5, 6 });
find_upper_bound({ 4, 4 });
find_upper_bound({ 1, 4 });
find_upper_bound({ 6, 6 });
find_upper_bound({ 6, 7 });
find_upper_bound({ 8, 10 });
find_upper_bound({ 9, 9 });
find_upper_bound({ 2, 6 });
find_upper_bound({ 7, 9 });
find_upper_bound({ 8, 10 });
cout << endl;
display_inserted_pair();
display_erased_pair();
display_next_pair();
display_prev_pair();
}
int main() {
display_pair();
return 0;
}
