Review

Standard Template Library

The Standard Template Library (STL) is a collection of powerful, template-based, reusable codes. It implements many general-purpose containers (data structures) together with algorithms that work on them.

The three pillars of STL are containers, iterators, and algorithms.

• A container class is a class template that holds a collection of homogeneous objects of the same type. For example, a vector container class (dynamic array with resizing handled by the STL) can be utilized as follows:
  
  

  #include <vector>
  std::vector<int> myVector; // STL vector of ints.
  myVector.emplace_back(10); // Add int value "10" to the back of the vector.

(See here for the difference between push_back and emplace_back.)


• Iterators are generalized pointers. For example, the following shows how to scan through a list container using an iterator:
  
  

  #include <iostream>
  #include <list>
  std::list<int> myList; // STL doubly linked list of ints.
  myList.emplace_back(10);
  myList.emplace_back(20);
  myList.emplace_back(30);
  // std::list<int>::iterator is STL list of ints iterator.
  for (std::list<int>::iterator it{myList.begin()}; it != myList.end(); ++it) {
    std::cout << *it << std::endl;
  }

  Iterators allow us to separate algorithms from containers when they are used with templates. It can be tedious to specify the full and correct templated typename when declaring an iterator, so the auto keyword is typically used instead.
  
  

  #include <iostream>
  #include <list>
  std::list<int> myList; // STL doubly linked list of ints.
  myList.emplace_back(10);
  myList.emplace_back(20);
  myList.emplace_back(30);
  for (auto it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << std::endl;
  }



• STL algorithms are implemented as global function templates. For example, use STL find algorithm to find an element in a list (though most STL Containers have their own find function or similar, which is generally faster and better):
  
  

  #include <string>
  #include <list>
  std::list<string> composers;
  composers.emplace_back("Bach");
  composers.emplace_back("Mozart");
  composers.emplace_back("Beethoven");
  auto it = std::find(composers.begin(), composers.end(), "Bach");
  

Trees

A tree T is a collection of nodes connected by edges.

• Base case: T is empty
• Recursive case: If not empty, a tree T consists of
  • A root node r, and
  • zero or more non-empty sub-trees: T₁, T₂, ..., T_k

Binary Tree

A binary tree is a tree in which no node can have more than two children. A typical implementation of Binary Tree ADT is shown below.

#include <iostream>     /* File: btree.h */
using namespace std;

template <typename T>
class BTnode
{
  public:
    BTnode(const T& x, BTnode* L = nullptr, BTnode* R = nullptr)
      : data(x), left(L), right(R) { }

    ~BTnode()
    {
      delete left;
      delete right;
      cout << "delete the node with data = " << data << endl;
    }

    const T& get_data() const { return data; }
    BTnode* get_left()  const { return left; }
    BTnode* get_right() const { return right; }
    void set_left(BTnode* left) { this->left = left; }
    void set_right(BTnode* right) { this->right = right; }

  private:
    T data;             // Stored information
    BTnode* left;       // Left child
    BTnode* right;      // Right child
};

Binary Search Tree

A binary search tree is a binary tree such that for every node x:

• All the keys in its left sub-tree are smaller than the key value in node x.
• All the keys in its right sub-tree are larger than the key value in node x.

A typical implementation of Binary Search Tree is shown below.

#include <iostream>  /* File: bst.h */
using namespace std;

template<typename T<
class BST
{
  private:
    struct BSTnode // A node in a binary search tree
    {
      T value;
      BST left; // Left sub-tree or called left child      BST right; // Right sub-tree or called right child
      BSTnode(const T &x) : value(x), left(), right() { }
        // Assume a copy constructor for T
      BSTnode(const BSTnode &node) // Copy constructor
        :value(node.value), left(node.left), right(node.right) { }
      ~BSTnode() { cout << "delete: " << value << endl; }
    };
    BSTnode *root = nullptr;

  public:
    BST() = default; // Empty BST
    ~BST() { delete root; } // Actually recursive
    // Shallow BST copy using move constructor
    BST(BST &&bst) { root = bst.root; bst.root = nullptr; }
    BST(const BST &bst) // Deep copy using copy constructor
    {
      if (bst.is_empty())
        return;

      root = new BSTnode(*bst.root); // Recursive
    }

    bool is_empty() const {
      return root == nullptr;
    }
    bool contains(const T &x) const;
    void print(int depth = 0) const;
    const T& find_max() const; // Find the maximum value
    const T& find_min() const; // Find the minimum value
    void insert(const T&); // Insert an item with a policy
    void remove(const T&); // Remove an item
};

