如何找到两个迭代器中间的迭代器？

Question

我正在尝试将我的快速排序算法实现转换为一个模板，以便可以与除向量之外的其他容器一起使用。

最初，我使用索引来找到中间索引，例如(first + last) / 2。如何在两个迭代器中找到中间位置呢？

- Roy

---

顺便问一下，为什么要实现自己的快速排序？std::sort应该已经包含了快速排序，并且还有stable_sort、partial_sort_copy等函数可用。 - StilesCrisis

我正在做欧拉计划，想研究一些排序算法，但如果我打算在将来重用它，你是对的 - 我最好使用std::sort。 - Roy

Answer 1

std::distance 可以尽可能高效地测量两个迭代器之间的距离。

std::advance 可以尽可能高效地增加一个迭代器。

虽然如此，我仍然不想使用快速排序来排序链表 :)

- StilesCrisis

---

为什么不能使用快速排序算法对链表进行排序？因为在快速排序中查找中间节点是不必要的。 - Dietrich Epp

@DietrichEpp：没错，但是std::sort特别要求随机访问迭代器也是有原因的。 - Nicol Bolas

我相信有技术原因，但与算法无关。对于链表来说，快速排序很容易实现。 - Dietrich Epp

不断地在列表中上下遍历是效率低下的。你会大量时间访问 "node->next" 和 "node->prev"，而几乎没有时间实际执行排序。从性能角度来看，将数据复制到向量中并在那里进行排序可能会更好。 - StilesCrisis

Answer 2

使用：

http://www.cplusplus.com/reference/std/iterator/distance/

以及

http://www.cplusplus.com/reference/std/iterator/advance/

这两个链接提供了关于C++中迭代器的距离和前进操作的详细说明。

- Anycorn

Answer 3

这样怎么样？

bool isMovingFirst = true;
while(first != last) {
  if(isMovingFirst) {
    ++first;
  } else {
    --last;
  }
  isMovingFirst = !isMovingFirst;
}

- Keldon Alleyne

---

通常认为重新实现标准库中已有的东西是不好的做法。不要重复自己，这很重要。 - StilesCrisis

哦，我完全同意。我只写它是因为它在相同的步骤中运行（而不调用advance）。但是，distance + advance仍然与quicksort的O（n log n）时间复杂度相比较低成本，所以在这种情况下我肯定认为你的观点是有效的。 - Keldon Alleyne

好的，如果我们要追求效率，你有一个完全不必要的额外布尔值...试试这个：for (;;) { if (first == last) break; ++first; if (first == last) break; --last;
} - StilesCrisis

Answer 4

要找到中间迭代器，您应该使用：

first + (last - first) / 2

- vladinkoc

---

这不正确。你的解决方案需要随机访问迭代器。OP要求一个与容器无关的解决方案。 - user1599559