We recently saw a tutorial on
Vectors in C++. Now its time for better things. So we all know what a set is. It is a group of elements in which there is no duplicate.
Consider we need a container with following features:
-> add an element, but do not allow duplicates
-> remove elements
-> get count of elements (distinct elements)
-> check whether elements are present in set
The container we have to use here is a "set". Set can add, remove and check the presence of particular element in O(log N), where N is the count of objects in the set.
Code:
set<int> r;
for(int i = 1; i <= 50; i++) {
r.insert(i); // Insert 50 elements, [1..50]
}
s.insert(4); // does nothing, 4 already exists in set
for(int i = 2; i <= 50; i += 2) {
s.erase(i); // Erase even values
}
int n = int(s.size()); // n will be 25
Since set is not a linear container, it’s impossible to take the element in set by index. Thus, we traverse the elements of set using iterators.
Code:
// Calculate the sum of elements in set
set<int> S;
// ...
int r = 0;
for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) {
r += *it;
}
To determine whether some element is present in set use 'find()' member function. There are several 'find()' ’s in STL. There is a global algorithm 'find()', which takes two iterators, element, and works for O(N). While searching in set and map do not use global find – instead, use member function 'set::find()'. As 'ordinal' find, set::find will return an iterator, either to the element found, or to 'end()'. So, the element presence check looks like this:
Code:
set<int> s;
// ...
if(s.find(4) != s.end()) {
// 4 present in set
}
else {
// 4 not present in set
}
To erase an element from set use the erase() function.
Code:
set<int> s;
// …
s.insert(54);
s.erase(29);
The erase() function also has the interval form:
Code:
set<int> s;
// ..
set<int>::iterator it1, it2;
it1 = s.find(10);
it2 = s.find(100);
// Will work if it1 and it2 are valid iterators, i.e. values 10 and 100 present in set.
s.erase(it1, it2); // Note that 10 will be deleted, but 100 will remain in the container
Set has an interval constructor as well:
Code:
int d[5] = { 7, 8, 4, 2, 6 };
set<int> S(d, d+5);
It gives us a simple way to get rid of duplicates in vector, and sort it:
Code:
vector<int> h;
// …
set<int> r(all(h));
vector<int> h1(all(r));
Last but not the least, here 'h1' will contain the same elements as 'h' but
sorted in ascending order and with
duplicates removed.
I hope now you realize the power of STL library in C++ :)