我有選擇正確的數據結構/ s的問題，這些都是要求：在集合中查找元素的索引，要使用哪個集合？
排序並不元素真的是必須的，重要的是獲得元素的索引，不管內部如何實現，但無論如何，我認爲最好的方法是排序。 元素的索引是集合內部的順序。所以必須使用某種順序。當我刪除一個元素時，從其他元素到最後改變它們的順序/索引。
第一種方法是使用鏈表，但我不想O（n）。 我也想過使用和排序的字典，這會給O（log n）查找/插入/刪除，不是嗎？ 有沒有更好的方法？我知道TRIE會爲O（1）提供常用操作，但我不知道如何獲取元素的索引，我不得不遍歷這個trie並給出O（n），我錯了嗎？
聽起來像你想要一個有序的數據結構，即（平衡）BST。插入和刪除確實是O（lg n），這對於許多應用程序來說已經足夠了。如果你也想元素有一個索引在結構，那麼你會希望有一個order statistic tree（見例如，CLR，算法導論，第14章），它提供了O此操作（LG ñ）。動態重新排序整個集合將是O（n lg n）。
如果「命令集合中的」你的意思是任何隨機的順序是不夠好，那麼就使用動態數組（矢量）：攤餘O（1）追加和刪除，O（ñ LG ñ）但是O（n）查找，直到執行排序，之後查找變爲O（lg n）並進行二分搜索。但是，如果數據要保持排序，刪除將是O（n）。
如果您的數據類似字符串，那麼您可能可以擴展一個樹狀結構，就像BST擴展成爲一個訂單統計樹一樣。
這裏沒有提及數組/矢量，但它符合大多數這些標準。 （請注意，「元素具有唯一的標識號」實際上與數據結構無關;這是否意味着與索引相同的東西？或者它是不可變的關鍵字，它更多地是您放置的數據的函數進入結構......）
在任何情況下都會進行時序權衡：你說鏈表是O（n），但是O（n）表示什麼？您並未真正瞭解添加與刪除與搜索相關的性能要求;哪個更重要？
是的，你是對的，我只是想表明你有一個可用標識符，如果你想使用它。我的意思是O（n）在鏈接列表中插入/刪除/查找。向量是好的，但不是最好的刪除（雖然我可以做一些類型的差距二進制搜索） –
那麼如果您的集合已排序，則不需要O（n）來查找元素。例如可以使用二分查找來確定元素的索引。還有可能在你的數組中寫入關於Entry的簡單包裝，它記住了它在collection中的索引。
謝謝，我剛剛搜索訂單統計樹。正如你所說，他們有一個方法返回元素的「排名」，這正是我需要的。另外，擴展一個行爲似乎是一個訂單統計樹是非常有趣的。 –