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++.

Coussoule

what kind of attention do you want? You grabbed attention of 2 TBB developers already. But your code does not work even with pure boost/C++, please fix its basics, then ask tbb-related question if anything remains beyond what I already suggested. – Heroic

@Heroic : Thank you for your help so far. To be honest, I am not an experienced developer. I would be really grateful if you could help me make my code work with TBB parallel_sort. Here is where I found my code: https://mcmap.net/q/153113/-sorting-zipped-locked-containers-in-c-using-boost-or-the-stl – Monda

are you sure that your task is to sort a zipped container? like that answer assumes – Heroic

@Anton: My task is to sort 2 arrays int *arr using tbb::parallel_sort. If you know a better way, please let me know. – Monda

so, both of them are of the same type, right? In that case you don't need these heavy tuple/template magic – Heroic

@Heroic Not always unfortunately – Monda

@Mooing Duck I believe you a very good at problems like this one so could you please take a look? – Monda

So what is the problem again if you add default&copy constructors and assigment operators to this iterator code? I dont have the env where both vs2012 and tbb coexist to try it myself – Heroic

-1 sorry, but had to downvote this post. The question is not clearly stated (what do you mean by sorting two arrays simulatenously?) and the code provided does not work. Btw, a tuple with just two elements is also called pair. – Trisect

@Trisect Of course code works, please try it in visual studio 2012. Why would I lie about that? Regarding what I am trying to do, it's clear: I want to sort two arrays based on the values of the first array. – Monda

@We'reAllMadHere I have no (and don't want a) windows box. From your other comment, I reckon you want to avoid additional O(N) storage -- correct? Or what to you mean that you don't have extra RAM? BTW, your code does not work as you fail to #include all the relevant headers ;-) – Trisect

Answer 1

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

Heroic

Unfortunately, you're wrong. The documentation claiming the same requirements is presumably correct (I don't see how this is obviously not so). See Yakk's excellent answer below. – Trisect

@Trisect does std::sort require iterators to be assignable? I have not found such a requirement. Thus my answer is correct – Heroic

@Anton, saying the same requirements as for std::sort is not very helpful, because hardly anybody knows exactly what these requirements are. Even if a certain iterator works with std::sort for a certain implementation, this does not imply that it meats those requirements (for the implementation of std::sort may not use all formal requirements). So the documentation should be more explicit -- but the tbb documentation is well known to be sloppy. – Trisect

@Trisect I agree and said the same to TBB developers. But my point was that my answer is still correct, so please remove your comment and downvote – Heroic

@Heroic -1 The very page you linked to, to show that the random access iterator concept does not require assignment, states that they do (b = a). In fact, all iterators must be default and copy c'tible as well as copy assignable. (A default constructed iterator is called singular, BTW.) So Yakk is right that this is about a particular implementation of std::sort, not the standard requirements. The TBB documentation is also correct because it refers to the standard, not a particular implementation. At least the current doc also explicitly refers to the random access iterator concept. – Figuration

Answer 2

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.

Flounce

Yes, but in order to do this I need to use extra ram which I don't have – Monda

@We'reAllMadHere Rubbish. You have plenty of extra RAM. How can you control whether any code you're using doesn't allocate? – Trisect

@Yakk Thanks for your help despite the fact that I did not actually solved the problem you helped me a lot that's why I will give you the bounty – Monda

Answer 3

I was not able to compile basic use case (i.e. with std::sort). Thus, the code is adapted to compile successfully in one specific compiler case.

BTW, RandomAccessIterator satisfies ForwardIterator requirements too. And if we look at the ForwardIterator's requirements we find out that it should be DefaultConstructible. (see §24.2.5 Forward iterators, section (1.2) in one of the latest C++ standard's working draft)

Chaffer

The point is that the documentation claims the same requirements as for std::sort but a simple test reveals the difference. It's worth clearly document the requirements (and/or relax them for tbb::parallel_for) – Heroic

Answer 4

The first error reads "no appropriate default constructor available..", but Iterators must be default constructible.

Whether the default construction is used in one algorithm or another doesn't matter, the requirement still holds. So compilation success with std::sort and failure with tbb::parallel_sort doesn't mean the The requirements on the iterator and sequence are the same as for std::sort isn't true; it just means that the implementation of std::sort that you are using doesn't rely on that pre-requisite.

If you implement your iterator to conform to the subset of standard that is relied upon by both algorithms, then it should work, per the documentation.

Fatwitted