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:
    http://shreyagarwal.blog.com
    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,375
    Likes Received:
    388
    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

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice