1. Phân tích cấu trúc mã nguồn và thiết kế khung

Khi nghiên cứu phiên bản SGI-STL 3.0, chúng ta có thể thấy rằng mã nguồn của map và set được tổ chức trong các tệp tiêu đề như stl_map.h, stl_set.h và đặc biệt là stl_tree.h. Điểm mấu chốt nằm ở việc cả hai container này đều sử dụng chung một cấu trúc cây nhị phân tìm kiếm cân bằng (Red-Black Tree) làm nền tảng.

Dưới đây là trích lược khung cốt lõi từ mã nguồn gốc:

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
private:
    // Cây đỏ đen lưu trữ Key như là Value
    typedef rb_tree<key_type, value_type, 
                    identity<value_type>, key_compare, Alloc> rep_type;
    rep_type tree_instance; 
};

// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
private:
    // Cây đỏ đen lưu trữ pair<Key, T>
    typedef rb_tree<key_type, value_type, 
                    select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type tree_instance; 
};

Qua phân tích trên, ta thấy tư tưởng lập trình泛型 (generic programming) được áp dụng rất triệt để. Cây đỏ đen (rb_tree) không hard-code việc nó lưu trữ chỉ khóa (key) hay cặp khóa-giá trị (key/value). Thay vào đó, kiểu dữ liệu thực tế lưu trong nút cây được quyết định bởi tham số模板 thứ hai.

Đối với set, tham số này là chính Key. Đối với map, tham số này là pair<const Key, T>. Nhờ vậy, cùng một cấu trúc cây có thể phục vụ cho cả hai mục đích tìm kiếm khác nhau.

Một điểm cần lưu ý là tên gọi trong mã nguồn gốc khá đa dạng: set dùng Key, map dùng Key và T, còn rb_tree lại dùng Key và Value. Trong đó, Value của cây chính là kiểu dữ liệu thực tế lưu trữ trong nút, không nhất thiết trùng với giá trị (value) mà người dùng hiểu trong ngữ cảnh map.

Vai trò của tham số模板 đầu tiên (Key) là để xác định kiểu dữ liệu dùng cho các hàm tìm kiếm (find) hoặc xóa (erase). Với set, Key và Value giống nhau, nhưng với map, chúng khác nhau hoàn toàn (insert nhận pair, find nhận Key).

2. Xây dựng mô phỏng Map và Set

2.1. Khung复用 cây đỏ đen và hỗ trợ chèn dữ liệu

Dựa trên thiết kế của STL, chúng ta sẽ xây dựng lại cây đỏ đen để cả map và set cùng sử dụng. Để linh hoạt hơn, chúng ta đặt tên tham số là K (Key), V (Value) và kiểu dữ liệu lưu trong cây là T.

Vấn đề đặt ra là cây đỏ đen chỉ lưu trữ T, làm sao để so sánh khóa khi T có thể là K (trong set) hoặc pair<K, V> (trong map)? Giải pháp là sử dụng một hàm đối tượng (functor) để trích xuất khóa từ T trước khi so sánh.

Chúng ta định nghĩa các lớp trích xuất khóa riêng cho Map và Set:

// Mymap.h
namespace custom_stl
{
    template<typename K, typename V>
    class MapContainer
    {
        // Functor trích xuất key từ pair
        struct MapKeyProjection
        {
            const K& operator()(const pair<K, V>& data) const
            {
                return data.first;
            }
        };
    public:
        bool insert(const pair<K, V>& item)
        {
            return tree_engine.InsertNode(item);
        }
    private:
        // Cây lưu trữ pair, dùng functor để lấy key so sánh
        RedBlackTree<K, pair<K, V>, MapKeyProjection> tree_engine;
    };
}

// Myset.h
namespace custom_stl
{
    template<typename K>
    class SetContainer
    {
        // Functor trích xuất key từ chính nó
        struct SetKeyProjection
        {
            const K& operator()(const K& item) const
            {
                return item;
            }
        };
    public: 
        bool insert(const K& item)
        {
            return tree_engine.InsertNode(item);
        } 
    private:
        RedBlackTree<K, K, SetKeyProjection> tree_engine;
    };
}

