自定义迭代器适用于std::sort，但不适用于tbb::parallel_sort

Question

我正在尝试使用tbb::parallel_sort同时对两个数组进行排序。英特尔的文档显示https://software.intel.com/en-us/node/506167CCD_ 2。事实似乎并非如此。我的自定义迭代器与std::sort配合使用非常好，但与tbb::parallel_sort配合使用会产生编译错误。请参阅下面的代码：

int main()//needs boost and tbb to compile
{
    int values_size = 6;
    int nums1[] = {5, 8, 7, 89, 56, 4};
    int nums2[] = {2, 1, 1, 4, 9, 2};
    //WORKS!
    std::sort(do_dual_sort.make_iter(nums1, nums2), 
    do_dual_sort.make_iter(nums1+values_size, nums2+values_size),
    do_dual_sort.make_comp_desc(nums1, nums2));
    //DOESN'T COMPILE
    tbb::parallel_sort(do_dual_sort.make_iter(nums1, nums2), 
    do_dual_sort.make_iter(nums1+values_size, nums2+values_size),
    do_dual_sort.make_comp_desc(nums1, nums2));
    for(unsigned int i = 0; i < values_size; i++) cout << "nums1[" << i << "] " << nums1[i] << " | nums2[" << i << "] "  << nums2[i] << "n";
    return 0;
}
class dual_sort
{
public:
    template <class T, class T2>
    struct helper_type {
        public:
            typedef boost::tuple<typename iterator_traits<T>::value_type, typename iterator_traits<T2>::value_type> value_type;
            typedef boost::tuple<typename iterator_traits<T>::value_type&, typename iterator_traits<T2>::value_type&> ref_type;
    };
    template <typename T1, typename T2>
    class dual_iterator : public boost::iterator_facade<dual_iterator<T1, T2>,
                                                        typename helper_type<T1, T2>::value_type,
                                                        boost::random_access_traversal_tag,
                                                        typename helper_type<T1, T2>::ref_type> {
    public:
        explicit dual_iterator(T1 iter1, T2 iter2) : mIter1(iter1), mIter2(iter2) {}
        typedef typename iterator_traits<T1>::difference_type difference_type;
    private:
        void increment() { ++mIter1; ++mIter2; }
        void decrement() { --mIter1; --mIter2; }
        bool equal(dual_iterator const& other) const { return mIter1 == other.mIter1; }
        typename helper_type<T1, T2>::ref_type dereference() const { return (typename helper_type<T1, T2>::ref_type(*mIter1, *mIter2)); }
        difference_type distance_to(dual_iterator const& other) const { return other.mIter1 - mIter1; }
        void advance(difference_type n) { mIter1 += n; mIter2 += n; }
        T1 mIter1;
        T2 mIter2;
        friend class boost::iterator_core_access;
    };
    template <typename T1, typename T2>
    dual_iterator<T1, T2> make_iter(T1 t1, T2 t2) { return dual_iterator<T1, T2>(t1, t2); }
    template <class T1, class T2> struct iter_comp_desc {
        typedef typename helper_type<T1, T2>::value_type T;
        bool operator()(const T& t1, const T& t2) const { return get<0>(t1) > get<0>(t2); }
        bool operator()(const char*& t1, const char*& t2) const { return strcmp(get<0>(t1), get<0>(t2)) == 1; }
    };
    template <class T1, class T2> iter_comp_desc<T1, T2> make_comp_desc(T1 t1, T2 t2) { return iter_comp_desc<T1, T2>(); }
} do_dual_sort;

我得到的编译错误是：

error C2512: 'dual_sort::dual_iterator<T1,T2>' : no appropriate default constructor available
with
[
    T1=int *,
    T2=int *
]
tbb44_20150728ossincludetbb/parallel_sort.h(201) : see reference to function template instantiation 'void tbb::internal::parallel_quick_sort<RandomAccessIterator,Compare>(RandomAccessIterator,RandomAccessIterator,const Compare &)' being compiled
with
[
    RandomAccessIterator=dual_sort::dual_iterator<int *,int *>,
    Compare=dual_sort::iter_comp_desc<int *,int *>
]
main.cpp(1125) : see reference to function template instantiation 'void tbb::parallel_sort<dual_sort::dual_iterator<T1,T2>,dual_sort::iter_comp_desc<T1,T2>>(RandomAccessIterator,RandomAccessIterator,const Compare &)' being compiled
with
[
    T1=int *,
    T2=int *,
    RandomAccessIterator=dual_sort::dual_iterator<int *,int *>,
    Compare=dual_sort::iter_comp_desc<int *,int *>
]

编辑：我使用的编译器是Visual Studio 2012。您可以尝试用std函数替换一些boost函数，使其在g++上工作。

Answer 1

对于RandomAccessIterator，reference必须是对value_type的引用。它不能是引用的元组。

因此，您的双迭代器不是有效的RandomAccess迭代器。

许多算法仍然可以工作，但这并不能使您的代码有效。

相同的要求并不意味着任何与std::sort的给定实现一起工作的东西也将与tbb::parallel_sort一起工作：std::sort的给定实现不必强制执行标准中的所有要求。

不管文档是什么，如果实现不能与您的代码一起工作，那么它也不能与代码一起工作。

最简单的方法可能是在原始数组中创建一个由伪索引对(或迭代器(组成的数组，然后对其进行排序。您只需要正确地重写<。

Answer 2

tbb/parallel_sort.h中的class quick_sort_range包含RandomAccessIterator begin;成员，该成员在其一个构造函数中进行复制初始化，默认初始化，然后在另一个构造函数分配。因此，它需要默认的迭代器&可施工和可转让的副本。

因此，TBB文档声称与std::sort有相同的要求是不正确的，因为后者只需要随机访问迭代器，而TBB实现要求版本<=4.4.

默认的可施工和可分配要求可以固定，但可能会保留可移动或可复制的要求(使文件中的索赔正确(。你可以在TBB论坛上报道这个问题。

您可以安全地添加默认&将构造函数和赋值运算符复制到代码中，以便使用tbb::parallel_sort编译它。

以下是您的代码片段的在线编译器：http://coliru.stacked-crooked.com/a/47dafd091d36a9c4

Answer 3

我无法编译基本用例(即使用std::sort(。因此，该代码适用于在一种特定的编译器情况下成功编译。

The requirements on the iterator and sequence are the same as for std::sort.0也满足ForwardIterator的要求。如果我们查看ForwardIterator的需求，我们会发现它应该是DefaultConstructible。(参见最新C++标准工作草案中的第(1.2(节，§24.2.5正向迭代器(

Answer 4

第一个错误为"没有合适的默认构造函数可用.."，但是迭代程序必须是默认可构造的。

默认构造是否用于一种算法或另一种算法并不重要，但该要求仍然适用。因此，std::sort的编译成功和tbb::parallel_sort的编译失败并不意味着The requirements on the iterator and sequence are the same as for std::sort不是真的；这只是意味着您正在使用的std::sort的实现不依赖于该先决条件。

根据文档，如果您实现迭代器以符合两种算法所依赖的标准子集，那么它应该可以工作。