Vector or Deque? (intermediate)


Match word(s).

If you have any questions or comments,
please visit us on the Forums.

FAQ > Prelude's Corner > Vector or Deque? (intermediate)

This item was added on: 2003/11/26

Vector or Deque?
More often than not, we recommend that a C++ programmer prefer the STL over hard coded arrays. This is because the vector and deque classes (those that resemble the functionality of an array most closely) are safer and easier to use. Here are some of the advantages to using a vector:

  • A vector manages its own memory. This is a wonderful feature because now you as the programmer need not worry about allocating enough memory or resizing an array if you run out of space. This is probably the biggest advantage to using a vector over an array, the vector will grow as required and destroy itself.

  • A vector has boundary checking with use of the at() member function. One of the biggest problems arrays have is that the random access with the [] operators allow an out of bounds index to be dereferenced. This is generally a Bad Thing and if you can avoid it you should. Granted, many programmers will opt to use the [] operator with vectors if they are confident in not going out of bounds, but if a slight slowdown is acceptable and added security is required, vectors offer an excellent alternative.

  • A vector has useful member functions for working with it.

  • A vector has more natural syntax when used with STL algorithms, arrays can be used but the syntax tends to be messy.

Here is an example of a program that uses an array and the equivalent program with a vector:


#include <iostream> 
#include <string> 
#include <algorithm> 
#include <new> 
#include <cstdlib> 

using std::cout;      
using std::cin;
using std::string;

int main()
{
 int size = 1;
 string *name_list = 0;

 string input;
 try {
   while ( cin>>input ) {
     string *temp = new string[size];

     for ( int j = 0; j < size - 1; ++j )
       temp[j] = name_list[j];

     name_list = temp;
     name_list[size - 1] = input;

     ++size;
   }
 }
 catch ( std::bad_alloc &ex ) {
   std::cerr<< ex.what() <<std::endl;
   exit ( EXIT_FAILURE );
 }

 std::copy ( &name_list[0], &name_list[size - 1],
   std::ostream_iterator<string>(cout, "\n" ) );

 delete [] name_list;

 return 0;
}


As you can imagine, this program is not only error prone, but it is also difficult to follow because of the memory handling and indexing tricks needed to get the program working. Granted, this could be written better with plenty of time to work on it, but often we don't have time. Here is a program that functions exactly the same except it makes use of std::vector:


#include <iostream> 
#include <string> 
#include <algorithm> 
#include <vector> 

using std::cout;      
using std::cin;
using std::string;    
using std::vector;

int main()
{
 vector name_list;

 string input;
 while ( cin>>input )
   name_list.push_back ( input );

 std::copy ( name_list.begin(), name_list.end(),
   std::ostream_iterator(cout, "\n" ) );

 return 0;
}


Notice that several variables have been removed, all of the problematic memory allocation and deallocation, copying, indexing, and tricks with the size have been removed as well and replaced by one line of code: name_list.push_back ( input );. Since std::vector handles its own memory in creation, usage, and destruction, we don't have to worry about it and can simply use the member function that inserts a new item at the end of the vector, push_back(). Also noticed that the address of the vector and the index isn't required for use with std::copy, std::vector offers two members that designate the beginning of the vector, and one item past the end. This simplifies and cleans up the syntax of std::copy. All in all, by using std::vector, we made the program smaller, safer, easier to understand, easier to modify, and all around more robust. What about a deque? The nice thing about a deque is that the usage is pretty much the same as vector:


#include <iostream> 
#include <string> 
#include <algorithm> 
#include <deque> 

using std::cout;      
using std::cin;
using std::string;    
using std::deque;

int main()
{
 deque name_list;

 string input;
 while ( cin>>input )
   name_list.push_back ( input );

 std::copy ( name_list.begin(), name_list.end(),
   std::ostream_iterator(cout, "\n" ) );

 return 0;
}


You'll notice that the only difference between this program and the one using a vector is that the word vector has been replaced with the word deque. It's just that simple, what a vector can do is also what a deque can do, but a deque is the better data structure for reasons which we will describe in just a moment.

Since both a deque and vector are so similar, why have them both? Isn't the choice of which to use really arbitrary? The answer is no, a deque is superior to a vector in both usage and underlying implementation. Here are the big differences:

  • A vector can only add items to the end efficiently, any attempt to insert an item in the middle of the vector or at the beginning can be and often is very inefficient. A deque can insert items at both the beginning and then end in constant time, O(1), which is very good. Insertions in the middle are still inefficient, but if such functionality is needed a list should be used. A deque's method for inserting at the front is push_front(), the insert() method can also be used, but push_front is more clear.

  • Just like insertions, erasures at the front of a vector are inefficient, but a deque offers constant time erasure from the front as well.

  • A deque uses memory more effectively. Consider memory fragmentation, a vector requires N consecutive blocks of memory to hold its items where N is the number of items and a block is the size of a single item. This can be a problem if the vector needs 5 or 10 megabytes of memory, but the available memory is fragmented to the point where there are not 5 or 10 megabytes of consecutive memory. A deque does not have this problem, if there isn't enough consecutive memory, the deque will use a series of smaller blocks.

  • A vector has two drawback methods, reserve() and capacity(), which can be used to improve efficiency by reserving a certain amount of memory before using the vector so that calls to push_back() or insert() will not result in many time intensive allocations. How is this a drawback? The implementation of a deque is efficient enough with allocations to not need these methods. Generally, if the programmer must help the data structure with its memory allocations to be more efficient then something is wrong with the data structure.

In conclusion, either a vector or a deque should be used in place of an array, that much is assured. The question of whether to use a vector or a deque is more difficult, a vector is faster than a deque, but a deque offers several advantages over a vector, especially for large lists of items. The C++ standard recommends that you prefer a vector unless you need to insert and delete at the end of the list in which case you should prefer a deque. I disagree and feel that a deque should be used if the list of items has any chance of being very large, whether you need insertions and erasure at the beginning or not. If the list will be short and you don't need to insert or delete at the front then a vector is the more efficient choice, but if the list is short then efficiency really isn't a factor. With these arguments in mind for both vector and deque, you can make your own decisions of which is the better choice for each situation.

Have fun!

Script provided by SmartCGIs