All about forward_list STL in c++ for competitive programming( initialization, traversal and methods/functions ) :
forward_list STL
Important Points:
- It is a sequence container that allows constant time insert and erase operations anywhere within the container.
- It is same as the singly linked list in c but with a huge advantage of availability of direct functions/methods for many operations.
- Its objects can only be iterated in one direction i.e forward because of single link.
- 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 ) ;
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 } ) ;
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.
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 << " " ;
}
Comments
Post a Comment