Page 1 of 1

C++ Deque Tutorial all about the construction and usage of the std::deque STL container Rate Topic: ****- 2 Votes

#1 jjhaag  Icon User is offline

  • me editor am smartastic
  • member icon

Reputation: 45
  • View blog
  • Posts: 1,789
  • Joined: 18-September 07

Posted 14 October 2007 - 03:09 PM

std::deque Tutorial


Introduction
Deques are one of the many standard template library (STL) containers available in C++. Their name suggests a good deal about their intended usage and what is possible with them. They are containers, meaning that they are designed to hold multiple data elements. They are templates, meaning that the constructors and methods have all been templatized, allowing for the use of any of the standard C++ data types, as well as user defined classes with the proper constructors defined. And the name of the template itself stands for double ended queue, implying behavior similar to a queue, except with fast access from both ends of the container. This tutorial will attempt to address all of the methods available for the deque container. Since many of the methods are also available for other STL containers, learning the syntax and usage of deques should provide a good start for figuring out some of the other elements of the STL.



Declaration/Instantiation
Several constructors are defined for the deque template. Their syntax and example code are given below:
deque();				   //default constructor
deque<int> dq1;			//produces empty deque of ints

deque(const deque& d );	//copy constructor
deque<int> dq2(dq1);	   //creates a copy of dq1 in dq2
	
	
deque(size_type number, const T& value=T() );	//initialization construction
deque<double> dq3(10);	 //deque of doubles with 10 elements set to default (0.0)
deque<double> dq4(5, 8.1); //deque of doubles with 5 elements set to 8.1


deque(iterator start, iterator end );	 //interator constructor
double array1[]={0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0};
deque<double> dq5(array1,array1+4);	   //constructs deque with elements 0-3 from array1


The first example is the default constructor, which results in the creation of an empty deque capable of holding the int data type. The second is the copy constructor, which creates an element-by-element copy of the deque d. The third creates a deque with number elements, and initializes each element to value, or to the default value of the type T if the value is not specified. The fourth creates a deque from another container or array, assigning the values between the iterators start and end. The iterator method results in a deque that is endstart elements long, beginning with start; the element specified by end is not included in the new object. Once we’ve looked at a couple of the other methods of the deque template, especially the iterator methods, we will see why.

Deques are not limited to just the builtin datatypes in C++. They are templatized to also any class or template with the proper constructors or iterators to be used as the data type.



Accessing and Assigning Single Elements: at(), front(), back()
One of the great benefits of the STL containers is that they are access safe, meaning that unlike the case with raw arrays, overshooting the end of the container will result in an exception being thrown, that can be caught within a try/catch statement. This is in constrast to raw arrays, where overshooting will result in the return of garbage data and possibly more serious problems. Accessing single elements from a deque safely involves the use of the at() member. Deque elements can also be accessed using the [] operator, but there is no boundary checking for the [] operator, which can result in garbage data being returned:
#include <iostream>
#include <stdexcept>	//required for defining and catching standard exceptions
#include <deque>

using namespace std;

int main() {
	//deque of doubles with 5 elements set to 8.1
	deque<double> dq(5, 8.1);

	for (int i=0; i<=5; ++i) {
		cout << "Element "<< i << " accessed with [] : "<< dq[i]<< endl;
	}

	try {
		cout << "Element " << i << " accessed with at(i) :" << dq.at(i) << endl;
	} catch (out_of_range&) {
		cout << "**out of range exception accessing element " << i << " with at() **" << endl;
	}

	return 0;
}


Like raw arrays, indices into deques range from 0 to number_of_elements-1. So while the [] approach will output some value from element 5 as if there isn’t a problem, the at() method results in the throwing of the out_of_range exception.

The at(index) method returns a reference to the element at index, meaning that the element in that position can be modified:
#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<double> dq(5, 8.1);

	//  change the value in element 2
	dq.at(2)=9.5;

	for (int i=0; i<5; ++i) cout << dq.at(i) << " ";
	cout << endl;

	return 0;
}


Two other methods are useful when the element to be accessed is in either the first or the last position in the deque. front() returns a modifiable reference to the first element, while back() returns a reference to the last element. When used as actual double-ended queues, rather than as random-access containers, front() and back() become very important methods, since the first and last elements in true double-ended queues have priority.



Container Information: size(), max_size(), empty()
There are three deque methods that allow the programmer or program to get information about the state of the deque. These are the size(), empty() and max_size() methods.

size() returns the number of elements currently contained in the deque. It is useful for setting boundaries in simple access/modifier loops without the need for extensive exception handling with unwieldy try-catch statements. empty() returns true if the deque holds no elements, and false otherwise. This is a useful method to call at the start of operations that remove elements from the container (more on these later), since a deletion operation on an empty deque will cause exceptions to be thrown.

