我有选择正确的数据结构/ 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中的索引。
谢谢，我刚刚搜索订单统计树。正如你所说，他们有一个方法返回元素的“排名”，这正是我需要的。另外，扩展一个行为似乎是一个订单统计树是非常有趣的。 –