Custom iterator works with std::sort but not with tbb::parallel_sort?

Question

I am trying to use tbb::parallel_sort to sort 2 arrays at the same time. Intel's documentation here says https://software.intel.com/en-us/node/506167 The requirements on the iterator and sequence are the same as for std::sort.. This doesn't seem to be the case. My custom iterator works perfectly fine with std::sort but produces a compilation error with tbb::parallel_sort. Please see the code bellow:

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;

The compilation error I am getting is:

error C2512: 'dual_sort::dual_iterator<T1,T2>' : no appropriate default constructor available
with
[
    T1=int *,
    T2=int *
]
tbb44_20150728oss\include\tbb/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 *>
]

Edit: The compiler I used is Visual Studio 2012. You can try to replace some boost functions with std ones to get it work on g++.

Answer 1

For a RandomAccessIterator, reference must be a reference to value_type. It cannot be a tuple of references.

As such, your dual iterator is not a valid RandomAccessIterator.

Many algorithms will still work, but that doesn't make your code valid.

The requirements being the same does not mean that anything that works with a given implementation of std::sort will also work with tbb::parallel_sort: a given implementation of std::sort does not have to enforce all of the requirements made in the standard.

Regardless of the documentation, if the implementation won't work with your code, it won't work with your code.

The easiest approach might be to create an array of pseudo-pairs of indexes (or iterators) into the original arrays, then sort it. You just need to override < properly.

Answer 2

The class quick_sort_range in tbb/parallel_sort.h contains RandomAccessIterator begin; member which is copy-initialized in one its constructor and default-initialized and then assigned in the other constructor. Thus it requires iterators which are default&copy-constructable and assignable.

So, the TBB documentation is not correct claiming the same requirements as std::sort since the later requires just random-access iterators which are not required to be assignable while TBB implementation requires it for versions <= 4.4.

The default-constructable and assignable requirements can be fixed but move or copy-constructable will likely remain (making the claim in the documentation correct). You can report this issue on TBB Forum.

You can safely add default&copy constructors and assignment operator to your code to compile it with tbb::parallel_sort as far as I can see.

Here is the online compiler with your snippet: http://coliru.stacked-crooked.com/a/47dafd091d36a9c4