All about deque STL in c++ for competitive programming( initialization, traversal and methods/functions ) :
deque STL
Important Points:
- It is a sequence container with dynamic size that can be expanded or contracted on both ends.
- deque is also known as double-ended queue.
- It is same as the double-ended queue in c but with a huge advantage of availability of direct functions/methods for many operations.
- Remember to use the header file #include<deque> before using deque STL.
deque vs other sequence containers:
- deque is similar to vector STL on the basis of functionality and interface and can be used for similar purposes but both are having different internal structures.
- deque provides efficient insertion of the element at the beginning or at the end and performs worse in insertion and removal of elements at the remaining positions.
deque vs queue:
- In queue insertion takes place from one end and removal takes place at the other end while in deque insertion/removal can be done from any end.
- We can use iterators with deque but not with queue.
Different ways to initialize a deque STL
1. declaring a deque and using push_front( ) method to put elements into it from front :
deque < int > dq ;
dq.push_front( 10 ) ;
dq.push_front( 20 ) ;
dq.push_front( 30 ) ;
dq.push_front( 10 ) ;
dq.push_front( 20 ) ;
dq.push_front( 30 ) ;
Therefore,
dq = { 30, 20, 10 }
2. declaring a deque and using push_back( ) method to put elements into it from back :
deque < int > dq ;
dq.push_back( 10 ) ;
dq.push_back( 20 ) ;
dq.push_back( 30 ) ;
dq.push_back( 10 ) ;
dq.push_back( 20 ) ;
dq.push_back( 30 ) ;
Therefore,
dq = { 10, 20, 30 }
3. declaring a deque and using assign( ) method to put elements into it :
deque < int > dq ;
dq.assign( { 10, 20, 30 } ) ;
dq.assign( { 10, 20, 30 } ) ;
Therefore,
dq = { 10, 20, 30 }
4. Initializing like arrays:
deque < int > dq = { 10, 20, 30 } ;
Therefore,
dq = { 10, 20, 30 } 5. filling a deque with the same specified element :
Suppose we want a deque of size 3 and it's every element is 10
Therefore,
deque < int > dq ( 3, 10 ) ;
or
deque < int > dq;
dq.assign( 3, 10 ) ;
Therefore,
dq = { 10, 10, 10 } 6. Initializing from another deque:
deque < int > dq1 ={ 10, 20, 30 } ;
deque < int > dq ( dq1.begin( ), dq1.end( ) ) ;
Therefore,
dq = { 10, 20, 30 } 8. Using other containers :
using vector STL, let the vector be v
deque < int > dq( v.begin( ), v.end( ) ) ;
using set STL, let the set be s
deque < int > dq( 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 deque STL below.
All deque STL methods/ functions
1. deque 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 deque.
2. end( ) : returns an iterator pointing to the theoretical element after the last element of the deque.
Other functions:
- rbegin( )
- cbegin( )
- crbegin( )
- rend( )
- cend( )
- crend( )
2. deque STL important capacity related functions:
1. size( ) : returns
the number of elements in the deque.
2. empty( ) : returns true if the container is empty otherwise, false.
Other functions:
- max_size( )
- shrink_to_fit( )
3. deque STL important element access functions:
1. front( ) : returns the first element of the deque.
3. at( ) : returns the element at the specified position in the parenthesis.
2. [ ] : returns the element at the specified position in the square brackets.
4. deque STL important modifying functions or modifiers:
1. push_back( ) or emplace_back( ) : used to put elements into a deque from back.
2. push_front( ) or emplace_front( ) : used to put elements into a deque from front.
3. insert( ) or emplace( ) : used to insert a new element into the deque at the specified position (using iterators).
5. pop_front( ) : removes the first element of the deque.
6. clear( ) : used to remove all elements from the deque container.
7. swap( ) : used to exchange the content of two deque containers of same type (size may differ).
8. erase( ) : used to remove a single element or a list of elements from the deque.
9. assign( ) : assigns new elements to the deque, 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().
all deque STL important functions with example
1. Initializing deque : deque< int > dq ;
2. Putting elements into it :
dq.push_back( 10 ) ;
dq.push_back( 30 ) ;
dq.push_back( 20 ) ;
Therefore,
dq = { 10, 30, 20 }
3. cout << dq.size( ) ; // 3
4. cout << dq.front( ) ; //10
5. cout << dq.back( ) ; // 20
6. cout << dq[ 2 ] ; // 30
7. cout << dq.at( 2 ) ; // 30
8. Checking whether deque is empty or not :
if( dq.empty( ) = = false )
cout << "not empty" ; //it will be printed
else
cout << "empty" ;
9. dq.pop_back( ) ;
// last element removed i.e 20
10. dq.pop_front( ) ;
// first element removed i.e 10
Therefore,
dq = { 30 }
11. dq.assign( { 1, 2, 4, 3, 2, 3 } ) ;
Therefore,
dq = { 1, 2, 4, 3, 2, 3 }
12. dq.insert( dq.begin( ), 10 ) ;
or
dq.emplace( dq.begin( ), 10 ) ;
// 10 is inserted at front
13. //setting up an iterator named it
deque < int > : : iterator it ;
it = dq.begin( ) ;
//iterator now pointing to the first element
cout << *it ; // 1
14. dq.erase( it ) // 1 is removed
15. dq.clear( ) // all elements are removed from the list
deque STL traversal methods
Let our deque be dq :
deque < int > dq ;
1. for ( auto &i : dq )
{
cout << i << " ";
}
2. for ( auto i = dq.begin( ) ; i ! = dq.end( ) ; i++)
{
cout << *i << " " ;
}
3. declaring an iterator it :
deque < int > : : it ;
for ( it = dq.begin( ) ; it!=dq.end( ) ; it++)
{
cout << *it << " " ;
}
Comments
Post a Comment