c++ - vector 和许多索引

Question

情况:我正在读取由几何 block 组成的 3D 文件格式。每个 block 依次具有对任何 block (类似于潜在可见集)的引用(使用索引)。

我正在设计的程序应该允许在列表中的任何位置插入和删除 block 。这意味着很多引用将变得无效。

一个解决方法是在读取文件时将索引转换为指针，这样就有一个这样的指针 vector :

class block;

class block
{
    std::vector<block*> a_references;

    // more data
};

std::vector<block*> a_blocks;

在我的程序中，用户可以查看a_blocks 数组中每个 block 的引用 block 。在这里，我想将它们显示为索引。在索引上使用指针时，这意味着我必须为每个 block 执行 std::find 以在数组中找到它的索引。我认为这会导致大量开销？

哪种方法更好，有哪些性能优势？

Answer 1

我会做什么(如果我正确理解了您的问题):保留索引:

class block
{
    std::vector<std::size_t> a_references; // some indices in a_blocks

    // more data
};

std::vector<block*> a_blocks;

然后不是删除元素，而是将其重置为 nullptr
在孔中或 vector 末尾添加元素。最后，您可能有一个折叠功能，它可以删除漏洞并修复索引。

另一种方法是:

class block
{
    std::vector<block*> a_references;
    std::vector<block*> back_references; // reference each block where `this` is in a_reference 
    std::size_t index; // index in a_blocks 

    // more data
};

删除后，您可以快速访问引用它的 block 。
在插入/删除时，您必须在线性时间内更新所有索引