面试题：C++内存布局与数据结构深度优化

C++对象内存布局

非虚函数类
- 成员变量：按声明顺序依次存储在对象内存空间中。例如：

class NonVirtualClass {
    int a;
    double b;
};

在64位系统中，int通常占4字节，double占8字节，对象NonVirtualClass大小为12字节（可能存在内存对齐，实际大小可能为16字节），a在前，b在后。

非虚函数：不占用对象内存空间，函数代码存储在代码段。调用非虚函数时，通过对象地址直接访问函数地址。

含虚函数类
- 虚函数表（vtable）：每个含有虚函数的类都有一个虚函数表，存储在全局数据区（静态存储区）。虚函数表是一个指针数组，每个元素是该类虚函数的地址。
- 虚函数表指针（vptr）：对象内存空间的起始位置存储一个指向虚函数表的指针（vptr）。例如：

class VirtualClass {
    virtual void func() {}
    int a;
};

在64位系统中，VirtualClass对象大小至少为16字节（8字节vptr + 4字节int + 4字节内存对齐）。 3. 继承体系下

无虚函数覆盖：派生类对象内存布局是基类对象在前，派生类新增成员变量在后。例如：

class Base {
    int a;
};
class Derived : public Base {
    double b;
};

Derived对象内存布局中，先存储Base类的a，再存储Derived类的b。

有虚函数覆盖：如果派生类覆盖了基类的虚函数，虚函数表中对应虚函数的地址会被替换为派生类虚函数的地址。派生类对象内存布局同样是基类对象在前（含基类vptr），若派生类新增虚函数，虚函数表会扩展。

哈希表嵌套红黑树优化方案

内存布局优化
- 对象池：
  - 原理：预先分配一块连续的内存空间作为对象池，用于创建红黑树节点和哈希表桶。对于红黑树节点，由于其结构相对固定（如包含键值对、左右子节点指针、父节点指针、颜色等），在对象池中分配内存可减少内存碎片。对于哈希表桶，同样在对象池中分配，可使哈希表的桶在内存中连续分布。
  - 对系统资源影响：内存占用方面，对象池需要预先分配一定大小的内存，可能会增加初始内存占用，但减少了频繁的内存分配和释放，从而减少内存碎片。缓存命中率提高，因为对象池内的数据在内存中连续，当访问红黑树节点或哈希表桶时，更容易命中缓存。
- 内存对齐优化：
  - 原理：确保红黑树节点和哈希表桶中的成员变量按合适的字节边界对齐。例如，对于64位系统，指针类型（通常8字节）应按8字节边界对齐，整数类型（如int 4字节）按4字节边界对齐等。合理的内存对齐可提高CPU访问效率。
  - 对系统资源影响：可能会增加一些内存占用，因为内存对齐可能会在成员变量之间填充一些字节，但能显著提高CPU访问速度，进而提高缓存命中率，因为CPU访问对齐数据时效率更高。
缓存利用优化
- 局部性原理利用：
  - 原理：尽量让频繁访问的数据在内存中靠近。例如，在哈希表中，将经常被访问的键值对所在的桶放置在内存中相邻位置。对于红黑树，在插入和删除操作时，尽量保持树的结构稳定，使经常访问的节点在内存中靠近。这可以利用空间局部性原理，当一个数据被访问时，其相邻数据也更有可能被访问。
  - 对系统资源影响：缓存命中率提高，因为当一个缓存行被加载到缓存中时，相邻的数据也被加载进来，增加了后续访问命中缓存的概率。内存占用基本不受影响。
- 缓存预取：
  - 原理：在预计会访问某个红黑树节点或哈希表桶之前，提前将其数据加载到缓存中。例如，在遍历红黑树时，根据树的遍历顺序，提前预测下一个要访问的节点，并通过硬件或软件预取机制将其数据加载到缓存。
  - 对系统资源影响：缓存命中率提高，因为数据提前被加载到缓存中等待访问。可能会增加一些系统开销，因为预取操作需要额外的指令和硬件支持，但整体性能提升通常大于开销。

星途面试题库

面试题：C++内存布局与数据结构深度优化

知识考点

面试题答案

C++对象内存布局

哈希表嵌套红黑树优化方案