C++/Data Structure/Deque

Assigning deque objects.

<source lang="cpp">

1. include <iostream>
2. include <deque>

using namespace std; int main() {

 deque<char> dequeObject1(10), dequeObject2;
 int i;
 for(i = 0; i <10; i++) 
    dequeObject1[i] = i + "A";
 cout << "Contents of dequeObject1 are: ";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << "\n\n";
 // assign one deque to another
 dequeObject2 = dequeObject1;
 cout << "Size of dequeObject2 is " << dequeObject2.size() << endl;
 cout << "Contents of dequeObject2 are: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 dequeObject2.assign(dequeObject1.begin()+2, dequeObject1.end()-2);
 cout << "Size of dequeObject2 is " << dequeObject2.size() << endl;
 cout << "Contents of dequeObject2 are: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 dequeObject2.assign(8, "X");
 cout << "Size of dequeObject2 is " << dequeObject2.size() << endl;
 cout << "Contents of dequeObject2 are: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 return 0;

}

      </source>

Demonstrate a deque.

<source lang="cpp">

1. include <iostream>
2. include <deque>
3. include <cstring>

using namespace std; int main() {

 deque<char> dequeObject1;
 char str[] = "Using a deque.";
 int i;
 for(i = 0; str[i]; i++) {
   dequeObject1.push_front(str[i]);
   dequeObject1.push_back(str[i]);
 }
 cout << "Original dequeObject1:\n";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << "\n\n";
 for(i = 0; i <strlen(str); i++) 
    dequeObject1.pop_front();
 cout << "dequeObject1 after popping front:\n";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << "\n\n";
 deque<char> dequeObject2(dequeObject1); 
 cout << "dequeObject2 original contents:\n";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 for(i = 0; i <dequeObject2.size(); i++)
    dequeObject2[i] = dequeObject2[i]+1;
 
 cout << "dequeObject2 transposed contents:\n";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 deque<char>::iterator p = dequeObject1.begin();
 while(p != dequeObject1.end()) {
   if(*p == "a") break;
   p++;
 }
 dequeObject1.insert(p, dequeObject2.begin(), dequeObject2.end());
 cout << "dequeObject1 after insertion:\n";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << "\n\n";
 return 0;

}

      </source>

Demonstrate raw storage iterators

<source lang="cpp">

1. include <iostream>
2. include <deque>
3. include <memory>
4. include <algorithm>

using namespace std; class MyClass {

 int a, b;
 int sum;

public:

 MyClass() { 
    a = b = 0; 
    sum = 0; 
 }
 MyClass(int x, int y) { 
    a = x; 
    b = y; 
 }
 MyClass(const MyClass &o) {
  a = o.a; b = o.b;
  sum = o.sum;
 }
 MyClass operator=(const MyClass &o) {
   a = o.a; b = o.b;
   return *this;
 }
 void setsum() { 
   sum = a+b; 
 }
 void show() {
   cout << a << "," << b;
   cout << " Sum is: " << sum << endl;
 }

}; int main() {

 unsigned char raw1[100], raw2[100];
 MyClass *p;
 deque<MyClass> dequeObject(5);
 int i;
 for(i = 0; i <5; i++) {
   dequeObject[ i ] = MyClass(i, i);
   dequeObject[ i ].setsum();
 }
 
 // store deque in uninitialized memory the wrong way
 copy(dequeObject.begin(), dequeObject.end(), (MyClass *)raw1);  
 cout << "Contents of raw memory (incorrect):\n";
 p = (MyClass *) raw1;
 for(i = 0; i <5; i++)
   p[ i ].show();
 // the right way
 copy(dequeObject.begin(), dequeObject.end(),raw_storage_iterator<MyClass *, MyClass>((MyClass *)raw2));
 cout << "Contents of raw memory (correct):\n";
 p = (MyClass *) raw2;
 for(i = 0; i <5; i++)
   p[ i ].show();
 return 0;

}

      </source>

Demonstrate resize() for deque

<source lang="cpp">

1. include <iostream>
2. include <deque>
3. include <algorithm>
4. include <cmath>

using namespace std; int main() {

 deque<double> dequeObject1, dequeObject2;
 double num;
 int i;
 for(;;) {
   cout << "Enter angles (0 to stop): ";
   cin >> num;
   if(num == 0.0) break;
   dequeObject1.push_back(num);
 }
 dequeObject2.resize(dequeObject1.size());
 for(i = 0; i <dequeObject2.size(); i++) {
   cout << "Angle and sine: ";
   cout << dequeObject1[i] << " " << dequeObject2[i];
   cout << endl;
 }
 cout << endl;
  
 return 0;

}

      </source>

Demonstrate swap() for deque

<source lang="cpp">

1. include <iostream>
2. include <deque>

using namespace std; int main() {

 deque<char> dequeObject1, dequeObject2;
 int i;
 for(i = 0; i <26; i++) 
    dequeObject1.push_back(i+"A");
 for(i = 0; i <10; i++) 
    dequeObject2.push_front(i+"0");
 cout << "Size of dequeObject1 and dequeObject2: ";
 cout << dequeObject1.size() << " " << dequeObject2.size() << endl;
 cout << "dequeObject1: ";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << endl;
 cout << "dequeObject2: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 // swap deques using member function.
 dequeObject1.swap(dequeObject2);
 cout << "Size of dequeObject1 and dequeObject2 after first swap: ";
 cout << dequeObject1.size() << " " << dequeObject2.size() << endl;
 cout << "dequeObject1 after first swap: ";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << endl;
 cout << "dequeObject2 after first swap: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << "\n\n";
 swap(dequeObject1, dequeObject2);
 cout << "Size of dequeObject1 and dequeObject2 after second swap: ";
 cout << dequeObject1.size() << " " << dequeObject2.size() << endl;
 cout << "dequeObject1 after second swap: ";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << endl;
 cout << "dequeObject2 after second swap: ";
 for(i = 0; i <dequeObject2.size(); i++)
   cout << dequeObject2[i];
 cout << endl;
 return 0;

}

      </source>