Book and Toy Store

Objective

In this lab, you will get familiar with Standard Template Library (STL) and Binary Search Tree (BST) in C++.

Description

The business of a Book and Toy Store is gaining traction. Joe, the owner of the store, is getting overwhelmed by the ever increasing workload to manage his store. In this lab, we will help Joe better manage the book and toy store, especially how to efficiently find a specific book or toy based on a query ID. If we manage the information with an array, it will take O(n) (n is the input length) at the worst case to complete a query, which would be quite expensive considering the massive amout of books and toys. However, if we utilize advanced data structures like Max Heap, whose basic structure is Binary Search Tree (BST), we can decrease the running time complexity to O(logn) significantly. In this lab, your task is exactly to help Joe develop a manager system based on BST.

Overview

There are 2 classes involved: BinarySearchTree and Manager. You need to maintain two Binary Search Trees to represent the book and toy sections respectively with the help of a Manager by using the STL map.

1. BinarySearchTree
   A good BST should support add (adding new IDs), hasId (checking whether a ID is in this tree) and height (checking the height of the BST) operations. You also need to finish the constructors and destructors. We have provided the printDFSPrefix and printDFSInfix to help you print the content of a BST.
2. Manager
   We use a STL map to manage the book section BST and toy section BST with the getSection, registerSection, deleteSection and printStatus operations.

Lab Tasks

1. Finish the TODOs in BinarySearchTree.cpp and Manager.cpp.
2. Compile the project.
3. Run the executable to check with the expected output below:

   /* test1.exe */
   Maneger has 1 sections: book
   The height of section #1 is: 4
   Section #1 prefix notation: 6 4 1 3 11 9 10 16 15 13
   Section #1 infix notation: 1 3 4 6 9 10 11 13 15 16
   11 is in Section #1
   Manager is deleting the book section
   Maneger has 1 sections: toy
   
   /* test2.exe */
   MManeger has 1 sections: book
   The height of section #1 is: 4
   Section #1 prefix notation: 6 4 1 3 11 9 10 16 15 13
   Section #1 infix notation: 1 3 4 6 9 10 11 13 15 16
   11 is in Section #1
   Maneger has 2 sections: book toy
   The height of section #2 is: 4
   Section #2 prefix notation: 6 4 1 3 5 11 9 10 16 15 13 19 17
   Section #2 infix notation: 1 3 4 5 6 9 10 11 13 15 16 17 19
   21 is not in Section #2
   Manager is deleting the book section
   Maneger has 1 sections: toy
   Manager is deleting the toy section
   Maneger has 0 sections
                           

Hint

1. Try to construct the BSTs by hand first to review the recursive process of BST construction.
2. Observe test1.cpp and test2.cpp to understand how to achieve the expected output.
3. Search the Internet to find more information about the usage of STL map and vector.

Introduction to C++ STL map

• Definition
Maps are associative containers that store elements in a combination of keys and mapped values that follow a specific order. For C++ STL maps, no two mapped values are allowed to have the same key values. To some extent, maps work quite similarly with special hash function which takes the key as input, and then output the corresponding value.

// If we have a map defined as below
demo_map = {apple: 3, banana: 1, watermelon: 3}
// Then according to the definition of maps, we have
demo_map[apple] = 3 & demo_map[banana] = 1 & demo_map[watermelon] = 3

• Syntax
A map should be defined in the following way:

// key_datatype: the data type for the keys in the map
// value_datatype: the data type for values corresponding to the keys in the map
// map_name: variable name of the map
std::map<key_datatype, value_datatype> map_name
// An example to declare a map with string values as keys and
// integers as their corresponding values would be:
std::map<string, int> sample_map;

• Interface
• at(key): return the corresponding value of a given key;
• emplace(key, value): add a new key-value pair to the map;
• erase(const g): remove the key value g from the map;
• begin(): return an iterator to the first element in the map;
• Have fun exploring different usages of STL maps!

Download

For this lab, you can download the source files here. Unzip the zip file and open the source directory via VSCode. In this lab, the file dependency is simple. The makefile is provided for you as a reference.
Download source file here

Submission and Deadline

Deadline: 22 November 2021 Monday 23:59 HKT.
You may earn 1% course grade for this lab via Automated Grading on the ZINC Online Submission System. Please compress and submit BinarySearchTree.cpp and Manager.cpp to ZINC. You can submit your codes multiple times by the deadline. Only the last submission will be graded.