c++ - 特殊排序算法和通用签名

Question

我有一个强大的用例来定义我自己的排序算法，该算法比 STL 中最快的算法更快，并且通过利用底层数据的一些很好的属性，我基本上可以在 O(n) 中进行排序.

到目前为止一切顺利，现在的问题是我想提供一个通用接口(interface)，它适合任何类型的容器，例如T*或std::vector<T>等等，只要几个关键概念适用，例如

• 有一个有效的运算符 [] 可用于访问集合的元素
• 集合的元素支持“小于”可比概念。

为了获得想法，我访问了头文件 <std_algo.h>并找到下面的函数接口(interface)，除了一个细节之外，它与我正在寻找的内容完全匹配，我不知道如何循环底层 _RandomAccessIterator将由编译器自动矢量化，忽略容器类型，这是我的问题......有没有办法让我拥有这一切？自动向量化+通用接口(interface)忽略底层集合类型？

我认为由于“非规范”循环模式，下面的代码不会自动矢量化 while (__last - __first > int(_S_threshold))和条件如 if (__depth_limit == 0)但这最后我在我的算法中不需要。所以我发现非规范类型的循环会阻止自动矢量化。

template<typename _RandomAccessIterator, typename _Compare> 
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
    __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
    _ValueType>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
    {
        std::__introsort_loop(__first, __last,
        std::__lg(__last - __first) * 2, __comp);
        std::__final_insertion_sort(__first, __last, __comp);
    }
}

所讨论的循环如下所示:

// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare> 
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
{
    while (__last - __first > int(_S_threshold))
    {
        if (__depth_limit == 0)
        {
            _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
            return;
        }
        --__depth_limit;
        _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
        std::__introsort_loop(__cut, __last, __depth_limit, __comp);
        __last = __cut;
    }
}

Answer 1

标准 C++ 库在标准算法中使用迭代器，例如 sort()。这允许算法实现忽略底层容器的确切细节。此外，此方法不允许使用 operator[]() 进行索引。

考虑到这一点，我有两个建议供您考虑:

1) 修改您的专用排序以使用迭代器，而不是 operator[]() 来访问容器中的元素。如果可以保持所需的 O(n) 速度，那么这可能是最理想的灵活性方法。

2) 使用模板化的容器类实现排序。类似的东西

template <class Container, class Compare>
void sort(Container cont, Compare comp);

应该可以解决问题。