c++ - 使用 STL 迭代器实现 Bentley-McIlroy 三向分区？

Question

在他们的谈话中 "Quicksort is Optimal" , Sedgewick 和 Bentley 指的是快速排序分区步骤的修改版本，称为 Bentley-McIlroy 三路分区。这个版本的分区步骤通过始终从剩余的元素中提取主元素的拷贝来优雅地适应包含相等键的输入，确保在包含重复项的数组上调用时算法仍然执行良好。

此分区步骤的 C 代码转载于此:

void threeWayPartition(Item a[], int l, int r)
{ 
  int i = l-1, j = r, p = l-1, q = r; Item v = a[r];
  if (r <= l) return;
  for (;;)
    { 
       while (a[++i] < v) ;
       while (v < a[--j]) if (j == l) break;
       if (i >= j) break;
       exch(a[i], a[j]);
       if (a[i] == v) { p++; exch(a[p], a[i]); }
       if (v == a[j]) { q--; exch(a[j], a[q]); }
    } 
  exch(a[i], a[r]); j = i-1; i = i+1;
  for (k = l; k < p; k++, j--) exch(a[k], a[j]);
  for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
}

我有兴趣将此版本的快速排序实现为 STL 算法(只是为了我自己的启发，而不是作为非常快速的 std::sort 的替代品)。为了做到这一点，理想情况下，我会接受一系列 STL 迭代器作为算法的输入，这些迭代器定义了要排序的范围。因为快速排序不需要随机访问，所以我希望这些迭代器是双向迭代器，因为这会使算法更通用，并允许我对 std::list 和其他仅支持的容器进行排序双向访问。

但是，这有一个小问题。请注意，三向分区算法的第一行包含以下内容:

int i = l-1, p = l-1;

这最终会创建两个位于要划分的范围之前的整数，这很好，因为在循环体中，它们在使用之前会递增。但是，如果我用双向迭代器替换这些索引，则此代码不再具有已定义的行为，因为它在要排序的范围开始之前支持迭代器。

我的问题如下 - 在不重写算法核心的情况下，有没有一种方法可以使这段代码适应使用 STL 风格的迭代器，因为该算法首先备份一个迭代器范围的开始？现在，我唯一的想法是引入额外的变量来“假装”我们在第一步备份了迭代器，或者用特殊的迭代器适配器装饰迭代器，允许您通过跟踪在开始之前备份在范围开始之前你有多少逻辑步骤。这些看起来都不是很优雅......我错过了什么吗？有直接的解决方案吗？

谢谢!

Answer 1

基本不重写算法核心

这几乎限制了您尝试破解边界问题的方法，因此您需要使用自定义迭代器适配器，或将迭代器包装在 boost::optional 或其他东西中相似，所以您知道什么时候是第一次访问。

更好的做法是修改算法以适应手头的工具(这正是 STL 的目的，对不同的迭代器类型使用不同的算法)。

我不知道this is correct , 但它以不同的方式描述算法，不需要迭代器越界。

---

编辑:话虽如此，我已经试过了。此代码未经测试，因为我不知道给定输入后的输出应该是什么样子 - 有关详细信息，请参阅评论。它只会有机会为双向/随机访问迭代器工作。

#include <algorithm>
#include <iterator>

template <class Iterator>
void three_way_partition(Iterator begin, Iterator end)
{
    if (begin != end)
    {
        typename Iterator::value_type v = *(end - 1);

        // I can initialise it to begin here as its first use in the loop has
        // changed to post-increment (its pre-increment in your original
        // algorithm).
        Iterator i = begin;

        Iterator j = end - 1;

        // This should be begin - 1, but thats not valid, I set it to end
        // to act as a sentinal value, that way I know when im incrementing
        // p for the first time, and can set it to begin.
        Iterator p = end;

        Iterator q = end - 1;

        for (;;)
        {
            while (*(i++) < v);

            while (v < *(--j))
            {
                if (j == begin)
                {
                    break;
                }
            }

            if (std::distance(i, j) <= 0)
            {
                break;
            }

            if (*i == v)
            {
                if (p == end)
                {
                    p = begin;
                }
                else
                {
                    ++p;
                }

                std::iter_swap(p, i);
            }

            if (v == *j)
            {
                --q;
                std::iter_swap(j, q);
            }
        }

        std::iter_swap(i, end - 1);

        j = i - 1;
        i++;

        for (Iterator k = begin; k < p; ++k, --j)
        {
            std::iter_swap(k, j);
        }

        for (Iterator k = end - 2; k > q; --k, ++i)
        {
            std::iter_swap(i, k);
        }
    }
}