|< C++ STL Container 3 | Main | C++ STL Container 5 >| Site Index | Download |


 

 

 

 

 

MODULE 27a

 THE STL CONTAINER PART 4

vector, deque

 

 

 

 

 

My Training Period: xx hours

 

This is a continuation from previous tutorial, compiled using VC++7.0/.Net, win32 empty console mode application.  g++ examples given at the end of this Module. The source code for this tutorial is available in C++ STL Container source code.

 

The C++ container class programming abilities that supposed to be acquired:

 

 

 

What we have in this page?

  1. The deque

  2. A simple deque program example

  3. The <deque> Header Members

  4. deque, constructors program example

  5. vector constructors program example - g++

  6. deque, constructors program example - g++

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

27.5.2  The deque

  • The term deque (pronounced “deck”) is an abbreviation for ‘double-ended queue’.   It is a dynamic array that is implemented so that it can grow in both directions.

  • So, inserting elements at the end and at the beginning is fast. However, inserting elements in the middle takes time because elements must be moved.  Deque structure can be depicted as follow:

C++ STL Container deque illustration

  • Deque reallocation occurs when a member function must insert or erase elements of the sequence:

  1. If an element is inserted into an empty sequence, or if an element is erased to leave an empty sequence, then iterators earlier returned by begin() and end() become invalid.

  2. If an element is inserted at the first position of the deque, then all iterators, but no references, that designate existing elements become invalid.

  3. If an element is inserted at the end of the deque, then end() and all iterators, but no references, that designate existing elements become invalid.

  4. If an element is erased at the front of the deque, only that iterator and references to the erased element become invalid.

  5. If the last element is erased from the end of the deque, only that iterator to the final element and references to the erased element become invalid.

  • Otherwise, inserting or erasing an element invalidates all iterators and references.

  • The following general deque example declares a deque for floating-point values, inserts elements from 1.2 to 12 at the front of the container, and prints all elements of the deque:

// a simple deque example

#include <iostream>

#include <deque>

using namespace std;

 

int main()

