Question

In C++ please.

5. Define container adapters that we studied. Explain why container

adapters more suitable for some tasks than regular sequential container.

State one container adapter and describe operations that are available for

this adapter.

Answer 1

The STL provides three container adaptersstack, queue and priority_queue. Adapters are not first-class containers, because they do not provide the actual data-structure implementation in which elements can be stored and because adapters do not support iterators. The benefit of an adapter class is that the programmer can choose an appropriate underlying data structure. All three adapter classes provide member functions push and pop that properly insert an element into each adapter data structure and properly remove an element from each adapter data structure. The next several subsections provide examples of the adapter classes.

stack Adapter

Class stack enables insertions into and deletions from the underlying data structure at one end (commonly referred to as a last-in, first-out data structure). A stack can be implemented with any of the sequence containers: vector, list and deque. This example creates three integer stacks, using each of the sequence containers of the Standard Library as the underlying data structure to represent the stack. By default, a stack is implemented with a deque. The stack operations are push to insert an element at the top of the stack (implemented by calling function push_back of the underlying container), pop to remove the top element of the stack (implemented by calling function pop_back of the underlying container), top to get a reference to the top element of the stack (implemented by calling function back of the underlying container), empty to determine whether the stack is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the stack (implemented by calling function size of the underlying container).

queue Adapter

Class queue enables insertions at the back of the underlying data structure and deletions from the front (commonly referred to as a first-in, first-out data structure). A queue can be implemented with STL data structure list or deque. By default, a queue is implemented with a deque. The common queue operations are push to insert an element at the back of the queue (implemented by calling function push_back of the underlying container), pop to remove the element at the front of the queue (implemented by calling function pop_front of the underlying container), front to get a reference to the first element in the queue (implemented by calling function front of the underlying container), back to get a reference to the last element in the queue (implemented by calling function back of the underlying container), empty to determine whether the queue is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the queue (implemented by calling function size of the underlying container).

priority_queue Adapter

Class priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. A priority_queue can be implemented with STL sequence containers vector or deque. By default, a priority_queue is implemented with a vector as the underlying container. When elements are added to a priority_queue, they are inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue. This is usually accomplished via a sorting technique called heapsort that always maintains the largest value (i.e., highest-priority element) at the front of the data structuresuch a data structure is called a heap. The comparison of elements is performed with comparator function object less< T > by default, but the programmer can supply a different comparator.

The common priority_queue operations are push to insert an element at the appropriate location based on priority order of the priority_queue (implemented by calling function push_back of the underlying container, then reordering the elements using heapsort), pop to remove the highest-priority element of the priority_queue (implemented by calling function pop_back of the underlying container after removing the top element of the heap), top to get a reference to the top element of the priority_queue (implemented by calling function front of the underlying container), empty to determine whether the priority_queue is empty (implemented by calling function empty of the underlying container) and size to get the number of elements in the priority_queue (implemented by calling function size of the underlying container).

Explain why container adapters more suitable for some tasks than regular sequential container.

Unlike sequence and adapter containers, container adapters—such as stack, queue, and priority_queue—apply some sort of constraints in the storage and retrieval process of elements in the underlying data structure. They are not like the first-class containers, although the underlying data structure used by them are from first-class containers only. Container adapter classes are typically convenient classes provided by the library for everyday programming. One can always ignore them and reinvent the wheel, but experience says it is better to adapt one that already exists unless, of course, there is a very good reason to start from scratch.

State one container adapter and describe operations that are available for this adapter.

queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:
empty
size
front
back
push_back
pop_front

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.