c++ - std::merge 和相等的元素顺序

Question

std::merge 在其输入列表中保留相等元素的顺序。它是否保证第一个列表中的元素出现在第二个列表中的相等元素之前，或者该保证仅适用于单个输入列表中的相等元素？

例子:

List1 有 1 个元素，A。List2 有 1 个元素，B。比较器认为 A 和 B 相等。

如果我std::merge(list1.begin(), list1.end(), list2.begin(), list2.end(), out, comparator)，就是相对顺序A 和 B 在输出中的定义？

我的意见是标准在这种情况下没有定义顺序。

Answer 1

C++14 标准草案 (n3797):

17.6.5.7/1

When the requirements for an algorithm state that it is “stable” without further elaboration, it means:
— For the merge algorithms, for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).