# Container Adaptors

Container adaptors provide a different interface for sequential containers. They do not have their own data structures. Instead, all their methods are implemented by the dependent containers. An example of a _stack_ with _deque_ as the default structure shows as follow:

```cpp
template<typename T, typename Container=deque<T>>
class Stack {
public:
    void push(const T &val) {
      con.push_back(val);
    }
    
    void pop() {
        con.pop_back();
    }
    
    T top() const {
        return con.back();
    }
private:
    Container con;
};
```

In addition, container adaptors do not have their own iterators as well.

### _stack_

```cpp
#include <stack>
```

_stack_ is a FILO (First-In-Last-Out) data structure which adapts a _deque_ by default.

`s.push(20)` Insert element at the top. Time complexity is _O(1)_.

`s.pop()` Remove the top element. Time complexity is _O(1)_.

`s.top()` Return the top element. Time complexity is _O(1)_.

`s.empty()` Check whether the container is empty.

`s.size()` Return the number of elements in the container.

### _queue_

```cpp
#include <queue>
```

_queue_ is a FIFO (First-In-First-Out) data structure which adapts a _deque_ by default.

`q.push(20)` Insert element at the end. Time complexity is _O(1)_.

`q.pop()` Remove the first element. Time complexity is _O(1)_.

`q.front()` Return the first element. Time complexity is _O(1)_.

`q.back()` Return the last element. Time complexity is _O(1)_.

`q.empty()` Check whether the container is empty.

`q.size()` Return the number of elements in the container.

### _priority\_queue_

```cpp
#include <priority_queue>
```

_priority\_queue_ is a container that can access queue elements by their priority (larger by default). It adapts a _vector_ by default.

`pq.push(20)` Insert element sorts the container. Time complexity is _O(nlog(n))_.

`pq.pop()` Remove the top element. Time complexity is _O(1)_.

`pq.top()` Return the top element. Time complexity is _O(1)_.

`pq.empty()` Check whether the container is empty.

`pq.size()` Return the number of elements in the container.

### More about Underlying Containers

**Q:** _stack_ and _queue_ use _deque_ as their default underlying containers. Why don't they use a _vector_?

**A:** We can answer from the differences between these two data structures.

1. The initial memory usage efficiency of _vector_ is worse than _deque_, since _deque_ allocates more memory when initialized and reduces overhead for expansion.
2. _queue_ requires insert from the end. These operations are _O(1)_ in _deque_, but _O(n)_ in _vector_.
3. When there are a large amount of elements, _vector_ requires large continuous memory, while _deque_ only requires segmented memory, thus providing a better memory utilization.

**Q:** Why does _priority\_queue_ use a _vector_？

**A:** The underlying data structure of _priority\_queue_ is a heap. In a heap structure, we access child nodes with the node index (For example, if a heap starts with 0 and a node has index _i_, then its child nodes are _2i +1_ and _2i + 2_). Therefore, heap indexes should be stored in an array of continuous memory. A _vector_ makes sure that random access of heap indexes is _O(1)_.
