c++ - 对重叠范围使用 std::merge 是否可以接受

Question

我有一个算法需要多次应用集合并集来增加整数集。为了提高效率，我将集合表示为已排序的 vector ，以便可以通过合并它们来获得它们的并集。

合并两个排序 vector 的经典方法是这样的:

void inmerge(vector<int> &a, const vector<int> &b) {
  a.reserve(a.size() + b.size());
  std::copy(b.begin(), b.end(), std::back_inserter(a));
  std::inplace_merge(a.begin(), a.end() - b.size(), a.end());
}

不幸的是，由于分配开销，std::inplace_merge 在这种情况下似乎比 std::sort 慢得多。最快的方法是直接使用 std::merge 输出到其中一个 vector 中。为了不在读取值之前写入值，我们必须从末尾开始，如下所示:

void inmerge(vector<int> &a, const vector<int> &b) {
  a.resize(a.size() + b.size());
  orig_a_rbegin = a.rbegin() + b.size();
  std::merge(orig_a_rbegin, a.rend(), b.rbegin(), b.rend(), a.rend(), [](int x, int y) { return x > y; });
}

可以肯定的是，merge 的实现绝不会写入比读取更多的元素，因此这是安全的做法。不幸的是，C++ 标准(甚至 C++17 草案)禁止这样做:

The resulting range shall not overlap with either of the original ranges.

如果我知道自己在做什么，可以忽略此限制吗？

Answer 1

不，忽略标准的要求(或您正在使用的某些库的任何其他文档)永远不会成功。您可能知道您 在做什么，但您确定您知道库 在做什么 - 或者可能在下一个版本中做什么？

例如，合并算法可以检测到至少有两个范围是反向范围，展开它们(然后展开或反转第三个)，然后在另一个方向上进行合并。只要保持先决条件，就没有明显的差异，但由于反向迭代器的开销消失了，可能会快一点。但这真的会搞砸你的代码。