我必须维护一个无序整数列表,其中整数的数量未知。随着时间的流逝,它可能会增加或减少。我需要经常更新此整数列表。我尝试使用vector。但这确实很慢。数组看起来更快,但是由于列表的长度不是固定的,因此需要花费大量时间来调整它的大小。请提出其他选择。
最佳答案
如果值的顺序不重要,请使用hash table。时间为O(1)。我很确定您会在标准模板库中找到一个实现。
失败的话,splay tree会非常快,尤其是如果您要保持列表有序:每次操作的O(ln n)摊销成本,且常数因子非常低。我认为C++ stdlib映射是这样的。
了解您的数据结构。