In the last article, we covered some sequence containers, where elements are stored sequentially. In this article, we will explore associative containers, which allow elements to be efficiently retrieved based on their keys.

Sets

While other containers allow duplicate elements, a set restricts its elements to be unique and sorted (in ascending order by default).

#include <set>
 
int main() {
    
    set<int> s; // set<int, greater<int>> s; for descending
    s.insert(1);
    s.insert(3);
    s.insert(2);
    s.insert(2);
 
    cout << "s:";
    for (auto i: s) {
        cout << " " << i;
    }
    cout << endl;
    // => s: 1 2 3
 
    return 0;
}

As shown above, the set only contains unique elements in sorted order. All standard container operations are also supported.

Maps

Maps are used not only to store unique keys but also to associate values with those keys as key-value pairs. By default, keys in a map are stored in ascending order, just like in sets.

#include <map>
 
int main () {
    map<string, int> m;
    m["a"] = 1;
    m["b"] = 2;
    m.insert(pair<string, int>("c", 3)); // "pair" is an object for key-value pair
 
    cout << "m:" << endl;
    for (auto i: s) {
        cout << " " << i.first << ": " << i.second << endl;
    }
    // => m: 
    //    a: 1
    //    b: 2
    //    c: 3
 
    return 0;
}

In maps, the key-value pairs are stored as pair objects, where the first member represents the key and the second member represents the associated value. Maps still support standard container operations, including iterators.

Binary Search Tree

The set and map containers are efficient at storing sorted elements and searching for an element. They are implemented using a binary search tree (BST), which provides these properties. A binary search tree is a tree where each node has at most two child nodes: the left node is smaller than the root node, and the right node is larger than the root node.

The example above shows a binary search tree. You can see that searching for an element takes, at most, the height of the tree ($O(log_2n)$ when balanced) as you can eliminate half of the nodes with each comparison, starting from the root. Inserting an element can also be done efficiently ($O(log_2n)$ when balanced) by searching for the correct location to insert the new element, comparing nodes at each level. Below is a partial C++ implementation of a BST.

#include <iostream>
using namespace std;
 
template <typename T>
class Node {
public:
    T data;
    Node* left;
    Node* right;
 
    // Constructor to initialize the node with data and null left and right pointers
    Node(T data) : data(data), left(nullptr), right(nullptr) {};
};
 
template <typename T>
class BST {
public:
    Node<T>* root;
 
    // Constructor initializes the root as nullptr (empty tree)
    BST() : root(nullptr) {};
 
    void insert(T data) {
        root = insertion(root, new Node<T>(data));
    }
 
    void print() {
        display(root);
        cout << endl;
    };
 
private:
    Node<T>* insertion(Node<T>* root, Node<T>* node) {
        if (root == nullptr) {
            return node;
        }
 
        if (node->data < root->data) {
            root->left = insertion(root->left, node);
        } else if (node->data > root->data) {
            root->right = insertion(root->right, node);
        }
 
        return root;
    };
 
    void display(Node<T>* root) {
        if (root != nullptr) {
            display(root->left);
            cout << root->data << " ";
            display(root->right);
        }
    };
};

The above implementation only handles insertion and printing. As a challenge, I recommend you implement searching and deleting. (Deleting a node may require shifting nodes, which can be a bit more complicated.) This demonstrates how the set is implemented using a BST to achieve efficient searching and insertion of unique elements in sorted order. The map can also be built with a BST, where each node stores a key-value pair.

Conclusion

In this article, we introduced associative containers available in the C++ Standard Library and explained how they are implemented using BSTs to achieve efficient insertion and search. In the next article, we will explore a different kind of container: unordered associative containers.

Resources

• javidx9. 2021. Back To Basics: C++ Containers. YouTube.