向量和許多索引

情況：我正在讀取由幾何塊組成的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

向量和許多索引

回答

相關問題