现代C++兼容插入排序

Question

这是对我以前的排序实现问题的一种后续，特别是插入排序和现代C++成语。任何看到这篇文章的人都可以看到，我是如何获得一种典型的C风格分类的，你可以通过访问我以前的分类评论在网上到处找到。

作为一次面试的回顾，我正在撰写我以前见过的符合现代C++的排序算法版本。这篇文章是关于插入排序和插入排序的。

// Shift/bubble each element toward the front into a sorted sub-array
template<typename BdIterator, typename Comparator = std::less<typename std::iterator_traits<BdIterator>::value_type>>
void sort_insertion(BdIterator beg, BdIterator end, Comparator cmp = Comparator())
{
    BdIterator front, cur, prev;
    // Assume the first element is sorted.
    for (front = beg + 1u; front != end; ++front)
    {
        cur = front;
        prev = cur - 1u;
        // Bubble the "next" element towards the front by swapping it with its 
        // "prev" neighbor until it is in its sorted position.
        while (cur != beg && cmp(*cur, *prev))
            std::iter_swap(cur--, prev--);
    }
}

和以前一样，我正在寻找算法本身可能遗漏的任何性能优化，以及本例中可能没有遵守的现代C++结构。

一个具体的问题是，我要处理的是我正在添加和减去的无符号整数，以便移动到容器中的下一个和以前的值。由于无法获得所提供的迭代器的容器类型，所以我看不到一种方法可以使假定容器的size_type添加和减去正确的类型，而不仅仅是无符号/有符号整数。

我正在减去的事实阻止了我将最小Iterator模板类型声明为前向迭代器(我们正在向后移动迭代器)。是否有更好的方法来解决这个问题，还是我应该坚持做最低限度的BiDirectionalIterators？

Answer 1

“我要问的一个具体问题是，我正在添加和减去迭代器中的无符号整数，以移动到容器中的下一个值和前一个值。由于无法获得所提供的迭代器的容器类型，所以我看不到获得假定容器的size_type来添加和减去正确类型的方法，而不仅仅是无符号/有符号整数。”

我刚刚发现std::prev和std::next是在#include 中定义的，我认为这将处理一些签名/无符号不匹配的情况。

对于需要执行更复杂的算术(例如除法或乘法)的其他情况，您可以使用：

std::iterator_traits<BdIterator>::difference_type

std::distance返回std::iterator_traits<BdIterator>::difference_type。

std::next和std::prev以std::iterator_traits<BdIterator>::difference_type为参数。双向迭代器上的算法可能会倒退。

“我正在减去的事实阻止了我将最小的Iterator模板类型声明为前向迭代器(我们正在向后移动迭代器)。有什么更好的方法来解决这个问题，还是我应该坚持做最小的BiDirectionalIterators呢？”

我没有意识到，无论我是否使用std::prev，算法本身都依赖于向前和向后移动迭代器，因此需要BiDirectional迭代器。

有一个更有效的解决方案，它依赖于找到一个洞并鼓起这个孔，然后将值插入到它的排序孔中。

// Shift/bubble each element toward the front into a sorted sub-array
template<typename BidirIt, typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_insertion(BidirIt first, BidirIt last, Comparator cmp = Comparator())
{
    using category = typename std::iterator_traits<BidirIt>::iterator_category;
    static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::value, "This algorithm requires bidirectional iterators.");

    // 1 element containers are sorted; 2 duplicate element containers are sorted.
    if (first != last)
    {
        // Make a hole by removing the element you are checking,
        // and move elements up to that hole until you find the correct position of the element removed.
        // ++cur: Assume the first element is sorted.
        for (BidirIt cur = first; ++cur != last;)
        {
            auto val = std::move(*cur);
            BidirIt next = cur, prev = std::prev(next);
            while (cmp(val, *prev))
            {
                *next = std::move(*prev);
                next = prev;
                if (prev != first) --prev;
                else break;
            }
            // insert value in its sorted hole.
            *next = std::move(val);
        }
    }
}

Answer 2

专注于使用<algorithm>作为更大功能的构建块。在使用双向迭代器进行插入排序的情况下，可以将查找插入点的逻辑与移位分离。

template <class BidirIt, class Compare = std::less<>>
void insertion_sort(BidirIt first, BidirIt last, Compare cmp = Compare{}) {
  if (first == last || std::next(first) == last) {
    return;
  }

  using RevIt = std::reverse_iterator<BidirIt>;
  for (auto curr = std::next(first); curr != last; ++curr) {
    // Reverse Linear Search the insertion point
    const auto insertion =
        std::find_if_not(RevIt(curr), RevIt(first), [=](const auto& elem) {
          return cmp(*curr, elem);
        }).base();

    auto elem = std::move(*curr);
    std::move_backward(insertion, curr, std::next(curr));
    *insertion = std::move(elem);
  }
}