max_size() returns a system and architecture dependant value. The upper limit for the size of a deque is related to maximum addressable memory space. On my 32-bit system, max_size() returns 2^32-1, which is the theoretical limit of the addressable memory space on a standard 32-bit machine. Support for greater addressable space also depends on the compiler; on my x64 system, the same value is returned for max_size() when I use the same compiler as on the 32-bit system.
#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<double> dq(5, 8.1); //deque of doubles with 5 elements set to 8.1
	
	cout << "Size of deque:		 " << dq.size() << endl;
	cout << "Is the deque empty?	" << ( (dq.empty()) ? ("Yes") : ("No")) << endl;
	cout << "Maximum size of deque: " << dq.max_size() << endl;
	
	return 0;
}


Unlike the STL vector container, there is no method reserve() for deques. This has to do with the fact that the underlying structure for a deque is more akin to a linked list than to a raw array. Deque elements are stored in small chunks of memory rather than in a continuous block as in vectors; additional memory can be allocated for the deque by allocating additional chunks, rather than having to reallocate space for the entire container all at once.



Adding or Removing Single Elements :push_front(), push_back(), pop_front(), pop_back()
The deque is designed to provide fast insertions and deletions at both ends of the container. The two insertion methods are push_front() and push_back(), and the two deletion methods are pop_front() and pop_back(). Push methods insert an element at either the back or the front of the deque, while pop methods remove an element:
#include <iostream>
#include <deque>

using namespace std;

int main() {
	
	//  create an empty deque and fill with ints using push_back()
	deque<int> dq;
	for (int i=0; i<5; ++i) {
		dq.push_back(i);
	}
	
	//  display to screen
	for (int i=0; i<(signed)dq.size(); ++i) cout << dq.at(i);
	cout << endl;
	
	//  add 3 copies of the number 8 to the front of the deque using push_front()
	for (int i=0; i<3; ++i) {
		dq.push_front(8);
	}
	
	//  display to screen
	for (int i=0; i<(signed)dq.size(); ++i) cout << dq.at(i);
	cout << endl;
	
	//  remove first and last elements with pop_back() and pop_front()
	dq.pop_front();
	dq.pop_back();
	
	//  display to screen
	for (int i=0; i<(signed)dq.size(); ++i) cout << dq.at(i);
	cout << endl;
	
	return 0;
}


These methods are most useful when you are trying to use the deque as an actually double-ended queue, rather than an all-purpose container. Normal priority objects can be inserted using push_back(), while high priority objects (ones requiring immediate use or attention) can be pushed into the front of the queue. This can be a benefit in the use of the deque over the standard, single-ended queue container, where no prioritization during the push process is possible.


Adding or Removing Multiple Elements: insert(), erase(), assign(), resize(), swap(), clear()
The two methods most frequently called for performing multiple-element insertions and deletions are, not surprisingly, named insert() and erase(). Both of these methods require the use of iterators, which behave much like pointers do for raw arrays. The syntaxes for the insert() method are given by:
iterator insert( iterator location, const T& value );
void insert( iterator location, size_type number, const TYPE& val );
template<T> void insert( iterator location, input_iterator start, input_iterator end );


The first method inserts the element given by value at the position given by the iterator location. The second method is similar, except it inserts number copies at the specified location, rather than just a single element. The final method inserts the elements between start and end at the position just before location. In this case, the input iterators can be iterators to different deques, or in fact any different type of container or raw array with a compatible data type:
#include <iostream>
#include <deque>

using namespace std;

int main() {
	
	//  declare raw array of ints
	int array[]= { 0, 1, 2, 3, 4 };

	deque<int> dq;
	
	//  populate deque by push_back'ing some numbers
	for (long i=0; i<5; ++i) {
		dq.push_back(i*10);
		cout << dq.at(i) << " ";
	}
	cout << endl;
	
	//  insert the array using iterators
	dq.insert(dq.begin()+2, array, array+5);

	for (long i=0; i<(long)dq.size(); ++i) {
		cout << dq.at(i) << " ";
	}
	cout << endl;
	
	//  insert 3 copies of the number 0
	dq.insert(dq.begin()+4, 3, 0);
	
	for (long i=0; i<(long)dq.size(); ++i) {
		cout << dq.at(i) << " ";
	}
	cout << endl;
	
	return 0;
}


This code introduces one more deque method: begin(). This method returns a random access interator to the first element of the deque. The offsets specified by dq.begin()+i follow the same rules as ordinary pointer arithmetic; position i is refered to by the base address of the deque ( specified by begin() ) plus an offset of i to get to element i. Notice the equivalent use of pointers and pointer arithmetic as iterators to raw arrays in the insertion of the raw array into the deque.

