【C++】map的模拟实现

C++ 中 map 的模拟实现

在 C++ 标准库中，map 是一种非常常用的容器类，它提供了键值对存储功能，能够高效地根据键查找值。map 通常是通过红黑树来实现的，因此具有 O(log n) 的查找、插入和删除复杂度。如果没有使用标准库，我们也可以手动实现一个简单的 map 类。下面我们通过示例代码来模拟实现一个基本的 map 类。

基本思路

在我们实现 map 之前，需要确定基本的结构和操作。我们可以使用链表（或自定义的节点结构）来存储数据。每个节点将包含键、值和指向下一个节点的指针。

我们的 map 类将包含以下基本操作： 1. 插入一个键值对 2. 查找一个键并返回对应的值 3. 删除一个键值对 4. 打印所有键值对

示例代码

#include <iostream>
#include <string>

template<typename K, typename V>
class MyMap {
private:
    struct Node {
        K key;
        V value;
        Node* next;

        Node(K k, V v) : key(k), value(v), next(nullptr) {}
    };

    Node* head;

public:
    MyMap() : head(nullptr) {}

    // 插入键值对
    void insert(K key, V value) {
        Node* newNode = new Node(key, value);
        if (!head) {
            head = newNode;
            return;
        }

        // 在表头插入或者更新现有的键
        if (head->key == key) {
            head->value = value;
            delete newNode;  // 不需要新的节点
            return;
        }

        Node* current = head;
        while (current->next) {
            if (current->next->key == key) {
                current->next->value = value;
                delete newNode;  // 不需要新的节点
                return;
            }
            current = current->next;
        }
        current->next = newNode;  // 在链表末尾插入
    }

    // 查找键
    bool find(K key, V& value) {
        Node* current = head;
        while (current) {
            if (current->key == key) {
                value = current->value;
                return true;
            }
            current = current->next;
        }
        return false;  // 找不到
    }

    // 删除键值对
    void erase(K key) {
        if (!head) return;

        if (head->key == key) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next) {
            if (current->next->key == key) {
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
                return;
            }
            current = current->next;
        }
    }

    // 打印所有键值对
    void print() {
        Node* current = head;
        while (current) {
            std::cout << "Key: " << current->key << ", Value: " << current->value << std::endl;
            current = current->next;
        }
    }

    ~MyMap() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    MyMap<std::string, int> myMap;

    myMap.insert("apple", 1);
    myMap.insert("banana", 2);
    myMap.insert("orange", 3);

    myMap.print();

    int value;
    if (myMap.find("banana", value)) {
        std::cout << "Found banana: " << value << std::endl;
    }

    myMap.erase("banana");
    myMap.print();

    return 0;
}

代码解析

在上面的 MyMap 类中，我们定义了一个内部结构 Node，用于存储每一个键值对。我们的 insert 方法用于插入或更新键值对，find 方法用于查找值，erase 方法用于删除键值对，最后的 print 方法用于输出所有的键值对。

小结

虽然这个简单的实现没有实现红黑树或平衡树的复杂性，使其在性能上不能与 STL 中的 map 相提并论，但它仍然展示了如何通过链表模拟键值对存储的基本原理。在实际开发中，使用 STL 中的 map 会更加高效和安全，但了解这些基础的实现方法对于学习数据结构和算法是非常有益的。