Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   STL library - Sets (http://www.go4expert.com/articles/stl-library-sets-t23350/)

 blitzcoder 19Sep2010 13:06

STL library - Sets

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++ :)

 shabbir 4Oct2010 10:21

Re: STL library - Sets