STL library - Sets

Contributed by blitzcoder On 19th September, 2010

This is an article on STL library - Sets in C++.

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 Go4Expert Founder
4Oct2010,10:21	#2
	If you liked this article do nominate this article for Article of the month - Sep 2010 Before 15th of October 2010.