我正在寻找一个容器，它可以很好地根据外部值进行排序。因此，例如，假设我的元素是:pair<char, int>这对 key 不是唯一的。比方说我有:
-
'a',0 -
'j',13 -
'm',42 -
'z',100
我想根据接近 char foo 来维护此容器的排序，这可能会改变，此时我需要对容器进行“动态排序”。例如，假设 foo开始为 'm'我希望这些元素按顺序排序。
-
'm',42 -
'j',13 -
'a',0 -
'z',100
现在foo更改为 'i'我需要在这个容器上调用 resort 来获取订单:
-
'j',13 -
'a',0 -
'm',42 -
'z',100
我知道我可以用 vector 做到这一点.那是我最好的选择吗？我真的在寻找类似 map 的东西但由于排序不一致，我不能使用它。
最佳答案
要对相对于 X 的内容进行排序，从排序列表开始，只需找到“X”在列表中的位置即可。
现在合并(如在 std::merge 中)“X 之后”和“X 之前，向后”的两个范围。
提高效率的诀窍是不要实际移动任何东西。将“排序”应用为惰性或包装操作。
具体如何操作取决于您需要的操作。如果您正在编写优先级队列，您可能会使用 std::map 并天真地插入东西。
然后要找到最低元素，使用下限/上限并比较(最多)两个候选元素以查看哪个元素“更低”。
这会给你 O(lg n) pop 最低。
如果您需要按该顺序迭代，则必须编写“合并前向范围”。 “合并前向范围”拥有两个前向迭代器范围和一个比较函数对象；它的迭代器是前向迭代器，并在每个范围内保留一个迭代器，取消引用和推进操作在“最低”的迭代器上(其中 end 永远不会最低)，并且 == 按元素工作。
在容器上前进的时间复杂度为 O(1)。
关于c++ - 是否有适合度假的标准容器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54658193/