c++ - 使用迭代器按谓词重新排列

Question

在具有给定签名的函数中，我想以这种方式重新排列序列 [first, last) 的元素，所有满足谓词的元素都放在不满足谓词的元素之前，并将迭代器返回到第一个不满足谓词的元素” t 满足给定的谓词。

我的算法是

• 开始迭代序列
• 如果当前元素不满足谓词，则将其替换为最后一个元素
• 再次检查同一位置上的新元素是否满足
• 如果不是用(last-1)替换，如果是就继续
• 重复，直到我们到达我们已经替换的元素之一

我的代码

template<class Iterator, class Predicate>
Iterator Rearrange(Iterator first, Iterator last, Predicate pred) {
  auto res = first;
  if (first == last) {
    ;
  }
  else {
    auto run = first;
    auto end = last;
    auto tmp = *first;
    while (run != end) {
      if (pred(*run) == false) {
      again: tmp = *(--end);
    *end = *run;
    *run = tmp;
    if (pred(*run) == false) {
      goto again;
    }
      }
      ++run;
    }
  }
  return res;
}

它给了我

terminate called after throwing an instance of 'std::range_error'
  what():  dereferencing end of sequence
Aborted

我找不到也看不懂。也就是说，我可以在某个地方读到我试图在容器外取消引用元素，但在我的程序中看不到它。任何人都可以帮助我修复编码错误或改进我的算法逻辑吗？

Answer 1

如果输入范围非空且其中没有元素满足谓词，您的代码将卡在 goto 循环中而不会再次到达 while。最终，--end 将在 first 之前采用 end。

如果这是一个学习练习，我建议你去掉goto；你不想学习不好的做法，虽然 goto 很少有合法用途，但替换循环不是其中之一。此外，tmp 的舞蹈可以替换为 std::swap。

如果这不是学习练习，只需使用 std::partition这正是你想要的。