Triển khai cơ bản của cây đỏ đen sẽ như sau:

// RBTreeImpl.h
enum NodeColor
{
    COLOR_RED,
    COLOR_BLACK
};

template<typename T>
struct TreeNodeRB
{
    T m_value;
    TreeNodeRB<T>* m_left;
    TreeNodeRB<T>* m_right;
    TreeNodeRB<T>* m_parent;
    NodeColor m_color;

    TreeNodeRB(const T& val)
        : m_value(val)
        , m_left(nullptr)
        , m_right(nullptr)
        , m_parent(nullptr)
        , m_color(COLOR_RED)
    {}
};

template<typename K, typename T, typename KeyExtract>
class RedBlackTree
{
    typedef TreeNodeRB<T> Node;
    Node* m_root = nullptr;

public:
    bool InsertNode(const T& data)
    {
        if (m_root == nullptr)
        {
            m_root = new Node(data);
            m_root->m_color = COLOR_BLACK;
            return true;
        }

        KeyExtract extractor;
        Node* parentPtr = nullptr;
        Node* currentPtr = m_root;

        // Tìm vị trí chèn
        while (currentPtr)
        {
            if (extractor(currentPtr->m_value) < extractor(data))
            {
                parentPtr = currentPtr;
                currentPtr = currentPtr->m_right;
            }
            else if (extractor(currentPtr->m_value) > extractor(data))
            {
                parentPtr = currentPtr;
                currentPtr = currentPtr->m_left;
            }
            else
            {
                return false; // Trùng khóa
            }
        }

        // Tạo nút mới
        currentPtr = new Node(data);
        Node* newNode = currentPtr;
        
        if (extractor(parentPtr->m_value) < extractor(data))
        {
            parentPtr->m_right = currentPtr;
        }
        else
        {
            parentPtr->m_left = currentPtr;
        }
        currentPtr->m_parent = parentPtr;

        // Cân bằng cây (xử lý vi phạm màu đỏ)
        // ... (logic cân bằng sẽ được thực hiện ở đây)
        
        return true;
    }
};

2.2. Triển khai Iterator cho cây nhị phân

Iterator đóng vai trò quan trọng để duyệt cây theo thứ tự trung tố (in-order). Logic cốt lõi của operator++ và operator-- dựa trên việc di chuyển giữa các nút mà không cần quan tâm đến toàn cục, chỉ cần xác định nút tiếp theo trong dãy trung tố.

Nguyên tắc duyệt trung tố: Trái - Gốc - Phải.

• Tăng iterator (++):
  • Nếu nút hiện tại có con phải: Tìm nút trái nhất của cây con phải.
  • Nếu không có con phải: Đi ngược lên cha. Nếu nút hiện tại là con trái của cha, thì cha là nút tiếp theo. Nếu là con phải, tiếp tục lên cho đến khi gặp một nút là con trái của cha nó.
• Giảm iterator (--): Logic ngược lại hoàn toàn với tăng.
• end(): Có thể biểu diễn bằng con trỏ nullptr. Khi --end(), cần tìm nút phải nhất của cây.

Để đảm bảo tính đóng gói và an toàn dữ liệu:

• set không cho phép sửa giá trị: Kiểu dữ liệu trong cây là const K.
• map không cho phép sửa Key nhưng cho phép sửa Value: Kiểu dữ liệu là pair<const K, V>.

2.3. Hỗ trợ toán tử [] cho Map

Để hỗ trợ cú pháp map[key], hàm Insert của cây cần trả về cặp pair<Iterator, bool> để biết vị trí chèn hoặc tìm thấy. Nếu key chưa tồn tại, nó sẽ chèn mới với value mặc định và trả về reference đến value đó.

2.4. Mã nguồn hoàn chỉnh Map và Set

Dưới đây là triển khai hoàn chỉnh cho các container tùy chỉnh:

// MySet.h
#include "RBTreeImpl.h"
namespace custom_stl
{
    template<typename K>
    class SetContainer
    {
        struct SetKeyProjection
        {
            const K& operator()(const K& key) const { return key; }
        };
    public:
        typedef typename RedBlackTree<K, const K, SetKeyProjection>::Iterator iterator;
        typedef typename RedBlackTree<K, const K, SetKeyProjection>::ConstIterator const_iterator;

