C++/Data Structure/Deque
Содержание
- 1 Assigning deque objects.
- 2 Demonstrate a deque.
- 3 Demonstrate raw storage iterators
- 4 Demonstrate resize() for deque
- 5 Demonstrate swap() for deque
- 6 Deque: push, pop, sort, find, begin, end, insert
- 7 Iterator values may change.
- 8 One way to reverse-copy a deque.
- 9 Reverse iterators and copy.
- 10 Use reverse iterators.
Assigning deque objects.
#include <iostream>
#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;
}
Demonstrate a deque.
#include <iostream>
#include <deque>
#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;
}
Demonstrate raw storage iterators
#include <iostream>
#include <deque>
#include <memory>
#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;
}
Demonstrate resize() for deque
#include <iostream>
#include <deque>
#include <algorithm>
#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;
}
Demonstrate swap() for deque
#include <iostream>
#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;
}
Deque: push, pop, sort, find, begin, end, insert
#include <string>
#include <deque>
#include <iostream>
#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;
}
Iterator values may change.
#include <iostream>
#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;
}
One way to reverse-copy a deque.
#include <iostream>
#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;
}
Reverse iterators and copy.
#include <iostream>
#include <deque>
#include <algorithm>
#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;
}
Use reverse iterators.
#include <iostream>
#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;
}