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这正是你想要的。