算法-使用boost或STL对C ++中的压缩(锁定)容器进行排序

我想做什么:我想对锁定在一起的2个,3个或N个向量进行排序,而无需将它们复制到元组中。 也就是说,将冗长性放在一边,类似:

vector<int>    v1 = {  1,   2,   3,   4,   5};
vector<double> v2 = { 11,  22,  33,  44,  55};
vector<long>   v3 = {111, 222, 333, 444, 555};

typedef tuple<int&,double&,long&> tup_t;
sort(zip(v1,v2,v3),[](tup_t t1, tup_t t2){ return t1.get<0>() > t2.get<0>(); });

for(auto& t : zip(v1,v2,v3))
  cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << endl;

这应该输出:

5 55 555
4 44 444
...
1 11 111

我现在的操作方式:我实现了自己的quicksort,其中我传递的第一个数组用于比较,并且排列应用于所有其他数组。 我只是想不通如何针对我的问题重用std :: sort(例如提取排列)。

我尝试了什么:boost :: zip_iterator和boost :: zip_range(带有boost :: combine range),但是std :: sort和boost :: range :: algorithm :: sort都抱怨迭代器/范围是只读的 而不是随机访问...

问题:如何在锁定步骤(压缩)中对N个向量进行排序? 这个问题看起来很普通而且很常见,所以我想必须通过一个可能非常复杂的库来找到一个简单的解决方案,但是我找不到它...

备注:是的,stackoverflow中也有类似的问题,这个问题经常以不同的形式被问到。 但是,它们始终使用以下答案之一关闭:

  • 将向量复制到对/元组中并对该元组进行排序...
  • 将向量复制到每个向量只有一个成员的结构中,并对结构的向量进行排序...
  • 为您的特定问题实现自己的排序功能...
  • 使用索引的辅助数组...
  • 使用boost :: zip_iterator而不使用示例或示例会产生不良结果。

提示:

  • 我在boost邮件列表中找到了该主题,该主题指向Anthony Williams的这篇论文。 尽管这似乎仅适用于配对,但他们也讨论了TupleIteratorType,但是我找不到它。
  • user673679发现此帖子包含针对两个容器的不错的解决方案。 它还可以解决问题(重点是我的问题):

根本的问题是数组引用的“成对”的行为不像它们应该表现的那样,我只是决定滥用迭代器的符号并编写有效的东西。 这涉及有效地编写一个不一致的迭代器,其中值类型的引用与引用类型不同。

答:请参阅下面的“ interjay评论”(这也会部分回答未来的问题):

#include "tupleit.hh"
#include <vector>
#include <iostream>
#include <boost/range.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/algorithm/for_each.hpp>

template <typename... T>
auto zip(T&... containers)
    -> boost::iterator_range<decltype(iterators::makeTupleIterator(std::begin(containers)...))> {
  return boost::make_iterator_range(iterators::makeTupleIterator(std::begin(containers)...),
                                      iterators::makeTupleIterator(std::end(containers)...));
}

int main() {

  typedef boost::tuple<int&,double&,long&> tup_t;

  std::vector<int>    a = {   1,   2,   3,   4 };
  std::vector<double> b = {  11,  22,  33,  44 };
  std::vector<long>   c = { 111, 222, 333, 444 };

  auto print = [](tup_t t){ std::cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << std::endl; };

  boost::for_each( zip(a, b, c), print);

  boost::sort( zip(a, b, c), [](tup_t i, tup_t j){ return i.get<0>() > j.get<0>(); });

  for ( auto tup : zip(a, b, c) ) print(tup);

  return 0;
}

未来的问题:先前的答案适用于序列容器。 我们还能在可排序的容器(例如序列和列表)上使用它吗? 这将需要random_access和双向TupleIterators,以及在双向迭代器上工作的排序算法。

更新:这适用于类似序列的容器的组合。 但是,混合列表将需要std :: sort支持BidirectionalIterators(不需要)。

gnzlbg asked 2020-07-21T06:48:04Z
5个解决方案
14 votes

这是一个基于range-v3库的工作示例,该库已提出标准化要求

#include <range/v3/all.hpp>
#include <iostream>

using namespace ranges;

int main() 
{
    std::vector<int> a1{15, 7, 3,  5};
    std::vector<int> a2{ 1, 2, 6, 21};
    sort(view::zip(a1, a2), std::less<>{}, &std::pair<int, int>::first); 
    std::cout << view::all(a1) << '\n';
    std::cout << view::all(a2) << '\n';
}

