向量和许多索引

情况：我正在读取由几何块组成的3D文件格式。每个块依次引用（使用索引）到任何块（类似于可能可见的集合）。向量和许多索引

我正在设计的程序应该允许在列表中的任何位置插入和删除块。这意味着很多参考文献将会失效。此

一个解决办法是阅读文件时给指数转换为指针，所以有这样一个指针的向量：

class block; 

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

    // more data 
}; 

std::vector<block*> a_blocks;

在我的程序，用户可以查看每个引用块a_blocks数组的块。在这里，我想把它们显示为索引。当在指标上使用指针时，这意味着我将不得不为每个块执行std::find以在数组中找到它的索引。这会造成我设想的很多开销？

哪种方法更好，哪些性能好处？

来源

2014-02-10 Midas

所以参考文献最初是以索引的形式给出的。如果某个引用的索引块被删除，应该发生什么？应该保留无效的参考吗？如果在相同的索引处创建一个新块，会发生什么？现在的旧参考文献是否指向这个新的区块？ – Nabla

是你的问题，你只能给'block *'找不到你的'block'的索引？为什么你不能在其中存储块的索引？并且在块被插入/删除时更新索引？ – David

@Nabla：当一个块被移除时，引用应该被保留，但是（最好）被设置为NULL，以便用户可以调整或移除它们。在相同索引处创建新块时，引用仍应指向旧块。 – Midas

我会怎么做，（如果我理解正确你的问题）：保持指数：

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

    // more data 
}; 

std::vector<block*> a_blocks;

然后，而不是remove元素，将其重置为nullptr
孔中或者在末尾添加元素矢量。最后，您可能有一个函数来折叠哪些删除洞并修复索引。

另一种方法是：

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 
};

上删除，您可以快速访问到它参考块。
在插入/删除时，必须在线性时间内更新所有索引

来源

2014-02-11 12:49:41 Jarod42

谢谢，但这并不能解决问题。删除或插入块时，应更新用户可见的索引以匹配新列表。您提供的解决方案假设索引保持不变，因为您不会将它们从列表中删除。另外，我不明白第二个选项？附加变量的目的是什么？（...）我想手动更新每个块中的每个索引（如Dave提出的）是唯一的方法去... – Midas

@Midas：对于第二个选项，索引是Dave提出的，'back_reference'是当前块被删除时要修改的块列表（如果'a_references'是被查看的块，'back_reference'是块的哪个视图当前块）。 – Jarod42

向量和许多索引

回答

相关问题