首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >是否有一个标准集装箱,可以很好地利用?

问是否有一个标准集装箱,可以很好地利用?
EN

Stack Overflow用户
提问于 2019-02-12 20:24:59
回答 2查看 156关注 0票数 1

我在找一个能根据外部值进行排序的容器。例如,假设我的元素是: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那样工作的东西,但是由于这种类型的不一致,所以我不能使用它。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2019-02-12 20:39:01

要对与X相关的东西排序,从排序列表开始,只需查找列表中的'X‘应该在哪里。

现在合并(如在std::merge中)的两个范围“后X”和“在X之前,向后”。

提高效率的诀窍是不动任何东西。将“排序”作为延迟或包装操作应用。

您到底是如何做到这一点,将取决于您需要什么操作。如果您正在编写优先级队列,则可以使用std::map并天真地插入内容。

然后,要找到最低的元素,使用下/上界并比较(最多)两个候选元素,看哪一个是“较低”。

这会给你O(lg n)流行音乐的最低价。

如果您需要按该顺序迭代,则必须编写一个“合并向前范围”。“合并前向范围”拥有两个前向迭代器范围和一个比较函数对象;它的迭代器是前向迭代器,并且在每个范围内保留一个迭代器,并且取消引用和前进操作在“最低”迭代(其中端点永远不是最低的)上,并且==按元素工作。

即O(1)在容器上前进。

票数 3
EN

Stack Overflow用户

发布于 2019-02-12 20:39:22

为了简单起见,假设您正在根据给定整数的距离对整数容器进行排序,然后考虑下面的示例(已经按递增顺序排序):

代码语言:javascript
复制
1 2 5 12 20 100

如果您想按照距离到10来排序,那么结果是

代码语言:javascript
复制
12 5 2 1 20 100

现在按距离排序到15

代码语言:javascript
复制
12 20 5 2 1 100

这些元素似乎完全被重新排序了,但是,如果您将排序分为两个步骤,那么很明显,不同的排序是如何相互关联的。

让我们从原来的

代码语言:javascript
复制
1 2 5 12 20 100
     ^------------ 10
        ^--------- 15

现在,如果您按距离到10排序,您已经完成了一半的工作,因为这两个部分

代码语言:javascript
复制
5 2 1          // first part reversed
12 20 100      // second part

已经排序了,您只需合并它们(简单的O(N))。按距离到15的排序相同:

代码语言:javascript
复制
12 5 2 1   // already sorted
20 100     // already sorted

把它们合并到O(N)中,你就完成了。

这只是为了概述这个想法。我可能会使用一个简单地按递增顺序排序的std::vector,然后创建所需的排序非常便宜。甚至可以认为,保持vector本身总是按递增顺序排序,并且只为不同排序的视图提供迭代器。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54658193

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档