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

-

deque STL

Important Points:

  1. It is a sequence container with dynamic size that can be expanded or contracted on both ends.
  2. deque is also known as double-ended queue.
  3. It is same as the double-ended queue in c but with a huge advantage of availability of direct functions/methods for many operations.
  4. 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 ) ;
 
    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 ) ;
  
    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 } ) ;
  
    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.

2. back( ) : returns the last 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).

4. pop_back( ) : removes the last element of the deque.
 
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 << " " ;
    }
 
 
 

 

 

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

Location: India

Comments

Post a Comment

Popular posts from this blog

Coursera's Algorithmic toolbox assignment solutions( Sum of Two Digits, Maximum Pairwise Product ) :

-
Problem 1: Sum of Two Digits Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) #include < bits/stdc++.h > using namespace std ; int main () { int a , b ; cin >> a >> b ; cout << a + b ; } This code is simple. There's no need for any explanation.         Problem 2: Maximum Pairwise Product Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) #include< bits/stdc++.h > using namespace std ; int main () {      long long n , i ;     cin >> n ;      long long a [ n ];      for ( i = 0 ; i < n ; i ++) { cin >> a [ i ]; } sort ( a , a + n ); cout <<( a [ n - 1 ]* a [ n - 2 ]); } This code is simple. There's no need for any explanation.       Guys , if you have any queries related to a question or need more explan
Read more

HackerEarth's basic programming solutions( Seating Arrangement, Zoos, Anagrams ) :

-
Problem 1: Seating Arrangement Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) #include< bits/stdc++.h > using namespace std ; int main () { long long t , s , p ; //t=no. of test cases cin >> t ; // s=seat no., p=corresponding seat no. while ( t --) { cin >> s ;      p = s % 12 ; //when to use modulo see below if ( p == 1 )      {          cout << s + 11 << " WS" << endl ;      }      else if ( p == 2 )      {          cout << s + 9 << " MS" << endl ;      } else if ( p == 3 )      {          cout << s + 7 << " AS" << endl ;      }      else if ( p == 4 )      {          cout << s + 5 << " AS" << endl ;      }      else if ( p == 5 )      {          cout << s + 3 << " MS" << endl ;     
Read more

HackerEarth's basic programming solutions( Minimize Cost, Magical Word, Best Index ) :

-
Problem 42: Minimize Cost Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) "Still working on this problem....."         Problem 43: Magical Word Solution: (in c++) ( please guys before moving to the solution try it yourself at least 3-4 times , if you really wanna become a good coder) #include< bits/stdc++.h > using namespace std ; int main () { int t ;    cin >> t ;     while ( t --)     {        int l ;       string s ;       cin >> l >> s ;        for ( int i = 0 ; i < s . length (); i ++)         {           if ( s [ i ]<= 69 && s [ i ]>= 65 )          s [ i ]= 'C' ;           else if ( s [ i ]<= 72 && s [ i ]>= 70 )          s [ i ]= 'G' ;           else if ( s [ i ]<= 76 && s [ i ]>= 73 )          s [ i ]= 'I' ;           else if ( s [ i ]<= 81 &&
Read more