The syntaxes for the erase() method are given by:
iterator erase( iterator location );
iterator erase( iterator start, iterator end );


The first method deletes the single element found at the position location, while the second deletes the elements between the locations specified by start and end:
#include <iostream>
#include <deque>

using namespace std;

int main() {

	deque<int> dq;

	//  populate deque by push_back'ing some numbers
	for (long i=0; i<20; ++i) {
		dq.push_back(i);
		cout << dq.at(i) << " ";
	}
	cout << endl;

	//  erase the next-to-last element
	dq.erase(dq.end()-2);

	for (long i=0; i<(long)dq.size(); ++i) {
		cout << dq.at(i) << " ";
	}
	cout << endl;

	//  erase the first three elements
	dq.erase(dq.begin(),dq.begin()+3);

	for (long i=0; i<(long)dq.size(); ++i) {
		cout << dq.at(i) << " ";
	}
	cout << endl;

	return 0;
}


This code also introduces a new element – the end() method. This method returns an interator just past the last element of the deque. This is not the last element of the deque, mind you, but the position just past the last element. More on this in a moment, when I will finally get back to some statements I made when discussing the constructors for deques.

Four other methods deal with multiple elements of a deque in one statement. These are assign(), resize(), swap(), and clear().

assign() allows for a complete restructuring of the deque to contain the elements of the assigned container, and results in the loss of the data formerly contained in the container. The syntax for assign is given by:
void assign( size_type number, const T& value );
void assign( input_iterator start, input_iterator end );


The first resizes the deque to contain number values, and sets all of their values to value.

resize(size_type number, const T& value = T()) changes the number of elements in a deque, as implied by the name. If the new number of elements is greater than the current number returned by size(), the new elements are all intialized to value, or to the default value for the type T if value is not specified. If the new number of elements is smaller than the current number of elements, the trailing elements are truncated.

swap(container& source) exchanges the contents of one deque with the contents of another. Simple as that.

clear() removes all of the elements from the deque, erasing the data and freeing memory. Following a call to clear(), size() will return 0.

The following code demonstrates the usage and syntax of these four functions in action:
#include <iostream>
#include <deque>

using namespace std;

int main() {
	
	//  declare two deques and intialize the second to contain 10 zeros
	deque<int> dq1;
	deque<int> dq2(10,0);
	
	//  assign 10 copies of the int 5 to deque 1
	dq1.assign(10,5);
	
	
	//  output each deque
	cout << "deque 1: ";
	for (long i=0; i<(long)dq1.size(); ++i) cout << dq1.at(i) << " ";
	cout << endl;
	
	cout << "deque 2: ";
	for (long i=0; i<(long)dq2.size(); ++i) cout << dq2.at(i) << " ";
	cout << endl;
	
	
	//  resize deque 1
	dq1.resize(15,10);

	
	//  output each deque
	cout << "deque 1: ";
	for (long i=0; i<(long)dq1.size(); ++i) cout << dq1.at(i) << " ";
	cout << endl;
	
	cout << "deque 2: ";
	for (long i=0; i<(long)dq2.size(); ++i) cout << dq2.at(i) << " ";
	cout << endl;
	
	
	//  swap contents of the deques
	dq1.swap(dq2);
	
	
	//  output each deque
	cout << "deque 1: ";
	for (long i=0; i<(long)dq1.size(); ++i) cout << dq1.at(i) << " ";
	cout << endl;
	
	cout << "deque 2: ";
	for (long i=0; i<(long)dq2.size(); ++i) cout << dq2.at(i) << " ";
	cout << endl;
	
	
	//  clear deque 1
	dq1.clear();
	
	cout << "after clear(), size of deque 1 is now " << dq1.size() << " elements.";
	
	return 0;
} 




Iterator Methods: begin(), end(), rbegin(), rend()
At several points in this tutorial, the concept of an iterator has been brought up. Iterators are powerful tools associated with the various STL container classes, deserving of a tutorial unto themselves. However, several deque methods require them, so at least a cursory understanding of them is required to properly manipulate deques.

Iterators are the pointers of the container world. They essentially reference addresses that the various elements of a container are stored at. However, because of different memory allocation schemes, they must be somewhat smarter than pointer in order to function properly. In analogy to pointer usage with arrays, they can be incremented to run through the elements of a container, with the element i of a container given by the base address of the container plus the offset i. They can also be dereferenced to return a modifiable reference to the element at the specified position. Deque iterators are random access interators, meaning that they can be incremented, decremented, and used with pointer arithmetic. Other types of iterators exist, but they are all less powerful than random access iterators, and generally less applicable to the deque container.

The four deque methods that focus on iterators are begin(), end(), rbegin(), and rend(). The first two have already been covered, but only very briefly, so we’ll deal with them first.

