面试题：深入剖析 C++ map 容器键值存储实现细节

1. 实现比较函数（operator< 重载）

假设自定义结构体如下：

#include <iostream>
#include <string>

struct MyComplexStruct {
    int id;
    std::string name;
    double* data;

    MyComplexStruct(int i, const std::string& n, double* d) : id(i), name(n) {
        data = new double[10];
        for (int j = 0; j < 10; ++j) {
            data[j] = d[j];
        }
    }

    ~MyComplexStruct() {
        delete[] data;
    }

    // 重载 operator<
    bool operator<(const MyComplexStruct& other) const {
        if (id != other.id) {
            return id < other.id;
        }
        if (name != other.name) {
            return name < other.name;
        }
        for (int i = 0; i < 10; ++i) {
            if (data[i] != other.data[i]) {
                return data[i] < other.data[i];
            }
        }
        return false;
    }
};

2. 内存管理注意事项

构造函数：在构造函数中分配内存时，要确保成功分配。如果分配失败（如 new double[10] 失败），应采取适当措施，如抛出异常或返回错误状态。
析构函数：必须实现析构函数来释放动态分配的内存，避免内存泄漏。在上述例子中，~MyComplexStruct 函数负责释放 data 所指向的内存。
复制构造函数和赋值运算符：由于结构体包含动态分配内存，还应考虑实现复制构造函数和赋值运算符，以确保在对象复制或赋值时内存管理的正确性。这可以避免浅拷贝问题。例如：

MyComplexStruct(const MyComplexStruct& other) : id(other.id), name(other.name) {
    data = new double[10];
    for (int j = 0; j < 10; ++j) {
        data[j] = other.data[j];
    }
}

MyComplexStruct& operator=(const MyComplexStruct& other) {
    if (this != &other) {
        id = other.id;
        name = other.name;
        delete[] data;
        data = new double[10];
        for (int j = 0; j < 10; ++j) {
            data[j] = other.data[j];
        }
    }
    return *this;
}

3. 性能相关问题

减少比较操作：在 operator< 中，优先比较那些区分度高的成员变量，以减少不必要的比较。例如上述代码中先比较 id，如果 id 不同，就无需再比较 name 和 data。
避免不必要的内存分配：如在复制构造函数和赋值运算符中，尽量复用已有的内存，减少不必要的动态内存分配和释放操作。

4. map 容器插入和查找时红黑树的操作步骤

插入操作

查找插入位置：从根节点开始，根据 operator< 比较待插入键值对的键与当前节点的键。如果待插入键小于当前节点的键，则向左子树移动；否则向右子树移动，直到找到合适的插入位置（一个空节点）。
插入新节点：在找到的空节点位置插入新的键值对，并将该节点着为红色。
修复红黑树性质：由于插入操作可能破坏红黑树的性质（如两个连续的红色节点），需要通过旋转（左旋、右旋）和重新着色操作来恢复红黑树的性质。例如，如果插入节点的父节点和叔父节点都是红色，需要将父节点和叔父节点着为黑色，祖父节点着为红色；如果出现红色节点父子关系且不符合红黑树规则，通过左旋或右旋操作调整树结构。

查找操作

从根节点开始，根据 operator< 比较待查找键与当前节点的键。
如果待查找键等于当前节点的键，则找到目标节点，返回对应的值。
如果待查找键小于当前节点的键，则向左子树移动；否则向右子树移动，继续比较，直到找到目标节点或遇到空节点（表示未找到）。

星途面试题库

面试题：深入剖析 C++ map 容器键值存储实现细节

知识考点

面试题答案

1. 实现比较函数（operator< 重载）

2. 内存管理注意事项

3. 性能相关问题

4. map 容器插入和查找时红黑树的操作步骤

插入操作

查找操作