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;

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

我的问题如下 - 在不大幅重写算法核心的情况下，考虑到该算法首先在范围的开始？现在，我唯一的想法是引入额外的变量来“假装”我们在第一步备份了迭代器，或者用特殊的迭代器适配器装饰迭代器，这样您就可以通过跟踪在开始之前进行备份在范围开始之前您有多少个逻辑步骤。这些看起来都不优雅......我错过了什么吗？有直接的解决方案吗？

谢谢!

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);
        }
    }
}