Go4Expert

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
 
If you liked this article do nominate this article for Article of the month - Sep 2010 Before 15th of October 2010.

GIRUM 3Dec2010 23:20

Re: STL library - Sets
 
every thing is good


All times are GMT +5.5. The time now is 07:00.