        iterator begin() { return tree_engine.Begin(); }
        iterator end() { return tree_engine.End(); }
        
        pair<iterator, bool> insert(const K& key) { return tree_engine.InsertNode(key); }
        iterator find(const K& key) { return tree_engine.FindNode(key); }

    private:
        RedBlackTree<K, const K, SetKeyProjection> tree_engine;
    };
}

// MyMap.h
#include "RBTreeImpl.h"
namespace custom_stl
{
    template<typename K, typename V>
    class MapContainer
    {
        struct MapKeyProjection
        {
            const K& operator()(const pair<K, V>& kv) const { return kv.first; }
        };
    public:
        typedef typename RedBlackTree<K, pair<const K, V>, MapKeyProjection>::Iterator iterator;
        
        iterator begin() { return tree_engine.Begin(); }
        iterator end() { return tree_engine.End(); }
        
        pair<iterator, bool> insert(const pair<K, V>& kv) { return tree_engine.InsertNode(kv); }
        
        V& operator[](const K& key)
        {
            pair<iterator, bool> result = insert(make_pair(key, V()));
            return result.first->second;
        }

    private:
        RedBlackTree<K, pair<const K, V>, MapKeyProjection> tree_engine;
    };
}

// RBTreeImpl.h (Chi tiết Iterator và Cân bằng)
template<typename T, typename Ref, typename Ptr>
struct TreeIterator
{
    typedef TreeNodeRB<T> Node;
    typedef TreeIterator<T, Ref, Ptr> Self;
    Node* m_node;
    Node* m_root;

    TreeIterator(Node* node, Node* root) : m_node(node), m_root(root) {}

    Self& operator++()
    {
        if (m_node->m_right)
        {
            Node* leftMost = m_node->m_right;
            while (leftMost->m_left) leftMost = leftMost->m_left;
            m_node = leftMost;
        }
        else
        {
            Node* cur = m_node;
            Node* parent = cur->m_parent;
            while (parent && cur == parent->m_right)
            {
                cur = parent;
                parent = cur->m_parent;
            }
            m_node = parent;
        }
        return *this;
    }

    Self& operator--()
    {
        if (m_node == nullptr)
        {
            Node* rightMost = m_root;
            while (rightMost && rightMost->m_right) rightMost = rightMost->m_right;
            m_node = rightMost;
        }
        else if (m_node->m_left)
        {
            Node* rightMost = m_node->m_left;
            while (rightMost->m_right) rightMost = rightMost->m_right;
            m_node = rightMost;
        }
        else
        {
            Node* cur = m_node;
            Node* parent = cur->m_parent;
            while (parent && cur == parent->m_left)
            {
                cur = parent;
                parent = cur->m_parent;
            }
            m_node = parent;
        }
        return *this;
    }

    Ref operator*() { return m_node->m_value; }
    Ptr operator->() { return &m_node->m_value; }
    bool operator!=(const Self& s) const { return m_node != s.m_node; }
    bool operator==(const Self& s) const { return m_node == s.m_node; }
};

template<typename K, typename T, typename KeyExtract>
class RedBlackTree
{
    typedef TreeNodeRB<T> Node;
public:
    typedef TreeIterator<T, T&, T*> Iterator;
    typedef TreeIterator<T, const T&, const T*> ConstIterator;

    Iterator Begin()
    {
        Node* leftMost = m_root;
        while (leftMost && leftMost->m_left) leftMost = leftMost->m_left;
        return Iterator(leftMost, m_root);
    }

    Iterator End() { return Iterator(nullptr, m_root); }

