Я пытаюсь использовать 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++
,
Для RandomAccessIterator, reference
должна быть ссылка на value_type
, Это не может быть кортеж ссылок.
Таким образом, ваш двойной итератор не является действительным RandomAccessIterator.
Многие алгоритмы все еще будут работать, но это не делает ваш код корректным.
Одни и те же требования не означают, что все, что работает с данной реализацией std::sort
также будет работать с tbb::parallel_sort
: данная реализация std::sort
не должен обеспечивать соблюдение всех требований, установленных в стандарте.
Независимо от документации, если реализация не будет работать с вашим кодом, она не будет работать с вашим кодом.
Самым простым подходом может быть создание массива псевдопар индексов (или итераторов) в исходных массивах, а затем сортировка. Вам просто нужно переопределить <
должным образом.
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
Я не смог скомпилировать базовый вариант использования (т.е. с std::sort
). Таким образом, код адаптирован для успешной компиляции в одном конкретном случае компилятора.
КСТАТИ, RandomAccessIterator
удовлетворяет ForwardIterator
требования тоже. И если мы посмотрим на ForwardIterator
требования мы выясняем, что это должно быть DefaultConstructible
, (см. §24.2.5 Прямые итераторы, раздел (1.2) в одном из последних Рабочий проект стандарта C ++)
Первая ошибка гласит: «Нет подходящего конструктора по умолчанию, доступного ..», но
Итераторы должны быть конструируемыми по умолчанию.
Независимо от того, используется ли конструкция по умолчанию в том или ином алгоритме, не имеет значения, требование остается в силе. Так что компиляция успеха с std::sort
и неудача с tbb::parallel_sort
не означает The requirements on the iterator and sequence are the same as for std::sort
не правда; это просто означает, что реализация std::sort
что вы используете, не зависит от этого предварительного условия.
Если вы реализуете свой итератор в соответствии с подмножеством стандарта, на которое опираются оба алгоритма, он должен работать согласно документации.