1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

STL library - Sets

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

  1. blitzcoder

    blitzcoder New Member

    Joined:
    Aug 24, 2010
    Messages:
    12
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Surat, India
    Home Page:
    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++ :)
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
  3. GIRUM

    GIRUM New Member

    Joined:
    Dec 3, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    every thing is good
     

Share This Page