C++ STL: Container Adapters and Use cases

This write-up will explain different Container Adapters, like Stack, Queue, Priority Queue their respective features and mainly their appropriate use-cases.

• Container Adapters are NOT full container classes.
• But the classes that provide a specific interface relying on an object of one of the Container class (such as deque/list) to handle the elements.
• The underlying container is encapsulated in a way that its elements are accessed by the members of the container adapter independent of the underlying container class.

Stack

• Operate in a LIFO context (last-in first-out)
• Elements are Inserted/Extracted Only from ONE END of the container.
• Elements are pushed/popped from the back of the specific container, which is known as the TOP of the stack.
• By default, standard container std::deque is used, if no container class is specified for a particular stack class instantiation.
• Otherwise, std::vector, std::list also used as underlying container.
• Use-cases:
  • First-In Last-Out operations
  • Reversal of elements
• Example:

  std::stack<int> first;                                  // empty stack
  ---------------------
      
  std::deque<int> mydeque (3,100);                        // deque with 3 elements
  std::stack<int> second (mydeque);                       // stack initialized to copy of deque
  ---------------------
      
  std::stack<int,std::vector<int> > third;                // empty stack using vector
  ---------------------
      
  std::vector<int> myvector (2,200);                      // vector with 2 elements
  std::stack<int,std::vector<int> > fourth (myvector);
  

Operations:

    * empty()
    * size()
    * top()
    * pop()
    * push()
    ------------
    
    C++11:
    * emplace()
    * swap()

Time Complexity Stack Operations

Stack Decision Criteria

• Order is Important.
• Last-in, First-out (LIFO) accepted/required.
• Size varies widely - Dynamic
• Need to find Nth element - Random Access
• Insert/Erase at the Front/Back
• Insert/Erase at Mid-positions
• Key:Value pair

References:

• std::stack

Queue

• Operate in FIFO (First-in, First-out)
• Elements are Inserted from one end of the container and Extracted from the other end.
• Elements are Pushed from the back of the specific container and Popped from its front.
• By default, standard container ‘std::deque’ is used, if no container class is specified for a particular queue class instantiation.
• Otherwise, std::vector, std::list also used as underlying container.
• Use-cases:
  • First-In First-Out operations
  • Simple online ordering system (first come first served)
  • Semaphore queue handling
  • CPU scheduling (FCFS)
• Example:

  std::queue<int> first;                                // empty queue
  ------------
      
  std::deque<int> mydeck (3,100);                       // deque with 3 elements
  std::queue<int> second (mydeck);                      // queue initialized to copy of deque
  ------------
      
  std::queue<int,std::list<int> > third;                // empty queue with list as underlying container
  ------------
      
  std::list<int> mylist (2,200);                        // list with 2 elements
  std::queue<int,std::list<int> > fourth (mylist);
  

Operations:

    * empty()
    * size()
    * front()
    * back()
    * pop()
    * push()
    --------------
    
    C++11:
    * emplace()
    * swap()

Time Complexity Queue Operations

Queue Decision Criteria

• Order is Important.
• First-in, First-out (FIFO) accepted/required.
• Size varies widely - Dynamic
• Need to find Nth element - Random Access
• Insert/Erase at the Front/Back
• Insert/Erase at Mid-positions
• Key:Value pair

Priority_Queue

• Its First element is always the “Greatest of the elements” it contains, according to some “strict weak ordering” criterion.
  • Similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).
• Elements are Popped from the back of the specific container, which is known as the top of the priority queue.
• The underlying container shall be accessible through Random Access Iterators
  • Support of Random Access Iterators is required to keep a “Heap structure” internally at all times.
  • This is done automatically by the container adapter by automatically calling the algorithm functions:
    • make_heap,
    • push_heap and
    • pop_heap
• By default, standard container ‘std::vector’ is used, if no container class is specified for a particular priority_queue class instantiation.
• Otherwise, ‘std::deque’ can also be used as underlying container.

Operation:

    * empty()
    * size()
    * top()
    * push()
    * pop()
    ------------
    
    C++11:
    * emplace()
    * swap()

Priority Queue Decision Criteria

• Order is Important.
• First-in, First-out (FIFO) accepted/required.
• Size varies widely - Dynamic
• Need to find Nth element - Random Access
• Insert/Erase at the Front/Back
• Insert/Erase at Mid-positions
• Key:Value pair

Reference

• std::stack
• std::queue
• std::priority_queue