2

我有一个强大的用例来定义我自己的排序算法，它比 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;
    }
}
4

2 回答 2

2

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

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

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

2) 使用模板化的容器类实现您的排序。就像是

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

应该做的伎俩。

于 2012-07-23T14:49:52.740 回答
0

模板的美妙之处在于，它们在模板类型被填写之前不会被完全编译，因此编译器可以根据最终代码应用优化。指针满足随机访问迭代器的T*所有必需属性，并且可以在任何需要它们的模板代码中轻松使用。

vector<float> v;
// load v
sort(&v[0], &v[v.size()]); // same as sort(v.begin(), v.end()) but possibly optimized better
于 2012-07-23T21:39:48.480 回答