Other STL Containers
As we learned in an earlier lecture, a deque is a double ended queue. A deque acts like either a queue or a stack except that it performs these tasks at both ends of the deque. The deque is one of the standard containers in the STL. It can be implemented by including the header like the following:
 |
#include<deque>
|
In some ways you may consider the STL deque as a variation of the STL vector. Like a vector, it supports random access using the [ ] operator. However unlike a vector, a deque can be accessed at the front as well as the back. It is similar to what might be considered a double-ended vector.
The features included in the STL deque go beyond the ADT deque. For example the STL deque permits access to any element of the deque using the [ ] operator. Like the STL vector, the STL deque permits insertion and removal of an element at any place in the deque.
Memory is allocated different for vectors and deques. A vector always occupies a contiguous region of memory. If a vector grows too large, it may need to be moved to a new location where it will fit. A deque, on the other hand, can be stored in several noncontiguous areas; i.e. it is segmented. You will recall that the vector member function capacity( ), returns the largest number of elements that a vector can store without being moved, but capacity( ) is not defined for deques because deques do not need to be moved.
There is only one constructor for a deque to be concerned with and a deque object would be defined like the following:
|
deque<double> a_deque;
|
Actually deque has several constructors as described in the following table that shows their prototypes:
|
| Constructor | Purpose |
|---|---|
| deque( ); | Creates an empty deque object of the specified data type. |
| deque(long n); | Creates a deque object of the specified data type with capacity for n elements. |
| deque(long n, datatype val); | Creates a deque object of the specified data type with n copies of the data element val of type datatype‥ |
| deque(const vector &v); | Creates a deque object of the specified data type with a copy of all of the elements in the vector v; |
| deque(datatype* firstptr, datatype* lastptr) | Creates a deque object of the specified data type that contains copies of elements in the memory locations from iterator: firstptr up to iterator: lastptr. |
Open table as spreadsheet |
Using these constructors, deques could have definitions like the following:
|
deque<short> v1; // creates an empty short deque v1 // deque<double> v2(20); // creates a double deque v2 // with a capacity for 20 doubles. // deque<long> v3(5,3443); // creates a long deque v3 // with 5 copies of 3443. // deque<long> v5(v3); // creates a long deque v5 that contains // a copy of all of the data in v3. // deque<char> v4(ptr,ptr+4); // creates a char deque v4 whose elements // are the chars beginning at the address // contained in the iterator ptr and going to // the address contained in the iterator ptr + 4. //
|
Some of the deque member functions are the following:
|
| Function | Purpose |
|---|---|
| begin( ) | Returns an iterator to the beginning of the deque for iterating forward through the deque. |
| end( ) | Returns an iterator to past-the-end location of the deque used to move from the end toward the beginning. |
| rbegin( ) | Returns a reverse iterator to the end of the container for iterating backward through the deque. |
| rend( ) | Returns a reverse iterator to the beginning of the deque, used to end backward iteration. |
| empty( ) | Returns true if no elements and false otherwise. |
| size( ) | Returns the number of elements in the deque. |
| front( ) | Returns the element at the front of the deque. |
| back( ) | Returns the element at the back of the deque. |
| push_front(theElement) | Adds theElement to the deque at the front. |
| push_back(theElement) | Adds theElement to the deque at the back. |
| pop_back( ) | Removes an element from the back. |
| pop_front( ) | Removes an element from the front. |
| deque2.swap(deque1) | Interchanges the elements of deque1 with the elements of deque2. |
| insert( ) | Inserts an element into a deque . |
| erase( ) | Removes an element from a deque. |
|
As discussed above, notice that there is no capacity( ) for deque. In addition to the above member functions, deque supports the following operators:
|
| Operator |
|---|
| ==( ) |
| <( ) |
| =( ) |
| [ ] |
| *( ) |
| +( ) |
| -( ) |
| ++( ) |
| --( ) |
| +=( ) |
| -=( ) |
|
Remember that the deque as with the vector will only work on those data types that support the operations of the deque. For an example of a deque, check out: deque.cpp and deque2.cpp.
In addition to the deque, STL also supports the stack as a container. To use the STL stack would require that you include the stack header as in the following:
|
#include<stack>
|
Since the stack is also based on template classes to define an instance you would include a statement like the following:
|
stack<long> a_stack;
|
The stack member functions are the following:
|
| Function | Purpose |
|---|---|
| ==( ) | Compares to stacks. |
| <( ) | Determines which stack is larger. |
| empty( ) | Returns true if the stack is empty and false otherwise. |
| size( ) | Returns the number of elements in the stack. |
| push(theElement) | Pushes an element theElement onto the stack. |
| pop( ) | Removes the top element from the stack. |
| top( ) | Returns a copy of the top element of the stack. |
|
Notice that the [ ] operator is not listed above. It is not activated on the STL stack. For an example we will return to the factorization problem. Click on, new_factor.cpp. Notice in this example, we did not need to specify the maximum size of the stack since we are not using an array as in a previous example.
The STL also has a queue container. To use the STL queue requires the following:
|
#include<queue>
|
Since the queue is also based on template classes, to define an instance you would include a statement like the following:
|
queue<long> a_queue;
|
The member functions are the following:
|
| Function | Purpose |
|---|---|
| ==( ) | Determines whether the two queues are the same. |
| <( ) | Compares two queues. |
| empty( ) | Returns true if no elements and false otherwise. |
| size( ) | Returns the number of elements in the queue. |
| front( ) | Returns a copy of the front element of the queue. |
| back( ) | Returns a copy of the back element of the queue. |
| push(theElement) | Adds theElement to the back of the queue. |
| pop( ) | Removes the first element from the front of the queue. |
|
For an example see: new_queue.cpp (this example uses the header: date.h). This example is a rewrite of the Date queue from an example seen earlier in the lecture notes. Notice that some of the functions had to have their names changed in our example and there is no need to test to determine if the queue is full. Since the STL queue is not based on an array and the [ ] operator is not available on the STL queue, the function to display all of the elements has been removed as well.
EAN: N/A
Pages: 142