    pair<Iterator, bool> InsertNode(const T& data)
    {
        if (m_root == nullptr)
        {
            m_root = new Node(data);
            m_root->m_color = COLOR_BLACK;
            return make_pair(Iterator(m_root, m_root), true);
        }

        KeyExtract extractor;
        Node* parentPtr = nullptr;
        Node* currentPtr = m_root;
        
        while (currentPtr)
        {
            if (extractor(currentPtr->m_value) < extractor(data))
            {
                parentPtr = currentPtr;
                currentPtr = currentPtr->m_right;
            }
            else if (extractor(currentPtr->m_value) > extractor(data))
            {
                parentPtr = currentPtr;
                currentPtr = currentPtr->m_left;
            }
            else
            {
                return make_pair(Iterator(currentPtr, m_root), false);
            }
        }

        currentPtr = new Node(data);
        Node* newNode = currentPtr;
        currentPtr->m_color = COLOR_RED;

        if (extractor(parentPtr->m_value) < extractor(data))
            parentPtr->m_right = currentPtr;
        else
            parentPtr->m_left = currentPtr;
        
        currentPtr->m_parent = parentPtr;

        // Xử lý cân bằng màu
        while (parentPtr && parentPtr->m_color == COLOR_RED)
        {
            Node* grandParent = parentPtr->m_parent;
            if (parentPtr == grandParent->m_left)
            {
                Node* uncle = grandParent->m_right;
                if (uncle && uncle->m_color == COLOR_RED)
                {
                    parentPtr->m_color = uncle->m_color = COLOR_BLACK;
                    grandParent->m_color = COLOR_RED;
                    currentPtr = grandParent;
                    parentPtr = currentPtr->m_parent;
                }
                else
                {
                    if (currentPtr == parentPtr->m_left)
                    {
                        RotateRight(grandParent);
                        parentPtr->m_color = COLOR_BLACK;
                        grandParent->m_color = COLOR_RED;
                    }
                    else
                    {
                        RotateLeft(parentPtr);
                        RotateRight(grandParent);
                        currentPtr->m_color = COLOR_BLACK;
                        grandParent->m_color = COLOR_RED;
                    }
                    break;
                }
            }
            else
            {
                Node* uncle = grandParent->m_left;
                if (uncle && uncle->m_color == COLOR_RED)
                {
                    parentPtr->m_color = uncle->m_color = COLOR_BLACK;
                    grandParent->m_color = COLOR_RED;
                    currentPtr = grandParent;
                    parentPtr = currentPtr->m_parent;
                }
                else
                {
                    if (currentPtr == parentPtr->m_right)
                    {
                        RotateLeft(grandParent);
                        parentPtr->m_color = COLOR_BLACK;
                        grandParent->m_color = COLOR_RED;
                    }
                    else
                    {
                        RotateRight(parentPtr);
                        RotateLeft(grandParent);
                        currentPtr->m_color = COLOR_BLACK;
                        grandParent->m_color = COLOR_RED;
                    }
                    break;
                }
            }
        }
        m_root->m_color = COLOR_BLACK;
        return make_pair(Iterator(newNode, m_root), true);
    }

private:
    void RotateLeft(Node* parent)
    {
        Node* subR = parent->m_right;
        Node* subRL = subR->m_left;
        parent->m_right = subRL;
        if (subRL) subRL->m_parent = parent;
        
        Node* parentParent = parent->m_parent;
        subR->m_left = parent;
        parent->m_parent = subR;
        
        if (parentParent == nullptr)
        {
            m_root = subR;
            subR->m_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->m_left)
                parentParent->m_left = subR;
            else
                parentParent->m_right = subR;
            subR->m_parent = parentParent;
        }
    }

    void RotateRight(Node* parent)
    {
        Node* subL = parent->m_left;
        Node* subLR = subL->m_right;
        parent->m_left = subLR;
        if (subLR) subLR->m_parent = parent;
        
        Node* parentParent = parent->m_parent;
        subL->m_right = parent;
        parent->m_parent = subL;
        
        if (parentParent == nullptr)
        {
            m_root = subL;
            subL->m_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->m_left)
                parentParent->m_left = subL;
            else
                parentParent->m_right = subL;
            subL->m_parent = parentParent;
        }
    }

    void Destroy(Node* root)
    {
        if (!root) return;
        Destroy(root->m_left);
        Destroy(root->m_right);
        delete root;
    }

    ~RedBlackTree() { Destroy(m_root); }

private:
    Node* m_root = nullptr;
};