Пользовательский итератор работает с std :: sort, но не с tbb :: parallel_sort?

Я пытаюсь использовать tbb::parallel_sort сортировать 2 массива одновременно. Документация Intel здесь говорит https://software.intel.com/en-us/node/506167 The requirements on the iterator and sequence are the same as for std::sort., Похоже, это не так. Мой пользовательский итератор прекрасно работает с 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_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 *>
]

редактировать: Компилятор, который я использовал Visual Studio 2012, Вы можете попробовать заменить некоторые функции повышения на std те, чтобы заставить его работать на g++,

8

Решение

Для RandomAccessIterator, reference должна быть ссылка на value_type, Это не может быть кортеж ссылок.

Таким образом, ваш двойной итератор не является действительным RandomAccessIterator.

Многие алгоритмы все еще будут работать, но это не делает ваш код корректным.

Одни и те же требования не означают, что все, что работает с данной реализацией std::sort также будет работать с tbb::parallel_sort: данная реализация std::sort не должен обеспечивать соблюдение всех требований, установленных в стандарте.

Независимо от документации, если реализация не будет работать с вашим кодом, она не будет работать с вашим кодом.

Самым простым подходом может быть создание массива псевдопар индексов (или итераторов) в исходных массивах, а затем сортировка. Вам просто нужно переопределить < должным образом.

6

Другие решения

class quick_sort_range в tbb/parallel_sort.h содержит RandomAccessIterator begin; элемент, который инициализируется копией в одном его конструкторе и инициализируется по умолчанию, а затем назначается в другом конструкторе. Таким образом, требуются итераторы, которые по умолчанию&копируемый и назначаемый.

Таким образом, документация TBB не является правильной и требует тех же требований, что и std::sort так как позже требуется только итераторы с произвольным доступом, которые не требуются быть назначаемым, пока реализация TBB требует его для версий <= 4.4.

Конструируемые и назначаемые по умолчанию требования могут быть исправлены, но перемещение или конструирование с возможностью копирования, скорее всего, останутся (делая утверждение в документации правильным). Вы можете сообщить об этой проблеме на Форум TBB.

Вы можете смело добавлять по умолчанию&скопировать конструкторы и оператор присваивания в ваш код, чтобы скомпилировать его с tbb::parallel_sort насколько я вижу.

Вот онлайн-компилятор с вашим фрагментом: http://coliru.stacked-crooked.com/a/47dafd091d36a9c4

6

Я не смог скомпилировать базовый вариант использования (т.е. с std::sort). Таким образом, код адаптирован для успешной компиляции в одном конкретном случае компилятора.

КСТАТИ, RandomAccessIterator удовлетворяет ForwardIterator требования тоже. И если мы посмотрим на ForwardIteratorтребования мы выясняем, что это должно быть DefaultConstructible, (см. §24.2.5 Прямые итераторы, раздел (1.2) в одном из последних Рабочий проект стандарта C ++)

5

Первая ошибка гласит: «Нет подходящего конструктора по умолчанию, доступного ..», но
Итераторы должны быть конструируемыми по умолчанию.

Независимо от того, используется ли конструкция по умолчанию в том или ином алгоритме, не имеет значения, требование остается в силе. Так что компиляция успеха с std::sort и неудача с tbb::parallel_sort не означает The requirements on the iterator and sequence are the same as for std::sort не правда; это просто означает, что реализация std::sort что вы используете, не зависит от этого предварительного условия.

Если вы реализуете свой итератор в соответствии с подмножеством стандарта, на которое опираются оба алгоритма, он должен работать согласно документации.

3
По вопросам рекламы [email protected]