有没有有序容器可以实现O(n)的有序删除和遍历？我正在尝试执行以下操作:
Hello -> 1,2,3,4,5,6
Hello1 -> 24,15,13,10,8,7
我需要能够尽快从 Hello 或 Hello1 连续插入和删除。我在考虑使用优先级队列，但每次我想删除我都花费 O(logn) 调整，所以 n 次删除将花费我 O(nlogn) 时间来保持内部结构有序。有没有什么数据结构可以在 O(n) 时间内完成这个任务？
最佳答案
只需使用 std::vector，并在顶部添加一些排序；不要每次都使用 std::sort - 使用合并排序。
复杂性很重要，但当数据集较小时，内存分配和缓存未命中所花费的时间将远远超过这一点。通常，对其进行概要分析，但我认为在这种情况下，vector 会很好。
仔细考虑是否需要保持结构始终有序；你可以在诉诸之前插入一些项目吗？ 2 个 vector 并在查找时合并怎么样？仔细考虑你的算法；例如，您可以在 O(n) 中删除任意数量的项目。
关于c++ - 存储内部排序的 map 元素的最快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15722622/