All about list STL in c++ for competitive programming( initialization, traversal and methods/functions ) :
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 doubly-linked list in c but with a huge advantage of availability of direct functions/methods for many operations.
- Its objects can be iterated in both directions i.e forwards and backwards.
- Remember to use the header file #include<list> before using list STL.
List vs other sequence containers:
- List perform generally better in inserting, extracting and moving elements to any position within the container.
- 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:
- list
is very similar to forward_list and the main difference being is, in
forward_list elements can only be iterated in one direction.
- list consumes some extra memory compared to forward_list because of double linking.
- list is used much in sorting algorithms because of its bi-directional sequence access.
Different ways to initialize a list STL
1. declaring a list and using push_front( ) method to put elements into it from front :
list < int > l ;
l.push_front( 10 ) ;
l.push_front( 20 ) ;
l.push_front( 30 ) ;
l.push_front( 10 ) ;
l.push_front( 20 ) ;
l.push_front( 30 ) ;
Therefore,
l = { 30, 20, 10 }
2. declaring a list and using push_back( ) method to put elements into it from back :
list < int > l ;
l.push_back( 10 ) ;
l.push_back( 20 ) ;
l.push_back( 30 ) ;
l.push_back( 10 ) ;
l.push_back( 20 ) ;
l.push_back( 30 ) ;
Therefore,
l = { 10, 20, 30 }
3. declaring a list and using assign( ) method to put elements into it :
list < int > l ;
l.assign( { 10, 20, 30 } ) ;
l.assign( { 10, 20, 30 } ) ;
Therefore,
l = { 10, 20, 30 }
4. Initializing like arrays:
list < int > l = { 10, 20, 30 } ;
Therefore,
l = { 10, 20, 30 } 5. filling a list with the same specified element :
Suppose we want a list of size 3 and it's every element is 10
Therefore,
list < int >l ( 3, 10 ) ;
or
list < int >l ;
l.assign( 3, 10 ) ;
Therefore,
l = { 10, 10, 10 } 6. Initializing from another list:
list < int > l1 ={ 10, 20, 30 } ;
list <int> l ( l1.begin( ), l1.end( ) ) ;
Therefore,
l = { 10, 20, 30 } 8. Using other containers :
using vector STL, let the vector be v
list < int > l( v.begin( ), v.end( ) ) ;
using set STL, let the set be s
list < int > l( 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 list STL below.
All list STL methods/ functions
1. 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 list.
2. end( ) : returns an iterator pointing to the theoretical element after the last element of the list.
Other functions:
- rbegin( )
- cbegin( )
- crbegin( )
- rend( )
- cend( )
- crend( )
2. list STL important capacity related functions:
1. size( ) : returns
the number of elements in the list.
2. empty( ) : returns true if the container is empty otherwise, false.
Other functions:
- max_size( )
3. list STL important element access functions:
1. front( ) : returns the first element of the list.
4. list STL important modifying functions or modifiers:
1. push_back( ) or emplace_back( ) : used to put elements into a list from back.
2. push_front( ) or emplace_front( ) : used to put elements into a list from front.
3. insert( ) or emplace( ) : used to insert a new element into the list at the specified position (using iterators).
5. pop_front( ) : removes the first element of the list.
6. clear( ) : used to remove all elements from the list container.
7. swap( ) : used to exchange the content of two lists of same type (size may differ).
8. erase( ) : used to remove a single element or a list of elements from the list.
9. assign( ) : assigns new elements to the list, replacing its current elements (if exists) and modifying its size accordingly.
10. 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. list STL other important functions (may come handy during competitions) :
1. splice( ) : used to transfer a single element, a range of elements or entire elements from one list to another.
2. remove( ) : removes the element specified in the parenthesis.
4. sort( ) : used to sort the elements of the list container.
5. merge( ) : used to merge two sorted lists.
6. reverse( ) : reverses the order of elements in the list container.
Other functions:
- remove_if( )
all list STL important functions with example
1. Initializing list : list< int > l ;
2. Putting elements into it :
l.push_back( 10 ) ;
l.push_back( 30 ) ;
l.push_back( 20 ) ;
Therefore,
l = { 10, 30, 20 }
3. cout << l.size( ) ; // 3
4. cout << l.front( ) ; //10
5. cout << l.back( ) ; // 20
6. Checking whether list is empty or not :
if( l.empty( ) = = false )
cout << "not empty" ; //it will be printed
else
cout << "empty" ;
7. l.pop_back( ) ;
// last element removed i.e 20
8. l.pop_front( ) ;
// first element removed i.e 10
Therefore,
l = { 30 }
9. l.assign( { 1, 2, 4, 3, 2, 3 } ) ;
Therefore,
l = { 1, 2, 4, 3, 2, 3 }
10. l.insert( l.begin( ), 10 ) ;
or
l.emplace( l.begin( ), 10 ) ;
// 10 is inserted at front
11. l.remove( 2 ) ;
// all 2s are removed
12. l.sort( ) ;
Therefore,
l = { 1, 3, 3, 4, 10 }
13. l.unique( ) ;
Therefore, l = { 1, 3, 4, 10 }
18. //setting up an iterator named it
list < int > : : iterator it ;
it = l.begin( ) ;
//iterator now pointing to the first element
cout << *it ; // 1
19. l.erase( it ) // 1 is removed
20. l.clear( ) // all elements are removed from the list
list STL traversal methods
Let our list be l :
list < int > l ;
1. for ( auto &i : l )
{
cout << i << " ";
}
2. for ( auto i = l.begin( ) ; i ! = l.end( ) ; i++)
{
cout << *i << " " ;
}
3. declaring an iterator it :
list < int > : : it ;
for ( it = l.begin( ) ; it!=l.end( ) ; it++)
{
cout << *it << " " ;
}
Comments
Post a Comment