实时示例(需要具有良好C ++ 14支持的最新编译器,而不是VS 2015)。

TemplateRex answered 2020-07-21T06:48:19Z
7 votes

对于两个容器的情况,这是基于上述文章在gcc 4.4.6上编译的版本。 在更高版本的gcc中,您可以将boost :: tuple换成std :: tuple

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

# include <boost/iterator/iterator_facade.hpp>
# include <boost/tuple/tuple.hpp> 

using namespace std;

template <class T, class T2>
struct helper_type {
  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 {
  typedef typename helper_type<T1, T2>::value_type T;
  bool operator()(const T& t1, const T& t2) { return get<0>(t1) < get<0>(t2); }
};

template <class T1, class T2> iter_comp<T1, T2> make_comp(T1 t1, T2 t2) { return iter_comp<T1, T2>(); }

template<class T> void print(T& items) {
  copy(items.begin(), items.end(), ostream_iterator<typename T::value_type>(cout, " ")); cout << endl;
}

int main() {
  vector<double> nums1 = {3, 2, 1, 0};
  vector<char> nums2 = {'D','C', 'B', 'A'};
  sort(make_iter(nums1.begin(), nums2.begin()), 
       make_iter(nums1.end(), nums2.end()), 
       make_comp(nums1.begin(), nums2.begin()));
  print(nums1);
  print(nums2);
}
Carl Cook answered 2020-07-21T06:48:39Z
5 votes

创建一个包含索引0..N-1的辅助数组。 使用自定义比较器对该数组进行排序,该比较器实际上返回比较主数组之一元素的结果。 然后,使用排序后的辅助阵列以正确的顺序打印出您的主阵列。

twalberg answered 2020-07-21T06:49:01Z
4 votes

很高兴认识一位互联网考古学家!

如何在锁定步骤(压缩)中对N个向量进行排序? 问题看起来 非常普通和通用,所以我想必须有一个简单的解决方案 通过一个可能非常复杂的库,但是我找不到它。

有时以前,我以类似的假设进行了一次寻宝活动。
没找到宝藏:(

我跟你走的路一样:

  • 经过通常的怀疑boost.iterator / boost.range / boost.fusion / boost.oven,经过大量的实验和研究后,他们意识到他们无法解决这个特定问题。
  • 经历关于SO的许多问题,才意识到已经用错误的答案(例如,建议boost :: zip_iterator在您指出的这种情况下不起作用)关闭了每个单独的窗口,或者采用了一些避免 事情的核心。
  • 遍历许多博客文章,邮件列表,才意识到除了...之外,没有人真正解决问题。
  • 经过大量研究,最终找到了安东尼奥·威廉(Antonius Wilhelm)的旧编解码器,后者声称已设计出通用解决方案“ TupleIterator”并将其锁定在一些存档文件“ tupleit.zip”中。 关于这一档案的历史资料如此稀缺,以至于我仍然不确定这个档案是否是神话,传说,还是仍然埋藏在互联网迷失的某个地方:)

好的,更严重的是,Anthony Williams的论文表明这个问题实际上真的很棘手,因此发现没有像boost这样的现有库就可以解决这个问题也就不足为奇了。

Thomas Petit answered 2020-07-21T06:50:01Z
2 votes

我很高兴地说,经过类似的寻宝活动,我找到了解决方案。 如果可以使用range-v3,则是个好主意,但如果确实需要迭代器,则HPX项目已创建了一个迭代器,并且可以完美地与sort一起使用。

由于疏忽,希望可以修复它,它仍然需要您链接到HPX库,但这对我来说是可以的,因为重点是使用HPX提供的C ++ 17并行算法。

#include <hpx/util/zip_iterator.hpp>

using zip_it = 
    hpx::util::zip_iterator<std::vector<std::size_t>::iterator,
                            std::vector<std::size_t>::iterator,
                            std::vector<double>::iterator>;

int main() {
    std::vector<std::size_t> rows{3, 2, 1};
    std::vector<std::size_t> cols{1, 2, 3};
    std::vector<double> values{4.0, 5.0, 6.0};

    auto start = hpx::util::make_zip_iterator(rows.begin(), cols.begin(), values.begin());
    auto stop  = hpx::util::make_zip_iterator(rows.end(), cols.end(), values.end());

    std::sort(start, stop);

    for ( int i = 0; i < 3; ++i ) {
        std::cerr << rows[i] << ", " << cols[i] << ", " << values[i] << "\n";
    }
}
Jeff Trull answered 2020-07-21T06:50:27Z
translate from https://stackoverflow.com:/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl