我在找一个能根据外部值进行排序的容器。例如,假设我的元素是:pair<char, int> --这对的键并不是唯一的。比方说,我有:
'a',0'j',13'm',42'z',100我希望通过接近char foo来维护这个容器的排序,这可能会发生变化,此时我需要对容器进行“动态排序”。例如,假设foo从'm'开始,我希望这些元素按顺序排序。
'm',42'j',13'a',0'z',100现在,foo更改为'i',我需要对这个容器进行一个度假村调用,以获得订单:
'j',13'a',0'm',42'z',100我知道我可以用vector来完成这个任务。这是我最好的选择吗?我真的在寻找像map那样工作的东西,但是由于这种类型的不一致,所以我不能使用它。
发布于 2019-02-12 20:39:01
要对与X相关的东西排序,从排序列表开始,只需查找列表中的'X‘应该在哪里。
现在合并(如在std::merge中)的两个范围“后X”和“在X之前,向后”。
提高效率的诀窍是不动任何东西。将“排序”作为延迟或包装操作应用。
您到底是如何做到这一点,将取决于您需要什么操作。如果您正在编写优先级队列,则可以使用std::map并天真地插入内容。
然后,要找到最低的元素,使用下/上界并比较(最多)两个候选元素,看哪一个是“较低”。
这会给你O(lg n)流行音乐的最低价。
如果您需要按该顺序迭代,则必须编写一个“合并向前范围”。“合并前向范围”拥有两个前向迭代器范围和一个比较函数对象;它的迭代器是前向迭代器,并且在每个范围内保留一个迭代器,并且取消引用和前进操作在“最低”迭代(其中端点永远不是最低的)上,并且==按元素工作。
即O(1)在容器上前进。
发布于 2019-02-12 20:39:22
为了简单起见,假设您正在根据给定整数的距离对整数容器进行排序,然后考虑下面的示例(已经按递增顺序排序):
1 2 5 12 20 100如果您想按照距离到10来排序,那么结果是
12 5 2 1 20 100现在按距离排序到15
12 20 5 2 1 100这些元素似乎完全被重新排序了,但是,如果您将排序分为两个步骤,那么很明显,不同的排序是如何相互关联的。
让我们从原来的
1 2 5 12 20 100
^------------ 10
^--------- 15现在,如果您按距离到10排序,您已经完成了一半的工作,因为这两个部分
5 2 1 // first part reversed
12 20 100 // second part已经排序了,您只需合并它们(简单的O(N))。按距离到15的排序相同:
12 5 2 1 // already sorted
20 100 // already sorted把它们合并到O(N)中,你就完成了。
这只是为了概述这个想法。我可能会使用一个简单地按递增顺序排序的std::vector,然后创建所需的排序非常便宜。甚至可以认为,保持vector本身总是按递增顺序排序,并且只为不同排序的视图提供迭代器。
https://stackoverflow.com/questions/54658193
复制相似问题