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

forward_list STL

Important Points:

1. It is a sequence container that allows constant time insert and erase operations anywhere within the container.
2. It is same as the singly linked list in c but with a huge advantage of availability of direct functions/methods for many operations.
3. Its objects can only be iterated in one direction i.e forward because of single link.
4. Remember to use the header file #include<forward_list> before using forward_list STL.
   

forward_list vs other sequence containers:

• forward_list perform generally better in inserting, extracting and moving elements to any position within the container. 
• forward_list lacks direct access to elements by their position. For example - to access the 6th element in it one has to iterate from beginning to that position.
  

 

list vs forward_list:

• forward_list is very similar to list and the main difference being is, in list elements can be iterated in from both directions i.e forward and backward.
  
• forward_list is less bulky therefore, fast compared to list because of only single links

 

 

Different ways to initialize a forward_list STL

1. declaring a forward_list and using push_front( ) method to put elements into it from front :  

    forward_list < int > f ;
    f.push_front( 10 ) ;
    f.push_front( 20 ) ;
    f.push_front( 30 ) ;

 

    Therefore, 

    f = { 30, 20, 10 }

  

 

2. declaring a forward_list and using assign( ) method to put elements into it :  

    forward_list < int > f ;
    l.assign( { 10, 20, 30 } ) ;

  

    Therefore,      

    f = { 10, 20, 30 } 

 

 

3. Initializing like arrays:

 

    forward_list < int > f  = { 10, 20, 30 } ;

 

    Therefore,      

    f = { 10, 20, 30 }

 

 

4. filling a forward_list with the same specified element :

Suppose we want a list of size 3 and it's every element is 10

Therefore,

 

    forward_list < int > f ( 3, 10 ) ; 

 

            or

 

    forward_list < int > f ;

    f.assign( 3, 10 ) ; 

 

  

    Therefore,      

    f = { 10, 10, 10 }

 

 

6. Initializing from another forward_list:

 

    forward_list < int > f1 ={ 10, 20, 30 } ;

    forward_list < int > f ( f1.begin( ), f1.end( ) ) ;

 

    Therefore,      

    f = { 10, 20, 30 }

 

 

8. Using other containers :

 

    using vector STL, let the vector be v

    forward_list < int > f( v.begin( ), v.end( ) ) ;

 

 

    using set STL, let the set be s

    forward_list < int > f( s.begin( ), s.end( ) ) ;

 

 

Similary, you can initialize it using other containers, if possible.

 

 

 

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

 

 

 

All forward_list STL methods/ functions  

1. forward_list 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 forward_list.

 

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

3. before_begin( ) :  returns an iterator pointing to the theoretical element before the first element of the forward_list.

 

Other functions:

•     cbegin( )
•     cend( )
•     cbefore_begin( ) 

 

 

2. forward_list STL  important capacity related functions

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

Other functions:

•     max_size( )

 

3. forward_list STL important element access functions:

1. front( ) : returns the first element of the forward_list.

 

 

4. forward_list STL important modifying functions or modifiers

1. push_front( ) or emplace_front( ) : inserts a new element at the beginning of the forward_list (right before its current first element).

 

2. insert_after( ) or emplace_after( ) : inserts a new element after the specified position (using iterators) in its parenthesis.

 

3. pop_front( ) : removes the first element of the forward_list.

4. clear( ) : used to remove all elements from the forward_list container.

 

5. swap( ) : used to exchange the content of two forward_lists of same type (size may differ).

 

6. erase_after( ) : used to remove a single element or a list of elements from the forward_list. 

7. assign( ) : assigns new elements to the forward_list, replacing its current elements (if exists) and modifying its size accordingly.

 

8. resize( ) : resizes the container to the number specified in the parenthesis.

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().

 

5. forward_list STL other important functions (may come handy during competitions) :

1. splice_after( ) : used to transfer a single element, a range of elements or entire elements from one forward_list to another.

 

2. remove( ) :  removes the element specified in the parenthesis.

3. unique( ) :  used to remove all the duplicate elements from the forward_list. (Note: this method works properly only when the forward_list is in sorted order.)

 

4. sort( ) :  used to sort the elements of the forward_list container.

 

5. merge( ) :  used to merge two sorted forward_lists. 

 

6. reverse( ) :  reverses the order of elements in the forward_list container.

 

Other functions:

•    remove_if( )

 

 all forward_list STL important functions with example

1. Initializing forward_list : forward_list < int > f ;

 

2. Putting elements into it : 

     f.push_front( 10 ) ;

     f.push_front( 20 ) ;

     f.push_front( 30 ) ;

     f.push_front( 40 ) ;  

     Therefore, 

     f = { 40, 30, 20, 10 } 

 

3. cout << f.front( ) ;               //40

 

4. Checking whether forward_list is empty or not :

    if( f.empty( ) = = false )

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

    else

    cout << "empty" ;

 

5. f.pop_front( ) ;  

    // first element removed i.e 40

        

     Therefore, 

       f = { 30, 20, 10 } 

 

6. f.assign( { 1, 2, 4, 3, 2, 3 } ) ;

      Therefore,  

       f = { 1, 2, 4, 3, 2, 3 }

 

7. f.remove( 2 ) ;

     // all 2s are removed

 

8. f.sort( ) ;  

      Therefore, 

       f = { 1, 3, 3, 4, }

 

9. f.unique( ) ;  

      Therefore, 

       f = { 1, 3, 4 }

 

10. //setting up an iterator named it

      forward_list < int > : : iterator it ;    

      it = f.before_begin( ) ;

      f.insert_after( it, { 10, 20, 30 } )       

      Therefore, 

      f = { 10, 20, 30, 1, 3, 4 }

 

19. it = f.begin( ) ;       

      //removing all elements after the first element

     f.erase_after( it, f.end( ) ) ;

      Therefore, 

       f = { 10 }

 

 20. f.clear( )      // all elements are removed from the forward_list

forward_list STL traversal methods

Let our forward_list be f :

forward_list < int > f ;

 

1. for ( auto &i : f )

    {

          cout << i << " "; 

    }

       

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

    {

         cout << *i << " " ;

    }

 

  

3. declaring an iterator it :

    forward_list < int > : : it ;

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

    {

         cout << *it << " " ;

    }

 

 

 

 

 

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