Deque: push, pop, sort, find, begin, end, insert

<source lang="cpp">

1. include <string>
2. include <deque>
3. include <iostream>
4. include <algorithm>

using namespace std; void print( deque<string> ); int main() {

   deque<string> dequeObject;                                                  
   dequeObject.push_back( "yak" );                                             
   dequeObject.push_back( "zebra" );                                               
   dequeObject.push_front( "cat" );                                            
   dequeObject.push_front( "canary" );                                         
   print(dequeObject);
   dequeObject.pop_front();                                                    
   dequeObject.pop_back();                                                     
   print(dequeObject);
   //list operations on a deque:
   dequeObject.erase(find( dequeObject.begin(), dequeObject.end(), "cat" ));           
   print(dequeObject);
   dequeObject.insert( dequeObject.begin(), "canary" );                            
   print(dequeObject);
   int sz = dequeObject.size();      
   dequeObject.resize( 5 );          
   dequeObject[sz] = "fox";          
   dequeObject[sz+1] = "elephant";   
   dequeObject[sz+2] = "cat";        
   print( dequeObject );             
   dequeObject.erase( dequeObject.begin() + 2 ); 
   print( dequeObject );             
   //sorting a deque:
   sort( dequeObject.begin(), dequeObject.end() );                                 
   print( dequeObject );           
   return 0;

} void print( deque<string> d ) {

   typedef deque<string>::const_iterator CI;                 
   cout << "The number of items in the deque:" << d.size() << endl; 
   for ( CI iter = d.begin(); iter != d.end(); iter++ )
        cout << *iter << " ";
   cout << endl << endl;

}

      </source>

Iterator values may change.

<source lang="cpp">

1. include <iostream>
2. include <deque>

using namespace std; int main() {

 deque<char> dequeObject;
 deque<char>::iterator p1, p2;
 int i;
 for(i = 0; i <5; i++) 
    dequeObject.push_back(i + "A");
 cout << "Original sequence: ";
 for(i = 0; i <dequeObject.size(); i++)
   cout << dequeObject[i] << " ";
 cout << endl;
 p1 = dequeObject.begin() + 2;
 p2 = dequeObject.begin() + 3;
 cout << "*p1: " << *p1 << ", ";
 cout << "*p2: " << *p2 << endl;
 cout << endl;
 dequeObject.insert(p1, "X");
 cout << "Sequence after insert: ";
 for(i = 0; i <dequeObject.size(); i++)
   cout << dequeObject[i] << " ";
 cout << endl;
 cout << "*p1: " << *p1 << ", ";
 cout << "*p2: " << *p2 << endl;
 return 0;

}

      </source>

One way to reverse-copy a deque.

<source lang="cpp">

1. include <iostream>
2. include <deque>

using namespace std; int main() {

 deque<char> dequeObject;
 deque<char> reversedQueue;
 int i;
 for(i = 0; i <10; i++) 
    dequeObject.push_back("A"+i);
 cout << "Contents of dequeObject: ";
 for(i = 0; i <dequeObject.size(); i++) 
   cout << dequeObject[i];
 cout << endl;
 while(!dequeObject.empty()) {
   reversedQueue.push_front(dequeObject.front());
   dequeObject.pop_front();
 }
 
 cout << "Contents of reversedQueue: ";
 for(i = 0; i <reversedQueue.size(); i++) 
   cout << reversedQueue[i];
   
 return 0;

}

      </source>

Reverse iterators and copy.

<source lang="cpp">

1. include <iostream>
2. include <deque>
3. include <algorithm>
4. include <cstring>

using namespace std; int main() {

 deque<char> dequeObject1(30), dequeObject2, dequeObject3;
 int i;
 char str1[] = "forward";
 for(i = 0; str1[i]; i++) 
    dequeObject2.push_back(str1[i]);
 copy(dequeObject2.begin(), dequeObject2.end(), dequeObject1.begin());
 cout << "Contents dequeObject1 after forward copy:\n";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 cout << "\n\n";
 char str2[] = "backward";
 for(i = 0; str2[i]; i++) 
    dequeObject3.push_back(str2[i]);
 copy(dequeObject3.rbegin(), dequeObject3.rend(), dequeObject1.begin()+strlen(str1));
 cout << "Contents dequeObject1 after reverse copy:\n";
 for(i = 0; i <dequeObject1.size(); i++)
   cout << dequeObject1[i];
 return 0;

}

      </source>

Use reverse iterators.

<source lang="cpp">

1. include <iostream>
2. include <deque>

using namespace std; int main() {

 deque<int> dequeObject;
 deque<int>::reverse_iterator rp;
 int i;
 for(i = 0; i <10; i++) 
    dequeObject.push_back(i);
 cout << "Contents printed backward:\n";
 rp = dequeObject.rbegin();
 while(rp != dequeObject.rend()) {
   cout << *rp << " ";
   rp++;
 }
 cout << "\n\n";
 cout << "Contents printed forward:\n";
 rp = dequeObject.rend();
 while(rp != dequeObject.rbegin()) {
   rp--;
   cout << *rp << " ";
 }
 return 0;

}

      </source>