# STL library - Sets

Discussion in 'C++' started by blitzcoder, Sep 19, 2010.

1. ### blitzcoderNew Member

Joined:
Aug 24, 2010
Messages:
12
2
Trophy Points:
0
Occupation:
Student
Location:
Surat, India
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 = { 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++ Joined:
Jul 12, 2004
Messages:
15,332
377
Trophy Points:
83

Joined:
Dec 3, 2010
Messages:
1