Section 9.7. Container Adaptors


9.7. Container Adaptors

In addition to the sequential containers, the library provides three sequential container adaptors: queue, priority_queue, and stack. An adaptor is a general concept in the library. There are container, iterator, and function adaptors. Essentially, an adaptor is a mechanism for making one thing act like another. A container adaptor takes an existing container type and makes it act like a different abstract type. For example, the stack adaptor takes any of the sequential containers and makes it operate as if it were a stack. Table 9.22 (p. 350) lists the operations and types that are common to all the container adaptors.

Table 9.22. Common Adaptor Operations and Types

size_type

Type large enough to hold size of largest object of this type.

value_type

Element type.

container_type

Type of the underlying container on which the adaptor is implemented.

A a;

Create a new empty adaptor named a.

A a(c);

Create a new adaptor named a with a copy of the container c.

Relational Operators

Each adaptor supports all the relational operators: ==, !=, <, <=, >, >=.


Exercises Section 9.6.5

Exercise 9.40:

Write a program that accepts the following two strings:

      string q1("When lilacs last in the dooryard bloom'd");      string q2("The child is father of the man"); 

Using the assign and append operations, create the string

      string sentence("The child is in the dooryard"); 

Exercise 9.41:

Write a program that, given the strings

      string generic1("Dear Ms Daisy:");      string generic2("MrsMsMissPeople"); 

implements the function

      string greet(string form, string lastname, string title,                   string::size_type pos, int length); 

using the replace operations, where lastname replaces Daisy and pos indexes into generic2 of length characters replacing Ms. For example, the following

      string lastName("AnnaP");      string salute = greet(generic1, lastName, generic2, 5, 4); 

returns the string

      Dear Miss AnnaP: 


To use an adaptor, we must include its associated header:

      #include <stack>    // stack adaptor      #include <queue>    // both queue and priority_queue adaptors 

Initializing an Adapator

Each adaptor defines two constructors: the default constructor that creates an empty object and a constructor that takes a container and makes a copy of that container as its underlying value. For example, assuming that deq is a deque<int>, we could use deq to initialize a new stack as follows:

      stack<int> stk(deq);      // copies elements from deq into stk 

Overriding the Underlying Container Type

By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector. We can override the default container type by naming a sequential container as a second type argument when creating the adaptor:

      // empty stack implemented on top of vector      stack< string, vector<string> > str_stk;      // str_stk2 is implemented on top of vector and holds a copy of svec      stack<string, vector<string> > str_stk2(svec); 

There are constraints on which containers can be used for a given adapator. We can use any of the sequential containers as the underlying container for a stack. Thus, a stack can be built on a vector, list, or deque. The queue adapator requires push_front in its underlying container, and so could be built on a list but not on a vector. A priority_queue requires random access and so can be built on a vector or a deque but not on a list.

Relational Operations on Adaptors

Two adaptors of the same type can be compared for equality, inequality, less-than, greater-than, less-than-equal, and greater-than-equal relationships, provided that the underlying element type supports the equality and less-than operators. For these operations, the elements are compared in turn. The first pair of unequal elements determines the less-than or greater-than relationship.

9.7.1. Stack Adaptor

The operations provided by a stack are listed in Table 9.23 on the facing page. The following program exercises this set of five stack operations:

Table 9.23. Operations Supported by the Stack Container Adaptor

s.empty()

Returns TRue if the stack is empty; false otherwise.

s.size()

Returns a count of the number of elements on the stack.

s.pop()

Removes, but does not return, the top element from the stack.

s.top()

Returns, but does not remove, the top element on the stack.

s.push(item)

Places a new top element on the stack.


      // number of elements we'll put in our stack      const stack<int>::size_type stk_size = 10;      stack<int> intStack; // empty stack      // fill up the stack      int ix = 0;      while (intStack.size() != stk_size)          // use postfix increment; want to push old value onto intStack          intStack.push(ix++); // intStack holds 0...9 inclusive      int error_cnt = 0;      // look at each value and pop it off the stack      while (intStack.empty() == false) {          int value = intStack.top();          // read the top element of the stack          if (value != --ix) {              cerr << "oops! expected " << ix                   << " received " << value << endl;              ++error_cnt; }          intStack.pop(); // pop the top element, and repeat      }      cout << "Our program ran with "           << error_cnt << " errors!" << endl; 

The declaration

      stack<int> intStack;   // empty stack 

defines intStack to be an empty stack that holds integer elements. The for loop adds stk_size elements initializing each to the next integer in sequence starting from zero. The while loop iterates through the entire stack, examining the top value and popping it from the stack until the stack is empty.

Each container adaptor defines its own operations in terms of operations provided by the underlying container type. By default, this stack is implemented using a deque and uses deque operations to implement the operations of a stack. For example, when we execute

      // use postfix increment; want to push old value onto intStack      intStack.push(ix++);    // intStack holds 0...9 inclusive 

this operation executes by calling the push_back operation of the deque object on which intStack is based. Although stack is implemented by using a deque, we have no direct access to the deque operations. We cannot call push_back on a stack; instead, we must use the stack operation named push.

9.7.2. Queue and Priority Queue

The library queue uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back. The next object retrieved is taken from the front of the queue. There are two kinds of queues: the FIFO queue, which we will speak of simply as a queue, and a priority queue.

A priority_queue lets us establish a priority among the elements held in the queue. Rather than place a newly entered item at the back of the queue, the item is placed ahead of all those items with a lower priority. By default, the library uses the < operator on the element type to determine relative priorities.

A real-world example of a priority queue is the line to check luggage at an airport. Those whose flight is going to leave within the next 30 minutes are generally moved to the front of the line so that they can finish the check-in process before their plane takes off. A programming example of a priority queue is the scheduler of an operating system determining which, of a number of waiting processes, should execute next.

To use either queue or priority_queue, we must include the queue header. Table 9.24 lists the operations supported by queue and priority_queue.

Table 9.24. Operations Supported by Queues and Priority Queues

q.empty()

Returns TRue if the queue is empty; false otherwise.

q.size()

Returns a count of the number of elements on the queue.

q.pop()

Removes, but does not return, the front element from the queue.

q.front()

Returns, but does not remove, the front element on the queue.

This operation can be applied only to a queue.

q.back()

Returns, but does not remove, the back element on the queue.

This operation can be applied only to a queue.

q.top()

Returns, but does not remove, the highest-priority element.

This operation can be applied only to a priority_queue.

q.push(item)

Places a new element at the end of the queue or at its appropriate position based on priority in a priority_queue.


Exercises Section 9.7.2

Exercise 9.42:

Write a program to read a series of words into a stack.

Exercise 9.43:

Use a stack to process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis, pop elements down to and including the open parenthesis off the stack. push a value onto the stack to indicate that a parenthesized expression was replaced.




C++ Primer
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2006
Pages: 223
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net