{

    // deque container for floating-point elements declaration

    deque<float> elem, elem1;

    // insert the elements each at the front

    cout<<"push_front()\n";

    for(int i=1; i<=10; ++i)

    // insert at the front

    elem.push_front(i*(1.2));

    // print all elements separated by a space

    for(i=0; i<elem.size(); ++i)

        cout<<elem[i]<<' ';

    cout<<endl;

    // insert the elements each at the back

    cout<<"\npush_back()\n";

    // insert at the back

    for(i=1; i<=10; ++i)

        elem1.push_back(i*(1.2));

    // print all elements separated by a space

    for(i=0; i<elem1.size(); ++i)

    cout<<elem1[i]<<' ';

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Container deque simple general program example

 

The <deque> Header Members

 

Operators

 

Operator

Description

operator!=

Tests if the deque object on the left side of the operator is not equal to the deque object on the right side.

operator<

Tests if the deque object on the left side of the operator is less than the deque object on the right side.

operator<=

Tests if the deque object on the left side of the operator is less than or equal to the deque object on the right side.

operator==

Tests if the deque object on the left side of the operator is equal to the deque object on the right side.

operator>

Tests if the deque object on the left side of the operator is greater than the deque object on the right side.

operator>=

Tests if the deque object on the left side of the operator is greater than or equal to the deque object on the right side.

 

Table 27.11

 

deque Template Class

 

Class

Description

deque

A template class of sequence containers that arrange elements of a given type in a linear arrangement and, like vectors, allow fast random access to any element and efficient insertion and deletion at the back of the container.

 

Table 27.12

deque Template Class Members

 

Typedefs

 

Typedef

Description

allocator_type

A type that represents the allocator class for the deque object.

const_iterator

A type that provides a random-access iterator that can access and read a const element in the deque.

const_pointer

A type that provides a pointer to a const element in a deque.

const_reference

A type that provides a reference to a const element stored in a deque for reading and performing const operations.

const_reverse_iterator

A type that provides a random-access iterator that can read any const element in the deque.

difference_type

A type that provides the difference between two iterators that refer to elements within the same deque.

iterator

A type that provides a random-access iterator that can read or modify any element in a deque.

pointer

A type that provides a pointer to an element in a deque.

reference

A type that provides a reference to an element stored in a deque.

reverse_iterator

A type that provides a random-access iterator that can read or modify an element in a reversed deque.

size_type

A type that counts the number of elements in a deque.

value_type

A type that represents the data type stored in a deque.

 

Table 27.13

 

deque Template Class Member Functions

 

Member function

Description

assign()

Erases elements from a deque and copies a new set of elements to the target deque.

at()

Returns a reference to the element at a specified location in the deque.

back()

Returns a reference to the last element of the deque.

begin()

Returns an iterator addressing the first element in the deque.

clear()

Erases all the elements of a deque.

deque()

deque constructor, constructs a deque of a specific size or with elements of a specific value or with a specific allocator or as a copy of all or part of some other deque.

empty()

Tests if a deque is empty.

end()

Returns an iterator that addresses the location succeeding the last element in a deque.

erase()

Removes an element or a range of elements in a deque from specified positions.

front()

Returns a reference to the first element in a deque.

get_allocator()

Returns a copy of the allocator object used to construct the deque.

insert()

Inserts an element or a number of elements or a range of elements into the deque at a specified position.

max_size()

Returns the maximum length of the deque.

pop_back()

Deletes the element at the end of the deque.

pop_front()

Deletes the element at the beginning of the deque.

push_back()

Adds an element to the end of the deque.

push_front()

Adds an element to the beginning of the deque.

rbegin()

Returns an iterator to the first element in a reversed deque.

rend()

Returns an iterator that point just beyond the last element in a reversed deque.

resize()

Specifies a new size for a deque.

size()

Returns the number of elements in the deque.

swap()

Exchanges the elements of two deques.

 

Table 27.14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

deque Template Class Operator

 

Operator

Description

operator[ ]

Returns a reference to the deque element at a specified position.

 

Table 27.15

// deque, constructors

#include <deque>

#include <iostream>

using namespace std;

 

int main()

{

    deque <int>::iterator deq0Iter, deq1Iter, deq2Iter, deq3Iter, deq4Iter, deq5Iter, deq6Iter;

    // create an empty deque deq0

    deque <int> deq0;

    // create a deque deq1 with 10 elements of default value 0

    deque <int> deq1(10);

    // create a deque deq2 with 7 elements of value 10

    deque <int> deq2(7, 10);

    // create a deque deq3 with 4 elements of value 2 and with the allocator of deque deq2

    deque <int> deq3(4, 2, deq2.get_allocator());

    // create a copy, deque deq4, of deque deq2

    deque <int> deq4(deq2);

    // deque deq5 a copy of the deq4[_First, _Last) range

    deq4Iter = deq4.begin();

    deq4Iter++;

    deq4Iter++;

    deq4Iter++;

    deque <int> deq5(deq4.begin(), deq4Iter);

    // create a deque deq6 by copying the range deq4[_First, _Last) and the allocator of deque deq2

    deq4Iter = deq4.begin();

    deq4Iter++;

    deq4Iter++;

    deq4Iter++;

    deque <int> deq6(deq4.begin(), deq4Iter, deq2.get_allocator());

    // ------------------------------------

    cout<<"Operation: deque <int> deq0\n";

    cout<<"deq0 data: ";

    for(deq0Iter = deq0.begin(); deq0Iter != deq0.end(); deq0Iter++)

        cout<<*deq0Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq1(10)\n";

    cout<<"deq1 data: ";

    for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

        cout<<*deq1Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq2(7, 3)\n";

    cout<<"deq2 data: ";

    for(deq2Iter = deq2.begin(); deq2Iter != deq2.end(); deq2Iter++)

    cout<<*deq2Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq3(4, 2, deq2.get_allocator())\n";

    cout<<"deq3 data: ";

    for(deq3Iter = deq3.begin(); deq3Iter != deq3.end(); deq3Iter++)

        cout<<*deq3Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq4(deq2);\n";

    cout<<"deq4 data: ";

    for(deq4Iter = deq4.begin(); deq4Iter != deq4.end(); deq4Iter++)

        cout<<*deq4Iter<<" ";

    cout<<endl;

    cout<<"\nOperation1: deq4Iter++...\n";

    cout<<"Operation2: deque <int> deq5(deq4.begin(), deq4Iter)\n";

    cout<<"deq5 data: ";

    for(deq5Iter = deq5.begin(); deq5Iter != deq5.end(); deq5Iter++)

        cout << *deq5Iter<<" ";

    cout << endl;

    cout<<"\nOperation1: deq4Iter = deq4.begin() and deq4Iter++...\n";

    cout<<"Operation2: deque <int> deq6(deq4.begin(), \n"

        "      deq4Iter, deq2.get_allocator())\n";

    cout<<"deq6 data: ";

    for(deq6Iter = deq6.begin(); deq6Iter != deq6.end(); deq6Iter++)

        cout<<*deq6Iter<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Container deque constructor

// *******vector.cp*********

// vector constructors

#include <vector>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int>::iterator vec0Iter, vec1Iter, vec2Iter, vec3Iter, vec4Iter, vec5Iter;

    // create an empty vector vec0

    vector <int> vec0;

    // create a vector vec1 with 10 elements of default value 0

    vector <int> vec1(10);

    // create a vector vec2 with 7 elements of value 13

    vector <int> vec2(7, 13);

    // create a vector vec3 with 5 elements of value 3 and with the allocator of vector vec2

    vector <int> vec3(5, 3, vec2.get_allocator());

    // vector vec4, a copy of vector vec2

    vector <int> vec4(vec2);

    // create a vector vec5 by copying the range of vec4[_First, _Last)

    vector <int> vec5(vec4.begin() + 1, vec4.begin() + 3);

    cout<<"Operation: vector <int> vec0\n";

    cout<<"vec0 data: ";

    for(vec0Iter = vec0.begin(); vec0Iter != vec0.end(); vec0Iter++)

        cout<<" "<<*vec0Iter;

    cout<<endl;

    cout<<"\nOperation: vector <int> vec1(10)\n";

    cout<<"vec1 data: ";

    for(vec1Iter = vec1.begin(); vec1Iter != vec1.end(); vec1Iter++)

        cout<<" "<<*vec1Iter;

    cout<<endl;

    cout<<"\nOperation: vector <int> vec2(7, 13)\n";

    cout<<"vec2 data: ";

    for(vec2Iter = vec2.begin(); vec2Iter != vec2.end(); vec2Iter++)

        cout<<" "<<*vec2Iter;

    cout<<endl;

    cout<<"\nOperation: vector <int> vec3(5, 3, vec2.get_allocator())\n";

    cout<<"vec3 data: ";

    for(vec3Iter = vec3.begin(); vec3Iter != vec3.end(); vec3Iter++)

    cout<<" "<<*vec3Iter;

    cout<<endl;

    cout<<"\nOperation: vector <int> vec4(vec2)\n";

    cout<<"vec4 data: ";

    for(vec4Iter = vec4.begin(); vec4Iter != vec4.end(); vec4Iter++)

    cout<<" "<<*vec4Iter;

    cout<<endl;

    cout<<"\nOperation: vector <int> vec5(vec4.begin()+1, vec4.begin()+3)\n";

    cout<<"vec5 data: ";

    for(vec5Iter = vec5.begin(); vec5Iter != vec5.end(); vec5Iter++)

        cout<<" "<<*vec5Iter;

    cout<<endl;  

    return 0;

}

 

[bodo@bakawali ~]$ g++ vector.cpp -o vector

[bodo@bakawali ~]$ ./vector

 

Operation: vector <int> vec0

vec0 data:

 

Operation: vector <int> vec1(10)

vec1 data:  0 0 0 0 0 0 0 0 0 0

 

Operation: vector <int> vec2(7, 13)

vec2 data:  13 13 13 13 13 13 13

 

Operation: vector <int> vec3(5, 3, vec2.get_allocator())

vec3 data:  3 3 3 3 3

 

Operation: vector <int> vec4(vec2)

vec4 data:  13 13 13 13 13 13 13

 

Operation: vector <int> vec5(vec4.begin()+1, vec4.begin()+3)

vec5 data:  13 13

 

// ********deque.cpp*********

// deque, constructors

#include <deque>

#include <iostream>

using namespace std;

 

int main()

{

    deque <int>::iterator deq0Iter, deq1Iter, deq2Iter, deq3Iter, deq4Iter, deq5Iter, deq6Iter;

    // create an empty deque deq0

    deque <int> deq0;

    // create a deque deq1 with 10 elements of default value 0

    deque <int> deq1(10);

    // create a deque deq2 with 7 elements of value 10

    deque <int> deq2(7, 10);

    // create a deque deq3 with 4 elements of value 2 and with the allocator of deque deq2

    deque <int> deq3(4, 2, deq2.get_allocator());

    // create a copy, deque deq4, of deque deq2

    deque <int> deq4(deq2);

    // deque deq5 a copy of the deq4[_First, _Last) range

    deq4Iter = deq4.begin();

    deq4Iter++;

    deq4Iter++;

    deq4Iter++;

    deque <int> deq5(deq4.begin(), deq4Iter);

    // create a deque deq6 by copying the range deq4[_First, _Last) and the allocator of deque deq2

    deq4Iter = deq4.begin();

    deq4Iter++;

    deq4Iter++;

    deq4Iter++;

    deque <int> deq6(deq4.begin(), deq4Iter, deq2.get_allocator());

    // ------------------------------------

    cout<<"Operation: deque <int> deq0\n";

    cout<<"deq0 data: ";

    for(deq0Iter = deq0.begin(); deq0Iter != deq0.end(); deq0Iter++)

        cout<<*deq0Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq1(10)\n";

    cout<<"deq1 data: ";

    for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

        cout<<*deq1Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq2(7, 3)\n";

    cout<<"deq2 data: ";

    for(deq2Iter = deq2.begin(); deq2Iter != deq2.end(); deq2Iter++)

    cout<<*deq2Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq3(4, 2, deq2.get_allocator())\n";

    cout<<"deq3 data: ";

    for(deq3Iter = deq3.begin(); deq3Iter != deq3.end(); deq3Iter++)

        cout<<*deq3Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: deque <int> deq4(deq2);\n";

    cout<<"deq4 data: ";

    for(deq4Iter = deq4.begin(); deq4Iter != deq4.end(); deq4Iter++)

    cout<<*deq4Iter<<" ";

    cout<<endl;

    cout<<"\nOperation1: deq4Iter++...\n";

    cout<<"Operation2: deque <int> deq5(deq4.begin(), deq4Iter)\n";

    cout<<"deq5 data: ";

    for(deq5Iter = deq5.begin(); deq5Iter != deq5.end(); deq5Iter++)

        cout << *deq5Iter<<" ";

    cout << endl;

    cout<<"\nOperation1: deq4Iter = deq4.begin() and deq4Iter++...\n";

    cout<<"Operation2: deque <int> deq6(deq4.begin(), \n"

        "      deq4Iter, deq2.get_allocator())\n";

    cout<<"deq6 data: ";

    for(deq6Iter = deq6.begin(); deq6Iter != deq6.end(); deq6Iter++)

        cout<<*deq6Iter<<" ";

    cout<<endl;

    return 0;

}

 

[bodo@bakawali ~]$ g++ deque.cpp -o deque

[bodo@bakawali ~]$ ./deque

 

Operation: deque <int> deq0

deq0 data:

 

Operation: deque <int> deq1(10)

deq1 data: 0 0 0 0 0 0 0 0 0 0

 

Operation: deque <int> deq2(7, 3)

deq2 data: 10 10 10 10 10 10 10

 

Operation: deque <int> deq3(4, 2, deq2.get_allocator())

deq3 data: 2 2 2 2

 

Operation: deque <int> deq4(deq2);

deq4 data: 10 10 10 10 10 10 10

 

Operation1: deq4Iter++...

Operation2: deque <int> deq5(deq4.begin(), deq4Iter)

deq5 data: 10 10 10

 

Operation1: deq4Iter = deq4.begin() and deq4Iter++...

Operation2: deque <int> deq6(deq4.begin(),

      deq4Iter, deq2.get_allocator())

deq6 data: 10 10 10

 

 

----------------------------------------------------End of C++ deque----------------------------------------------

---www.tenouk.com---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ Container related reading:

 

  1. The source code for this tutorial is available in C++ STL Container source code.

  2. A complete C & C++ Standard Library documentation that includes STL.

  3. Check the best selling C / C++ books at Amazon.com.

 

 

 

 

 

|< C++ STL Container 3 | Main | C++ STL Container 5 >| Site Index | Download |


C++ STL Container Classes:  Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11