c++ - 减少内存分配 C++

Question

我很难想出一个好的策略来减少以下问题的内存分配:

我正在 build 一棵树。一开始，我只有包含一些数据的根(索引列表 (std::vector))。我分成两部分，其中一部分索引转到左边的 child ，另一部分转到右边的 child 。我不知道有多少人会向左/向右。一次，我完成了对根的处理，不再需要为其存储索引。事实上，我只对那些叶子感兴趣。此外，每次拆分都可以添加额外的数据!所以，如果根有 20 个元素，那么在拆分之后，左边的可能有 12 个元素，右边的可能有 10 个。

在每个节点中，我保留一个包含这些索引的 std::vector。当我添加元素时，我 push_back() 导致许多内存分配的元素。

保留索引的好策略是什么？

问题与SBVH数据结构的生成有关。

代码:

struct Node {
     std::vector<unsigned> indices_;
     // ... some other stuff here
}
void partition(Node* node) {
    Node* left = new Node();
    Node* right = new Node();
    float axis = findSplitPosition(node);

    for(size_t i = 0; i < node->indices_.size(); ++i) {
        if (index is strictly left on axis) {
            left->indices_.push_back(node->indices_[i]);
        } else if(index is strictly right on axis) {
            right->indices_.push_back(node->indices_[i]);
        } else {
            // it intersects the axis -> add to left and right
            left->indices_.push_back(node->indices_[i]);
            right->indices_.push_back(node->indices_[i]);
        }
    }

    // root indices no longer needed
    node->indices_.clear();

}

Answer 1

如果每个节点都必须自己维护一个动态列表，那么您可以使用std::vector::reserve()在调用所有这些 push_back() 之前。

但是，如果一旦您设置了根并且初始 vector 保持不变，整个长度就确定了，然后您只是在每个节点之间“拆分它”，那么节点本身可以​​简单地保存指向内部数据的指针初始 vector ——从而消除了围绕该数据结构的几乎所有分配。