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