logo标签列表

自定义迭代器在std::sort中可以工作，但在tbb::parallel_sort中却不能？

c++iteratortbb
8

我正在尝试使用tbb::parallel_sort同时对两个数组进行排序。英特尔的文档在此处说明：https://software.intel.com/en-us/node/506167迭代器和序列的要求与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。您可以尝试将一些Boost函数替换为std函数，使其在g++上运行。

你想要什么样的关注？你已经吸引了两个TBB开发者的注意，但是即使使用纯boost/C++，你的代码也无法正常工作，请先修复其基础问题，如果除了我已经提出的建议之外还有其他问题，请再提出与TBB相关的问题。 - Anton
你确定你的任务是对一个压缩容器进行排序吗？就像那个答案所假设的那样。 - Anton
@Anton 不幸的是，并不总是这样。 - We're All Mad Here
@Walter 当然代码是可以运行的，请在Visual Studio 2012中尝试一下。我为什么要说谎呢？关于我想做的事情，很明显：我想根据第一个数组的值对两个数组进行排序。 - We're All Mad Here
@We'reAllMadHere 我没有（也不想要）Windows电脑。从你的另一个评论中，我猜想你想避免额外的O(N)存储 - 是吗？或者你是指你没有额外的RAM？顺便说一下，你的代码不能工作，因为你没有包含所有相关的头文件;-) - Walter
显示剩余6条评论
4个回答
6
在`tbb/parallel_sort.h`中，`class quick_sort_range`包含一个成员`RandomAccessIterator begin;`，它在一个构造函数中进行复制初始化，在另一个构造函数中进行默认初始化并分配。因此，需要具有默认和可复制构造以及可赋值的迭代器。
因此，TBB文档声称与`std::sort`具有相同的要求是不正确的，因为后者仅需要随机访问迭代器，而这些迭代器不一定需要可赋值，在TBB实现中需要版本<= 4.4的迭代器可赋值。
可以通过添加默认构造函数和可赋值运算符来修复对可默认构造和可赋值的要求，但移动或复制构造可能仍然存在（使文档中的声明正确）。您可以在TBB Forum上报告此问题。
据我所见，您可以安全地添加默认和复制构造函数以及赋值运算符来编译带有`tbb::parallel_sort`的代码。
以下是带有您代码片段的在线编译器：http://coliru.stacked-crooked.com/a/47dafd091d36a9c4。
4
很抱歉，你是错的。声称有相同要求的文件很可能是正确的（我不明白这显然为何不是这样）。请参见下面Yakk出色的回答。 - Walter
@Walter，std::sort需要迭代器可分配吗？我没有找到这样的要求。因此我的回答是正确的。 - Anton
@Anton，说“与std::sort相同的要求”并不是很有帮助，因为几乎没有人知道这些要求到底是什么。即使某个特定的iterator在某个实现中与std::sort一起使用，也不能说明它满足这些要求（因为std::sort的实现可能不使用所有正式要求）。因此，文档应该更加明确——但是众所周知，tbb文档很草率。 - Walter
@Walter 我同意并向TBB开发人员表达了同样的观点。但我的观点是我的答案仍然是正确的，所以请删除您的评论和负评。 - Anton
@Anton -1 你提供的链接页面显示随机访问迭代器概念不需要赋值，但实际上它们需要(b = a)。事实上，所有迭代器都必须是默认的、可复制的和可复制赋值的。(默认构造的迭代器被称为奇异，顺便说一下。)所以Yakk是正确的，这是关于std::sort特定实现的问题，而不是标准要求。TBB文档也是正确的，因为它涉及到标准，而不是特定的实现。至少当前文档还明确提到了随机访问迭代器概念。 - Arne Vogel
6
对于RandomAccessIterator，reference必须是对value_type的引用，而不能是引用元组。因此，你的双向迭代器不是有效的RandomAccessIterator。
许多算法仍然可以工作，但这并不意味着你的代码是有效的。
要求相同并不意味着任何在给定实现的std::sort中工作的东西也会在tbb::parallel_sort中工作：给定的std::sort实现不必强制执行标准中的所有要求。
无论文档如何，如果实现无法与你的代码一起工作，它就不会与你的代码一起工作。
最简单的方法可能是创建一个伪对数组（或迭代器），指向原始数组，然后对其进行排序。你只需要正确覆盖<操作符。
是的，但为了做到这一点，我需要使用额外的内存，而我没有。 - We're All Mad Here
@We'reAllMadHere 说的不对。你有足够多的额外内存。但是你如何控制你使用的任何代码不会分配内存呢？ - Walter
@Yakk 感谢您的帮助，尽管我实际上没有解决问题，但您帮了我很多，这就是为什么我会给您赏金的原因。 - We're All Mad Here
5
我无法编译基本用例（例如使用std::sort）。因此，该代码已被调整为在一个特定的编译器案例中成功编译。
顺便说一下，RandomAccessIterator 也满足ForwardIterator 的要求。如果我们查看ForwardIterator 的要求，我们会发现它应该是DefaultConstructible。（请参见最新的C++标准工作草案中的§24.2.5正向迭代器，第（1.2）节）。
重点在于文档声称与std::sort相同的要求，但简单的测试揭示了差异。值得明确记录要求（并/或放宽tbb::parallel_for的要求）。 - Anton
3
第一个错误信息提示“没有适当的默认构造函数可用。。。”，但是迭代器必须具有默认构造函数。
无论在哪个算法中使用默认构造，要求仍然存在。因此，使用std::sort编译成功而使用tbb::parallel_sort失败并不意味着迭代器和序列的要求与std::sort相同不正确；只是意味着您正在使用的std::sort实现不依赖于该前提条件。
如果实现您的迭代器符合两个算法所依赖的标准的子集，那么它应该可以正常工作，符合文档要求。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接