begin() returns an iterator to the first element of a deque, and end() returns and iterator to the point just past the end of the queue. Although it might seem to make sense to return an iterator to the last element instead, the syntax of end() allows one to use it as the stop condition in loops as follows:
deque<int> dq(10,5);

for (deque<int>::iterator itr=dq.begin(); itr!=dq.end(); ++itr) {
...


If end() returned the last element, the above code would skip the final element in the container.

The position of end just beyond the end of the deque also explains the behavior of the constructors and insertion and deletion methods that have iterators as arguments. The iterator-based constructor has the syntax deque(iterator start, iterator end), and in the first section I mentioned that the created object contains the elements found between start and end, excluding the element found at end. This allows the following syntax to be valid:
deque<int> dq2(dq1.begin(), dq1.end());
This code will create a new deque dq2 containing all of the elements of dq1. It also allows for the insert() method to be able to add elements before or after any position in the deque. Insertions before the first element use begin() as the location, while insertions after the last element use end().

The methods rbegin() and rend() are identical to the begin() and end() methods, except they return reverse iterators. Reverse iterators are similar to random-access iterators, except that the increment and decrement operations are reversed from the behavior associated with random-access iterators, and the directionality of the deque appears to be reversed when using them (first element appears to be in the last position and vice versa). They are convenient for creating new deque objects or performing insertions of elements where the elements are reversed:
#include <iostream>
#include <deque>

using namespace std;

int main() {
	
	//  declare a deque object, fill with a series of ints, and display
	deque<int> dq1;
	
	for (long i=0; i<10; ++i) dq1.push_back(i);
	
	cout << "dq1: ";
	for (long i=0; i<(long)dq1.size(); ++i) cout << dq1.at(i) << " ";
	cout << endl;
	
	//  create a new deque, reversing dq1 by using reverse iterators
	deque<int> dq2(dq1.rbegin(), dq1.rend());
	
	//  create a new deque using normal random-access iterators
	deque<int> dq3(dq1.begin(), dq1.end());
	
	
	//  display the new deques
	cout << "dq2: ";
	for (long i=0; i<(long)dq2.size(); ++i) cout << dq2.at(i) << " ";
	cout << endl;
	
	cout << "dq3: ";
	for (long i=0; i<(long)dq3.size(); ++i) cout << dq3.at(i) << " ";
	cout << endl;
	
	return 0;
	
}





Performance Issues
The deque container is generally chosen when a random-access container is required that allows for good performance in insertion/deletion operations at locations other than at the end of the container. Because they are based on an underlying structure of a linked list, there is no requirement for a reserve() method to allocate an as-of-yet unused block of memory, as there is in the case of the std::vector container. Upon an increase in size, instead of having to allocate a huge block of memory and copy the entire container into it, the deque simply allocates a new smaller block and adjusts the internal pointer linking as necessary to provide serial access. Because of this memory allocation strategy, the use of a vector instead of a deque where many insertions or deletions are required can result in over a hundredfold increase in computation time for these operations. However, insertions or deletion speeds at the end of the container are generally comparable between the two containers, as long as no more memory must be allocated for the vector.

However, the underlying structure of the deque results in slower random access than in vectors. On my test machine, it can take more than twice the time to access the same number of elements from a deque than from a vector. This is because the std::vector container is based essentially on a raw array, so moving from one element to another is a relatively simple matter of defining offsets from the base address of the private data, whereas in the std::deque accessing a particular element requires a determination of which memory block the element is in, as well as the offset from the start of the block.

If performance is a critical aspect of your program, you should probably consider the performance limitations inherent in each of these containers. A couple of trial runs using each of the container types may prove beneficial. Using a #define container vector or #define container deque and using container as the name for the general container template in your code can work, though posting such code would probably cause a few people’s heads to explode, since macros are pretty unpopular in most of the C++ world. However, if you’re doing a lot of insertions/deletions, the deque is probably the way to go; save the use of vectors when you need random access to a relatively constant-sized container.



That’s all for now. I hope that this helps to clarify the syntax and usage of the std::deque container, and provide some insight as to whether or not it is the proper container choice for your application.

Is This A Good Question/Topic? 0
  • +

Replies To: C++ Deque Tutorial

#2 born2c0de  Icon User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 180
  • View blog
  • Posts: 4,667
  • Joined: 26-November 04

Posted 15 October 2007 - 05:10 AM

Nicely done.
:^:
Was This Post Helpful? 0
  • +
  • -

#3 nirvanarupali  Icon User is offline

  • D.I.C Stomach
  • member icon

Reputation: 13
  • View blog
  • Posts: 1,119
  • Joined: 01-August 07

Posted 17 October 2007 - 07:43 PM

That's great tutorial man. I hope you can also write on <map> containter. :^:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1