特殊排序算法与通用签名

Question

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

到目前为止，问题是，我想提供一个通用的接口，它适用于任何类型的容器，例如T*或std::vector<T>等，只要有几个关键概念适用。

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

为了了解一些想法，我转到了头文件<std_algo.h>并找到了下面的函数接口，它与我所要寻找的内容完全匹配，除了一个细节之外，我不认为编译器忽略容器类型会自动向向量遍历底层_RandomAccessIterator，这是我的问题.有什么办法可以让我拥有一切吗？自动矢量化+通用接口忽略底层集合类型？

我认为，由于“非规范”循环模式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);

应该能起作用。

Answer 2

模板的奇妙之处在于，直到模板类型被填充之后，它们才会被完全编译，所以编译器可以根据最终的代码应用优化。T*指针满足随机访问迭代器所需的所有属性，并且可以很容易地在任何需要它们的模板代码中使用。

vector<float> v;
// load v
sort(&v[0], &v[v.size()]); // same as sort(v.begin(), v.end()) but possibly optimized better