存储C++基类与派生类实例的高效容器实现方案咨询

回答 #

1. 标准容器适配性

没有完全匹配需求的现有标准容器：

• 常规多态存储方案std::vector<std::unique_ptr<A>>虽然满足尾插、遍历删除的需求，但默认用new分配的对象内存分散，缓存命中率低，不符合你遍历优先的性能要求
• std::list/std::forward_list的插入删除效率高，但遍历缓存局部性极差，性能远低于连续存储结构
• 标准库没有原生支持多态连续存储的容器，需要自定义实现。

2. 自定义容器实现方案

结合你的需求（遍历优先级最高、删除仅在遍历中执行、总对象规模小），推荐两种落地性极强的方案：

方案1：带延迟删除的连续内存池方案（最优适配你的场景）

核心思路是用连续内存池存储所有多态实例，配合指针数组和删除标记实现高性能遍历和删除：

• 底层用std::vector<std::byte>作为预分配的连续内存块，提前分配足够容纳所有预期对象的空间（比如1MB空间足够存储上万个你的小尺寸派生类对象）
• 维护一个std::vector<A*>的指针数组，所有元素指向内存池中的有效实例，数组本身连续存储，遍历效率接近原生数组
• 维护一个同长度的std::vector<bool>删除标记数组，删除操作仅给对应位置打标记，不需要立刻释放或移动内存
• 遍历的时候直接迭代指针数组，跳过标记为删除的元素即可，缓存命中率极高
• 等到内存池剩余空间不足，或者每次遍历结束后，统一执行内存压缩：将所有未标记删除的对象移动到内存池头部，重建指针数组和删除标记数组即可，因为总对象规模小，压缩的开销可以忽略不计。

方案2：同类型分区存储方案（适合派生类固定的场景）

如果后续派生类扩展频率低，可以为每个派生类单独维护一个连续存储的std::vector：

• 比如内部存std::vector<A>、std::vector<B>两个独立数组，同类型实例完全连续，缓存命中率达到最高
• 迭代器用简单的类型擦除逻辑封装，遍历的时候依次遍历每个类型的数组，对外统一暴露基类A&的访问接口
• 插入时直接对应到派生类的数组尾插，删除时同样可以打标记延迟清理，性能比内存池方案更高，缺点是新增派生类需要修改容器代码。

3. 预分配连续内存的可行性

完全可以实现，不需要提前知道单个元素的大小：

• 预分配阶段只需要确定内存池总容量（根据你预计的最大总对象数乘以最大派生类大小预留即可，你的场景下预留1~2MB完全足够）
• 插入对象时先做地址对齐，直接在内存池的当前偏移位置用定位new构造对象，再把地址存入指针数组即可
• 就算后续有更大的派生类加入，只需要调整预分配的总容量即可，不需要修改核心逻辑。

简化实现示例 #

#include <vector>
#include <cstddef>
#include <memory>
#include <algorithm>

int globalB = 5;

class A {
public:
    A(int a) : a(a) {}
    virtual ~A() = default;

    int a;
    virtual int get_b() {
        return globalB;
    }
};

class B : public A {
public:
    B(int a, int b) : A(a), b(b) {}
    int b;
    int get_b() override {
        return b;
    }
};

class Container {
public:
    // 预分配1MB内存池，足够使用
    Container() {
        m_memory.resize(1024 * 1024);
        m_current_offset = 0;
    }

    ~Container() {
        // 手动析构所有有效对象
        for (size_t i = 0; i < m_ptrs.size(); i++) {
            if (!m_deleted[i]) {
                m_ptrs[i]->~A();
            }
        }
    }

    void add_element(int a) {
        // 对齐到最大对齐要求
        size_t align = alignof(A);
        size_t offset = (m_current_offset + align - 1) & ~(align - 1);
        A* ptr = new (m_memory.data() + offset) A(a);
        m_ptrs.push_back(ptr);
        m_deleted.push_back(false);
        m_current_offset = offset + sizeof(A);
    }

    void add_element(int a, int b) {
        size_t align = alignof(B);
        size_t offset = (m_current_offset + align - 1) & ~(align - 1);
        B* ptr = new (m_memory.data() + offset) B(a, b);
        m_ptrs.push_back(ptr);
        m_deleted.push_back(false);
        m_current_offset = offset + sizeof(B);
    }

    void remove_a0_elements() {
        // 遍历过程中打删除标记
        for (size_t i = 0; i < m_ptrs.size(); i++) {
            if (!m_deleted[i] && m_ptrs[i]->a == 0) {
                m_deleted[i] = true;
            }
        }
        // 立刻执行压缩（也可以延迟到下次插入前执行）
        compact();
    }

    // 范围for支持，迭代器直接用指针数组的迭代器即可，跳过已删除元素
    struct Iterator {
        using value_type = A;
        using difference_type = std::ptrdiff_t;
        using pointer = A*;
        using reference = A&;
        using iterator_category = std::forward_iterator_tag;

        Iterator(std::vector<A*>::iterator ptr_it, std::vector<bool>::iterator del_it, std::vector<A*>::iterator end)
            : m_ptr_it(ptr_it), m_del_it(del_it), m_end(end) {
            skip_deleted();
        }

        reference operator*() const { return **m_ptr_it; }
        pointer operator->() const { return *m_ptr_it; }

        Iterator& operator++() {
            ++m_ptr_it;
            ++m_del_it;
            skip_deleted();
            return *this;
        }

        bool operator==(const Iterator& other) const { return m_ptr_it == other.m_ptr_it; }
        bool operator!=(const Iterator& other) const { return !(*this == other); }

    private:
        std::vector<A*>::iterator m_ptr_it;
        std::vector<bool>::iterator m_del_it;
        std::vector<A*>::iterator m_end;

        void skip_deleted() {
            while (m_ptr_it != m_end && *m_del_it) {
                ++m_ptr_it;
                ++m_del_it;
            }
        }
    };

    Iterator begin() { return Iterator(m_ptrs.begin(), m_deleted.begin(), m_ptrs.end()); }
    Iterator end() { return Iterator(m_ptrs.end(), m_deleted.end(), m_ptrs.end()); }

private:
    std::vector<std::byte> m_memory;
    size_t m_current_offset;
    std::vector<A*> m_ptrs;
    std::vector<bool> m_deleted;

    void compact() {
        size_t new_offset = 0;
        std::vector<A*> new_ptrs;
        std::vector<bool> new_deleted;

        for (size_t i = 0; i < m_ptrs.size(); i++) {
            if (m_deleted[i]) {
                m_ptrs[i]->~A();
                continue;
            }
            // 移动对象到新位置
            size_t align = m_ptrs[i]->get_b() == globalB ? alignof(A) : alignof(B);
            size_t offset = (new_offset + align - 1) & ~(align - 1);
            A* new_ptr = new (m_memory.data() + offset) A(std::move(*m_ptrs[i]));
            new_ptrs.push_back(new_ptr);
            new_deleted.push_back(false);
            m_ptrs[i]->~A();
            new_offset = offset + (m_ptrs[i]->get_b() == globalB ? sizeof(A) : sizeof(B));
        }

        m_ptrs.swap(new_ptrs);
        m_deleted.swap(new_deleted);
        m_current_offset = new_offset;
    }
};

// 示例用法和你给出的完全兼容
static int example_usage() {
    Container container;
    for (int a = 1; a <= 100; a++) {
        container.add_element(a);
        container.add_element(a, a);
    }

    int sum = 0;
    for (auto& elem : container) {
        sum += elem.get_b();
    }

    return sum;
}

内容的提问来源于stack exchange，提问作者Samufi