All about set STL in c++ for competitive programming( initialization, traversal and methods/functions ) :

set STL

Important Points:

1. It is an associative container which contains a sorted set of unique objects of type keys.
   
2. The value of the elements in a set can't be modified once put in the container, but they can be inserted or removed from the container.
   
3. Set is typically implemented as binary search tree.
4. Remember to use the header file #include<set> before using set STL.
   

Advantages of using set STL:

• Since set contains only unique elements therefore, we can use this feature to remove all the duplicate elements. 
• Insertion, removal and searching have logarithmic time complexity. 
• Elements are also in sorted order (ascending by default) which can be useful in some cases.

 

Associative containers vs Sequence containers:

• Unlike sequence containers elements in associative container are referenced by their key and not by their absolute position in the container.
• Elements of an associative container follows strict weak ordering.
• Example for associative containers - set, map, multiset, multimap etc.
• Example for sequence containers - vector, array, deque etc.
  

 

 

Different ways to initialize a set STL

1. declaring a set and using insert( ) method to put elements into it :  

    set < int > s ;
    s.insert( 10 ) ;
    s.insert( 20 ) ;
    s.insert( 30 ) ;

 

 

2. Initializing like arrays:

 

    set < int > s{ 10, 20, 30 } ;

 

 

3. Initializing from a vector:

    vector < int > v { 10, 20, 30 } ;

    set < int > s( v.begin( ),  v.end( ) ) ;

  

Note: If the vector is having duplicate elements then on converting it to set will remove all the duplicates.

 

4. Initializing from another set:

 

    set < int > s1{ 10, 20, 30 } ;

    set <int>s2( s1.begin( ), s1.end( ));

 

 

5. What if we want the sorting order of the elements in the set to be in descending order instead of the ascending which is the default behaviour, then initialize it like this :

 

    set < int, greater < int > > s ;

 

 

 

**don't worry about the methods / functions used above, i am going to explain each and every function associated with set STL below.

 

 

 

All set STL methods/ functions  

1. set STL important iterator functions:

Iterator definition: An iterator is something which helps in moving within the container. It points to a specific element and it moves according to our commands from one element to another.

 

1. begin( ) : returns an iterator pointing to the first element of the set.

 

2. end( ) :  returns an iterator pointing to the theoretical element after the last element of the set.

Other functions:

•  rbegin( )
•  cbegin( )
•  crbegin( )
•  rend( )
•  cend( )
•  crend( )
  

 

 

2. set STL  important capacity related functions:

1. size( ) : returns the number of elements in the set.

2. empty( ) : returns true if the container is empty otherwise, false.

Other functions:

•  max_size( )

 

 

3. set STL important modifying functions or modifiers:

1. insert( ) or emplace( ) :  used to insert a new element into the set.

2. clear( ) : used to remove all elements from the set container.

 

3. swap( ) : used to exchange the content of two sets of a same type (size may differ).

 

4. erase( ) : used to remove a single element or a list of elements from the set. 

 

Other functions:

•  emplace_hint( )

 

emplace( ) vs insert( ) which to use?

• emplace() avoids unnecessary copy of objects.
• for primitive data types it does not matter which one to use but for objects or bigger objects use emplace() for efficiency.
• unlike insert(), no copy or move operation are performed in emplace().

 

4. set STL other important functions (may come handy during competitions) :

1. find( ) : It searches for the element specified in the parenthesis and returns an iterator pointing towards it if found. Otherwise, it returns an iterator pointing to set_name.end( ) .

 

2. count( ) :  Since set is having all unique elements, it returns 1 if the element specified in its parenthesis is present in the set. Otherwise, it returns 0.

3. lower_bound( ) :  It returns an iterator pointing to the element greater than or equal to the value specified in the parenthesis. Otherwise, it returns an iterator pointing to set_name.end( ) .

 

4. upper_bound( ) :  It returns an iterator pointing to the element greater than the value specified in the parenthesis. Otherwise, it returns an iterator pointing to set_name.end( ) .

 

 

Other functions:

• equal_range( ) 
• key_comp( )
• value_comp( )
  

 

 

 

 

List of all set STL important functions with example

 1. Initializing set : set< int > s ;

 

 2. Putting elements into it : 

     s.insert( 10 ) ;

     s.insert( 30 ) ;

     s.insert( 10 ) ;

     s.insert( 20 ) ;  

     Therefore, 

     s = { 10, 20, 30 } 

 

3. cout << s.size( ) ;               // 3

 

4. Checking whether vector is empty or not :

    if( s.empty( ) = = false )

    cout << "not empty" ;     //it will be printed

    else

    cout << "empty" ;

 

5. s.erase( 30 ) ;     // 30 will be removed

    Therefore, 

    s = { 10, 20 }

 

6. using erase( ) to remove a range of elements :

    //setting up an iterator named it     

    set < int > : : iterator it ;

    s.insert( 15 ) ;

    s.insert( 30 ) ;

    s.insert( 40 ) ;

    Therefore, 

    s = { 10, 15, 20, 30, 40 }

    it = s.find( 20 ) ;

    //iterator pointing towards element 20 in set

    s.erase( it, s.end( ) ) ;

    Therefore,    

    s = { 10, 15 }

     

 

7. it = s.lower_bound( 10 ) ;     

    //iterator pointing towards element 10 in set

 

8. it = s.upper_bound( 10 ) ;     

    //iterator pointing towards element 15 in set

 

9. s.clear( )      // all elements are removed from the set

set STL traversal methods

Let our set be s :

set < int > s ;

 

1. for ( auto &i : s)

    {

          cout << i << " "; 

    }

       

2. for ( auto i = s.begin( ) ; i ! = s.end( ) ; i++)

    {

         cout << *i << " " ;

    }

 

  

3. declaring an iterator it :

    set < int > : : it ;

    for ( it = s.begin( ) ; it!=s.end( ) ; it++)

    {

         cout << *it << " " ;

    }

 

4. You can also convert the given set into vector by: 

    vector < int > v( s.begin( ),  s.end( ) ) ;

    and can use all vector traversal methods.

 

 

 

 

 

 

Hi reader! got any queries or need more explanation for something? Feel free to comment below.