使用boost或STL在C++中对压缩的容器进行排序

Question

我想要做什么：我想要将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

我现在的做法： 我实现了自己的快速排序算法，其中第一个数组用于比较，排列应用于所有其他数组。我只是无法想出如何重复使用std::sort来解决我的问题（例如提取排列）。

我尝试过的： boost::zip_iterator 和 boost::zip_range（使用boost::combine范围），但是std::sort和boost::range::algorithm::sort都抱怨迭代器/范围是只读而不是随机存取的...

问题： 如何同时对N个矢量进行锁定排序（zipped）？这个问题看起来非常通用和常见，所以我猜应该有一个简单的解决方案，虽然可能需要一个非常复杂的库，但我就是找不到它...

备注： 是的，在stackoverflow上有类似的问题，这个问题以不同的形式经常被提出。但是它们总是被以下答案之一关闭：

• 将您的向量复制到一个对/元组中，然后对该元组进行排序...
• 将您的向量复制到一个结构体中，每个向量都有一个成员，然后对结构体向量进行排序...
• 为您特定的问题实现自己的排序函数...
• 使用辅助索引数组...
• 使用boost::zip_iterator而没有示例或使用会产生错误结果的示例。

提示：

• 我在boost邮件列表中找到了这个主题，它指向了Anthony Williams的这篇文章。虽然这似乎只适用于一对，但他们也讨论了TupleIteratorType，但我还没有找到它。
• user673679发现了这篇帖子，其中包含两个容器情况的好解决方案，它还解决了问题（强调是我的）：

基本问题在于“数组引用的对”不像它们应该的那样工作。我决定滥用迭代器的符号并编写一些有效的代码。这涉及编写一个不符合规范的迭代器，其中值类型的引用不同于引用类型。

#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;
}

未来问题: 上一个答案适用于序列容器。我们是否可以在可排序的容器（例如序列和列表）上实现这个功能？这将需要使用随机访问和双向元组迭代器以及能够在双向迭代器上工作的排序算法。

更新: 这适用于类似序列的容器的组合。但是混合使用列表将需要std::sort支持BidirectionalIterators（目前不支持）。

- gnzlbg

---

考虑 std::sort 如何通过 std::iter_swap 重新排列元素：你的 zip_iterator 应该支持这一点。 - pmr

这是一个非常有趣的任务，你对自己下定决心了 :) - Matthieu M.

这里是Anthony Williams的代码：tupleit.hh，testtupleit.cpp。可以从tupleit.zip这里下载（需要加入）。 - interjay

@JonathanWakely 我能否也使用redi的zip进行排序？示例展示了只读访问，而这已经可以通过boost::zip_iterator实现。 - gnzlbg

也许将boost标签更改为range-v3？（请参见我的答案） - TemplateRex

Answer 1

这是一个基于已提议标准化的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

---

我已经移除了临时变量、lambda表达式，并使用了投影。现在这可能是最好的答案，所以我将更新答案为此。 - gnzlbg

@gnzlbg 哦，是的，投影仍需要一些时间来适应。 - TemplateRex

看起来你是对的，错误列表非常长。但是，也许 @EricNiebler 知道最近版本的 range-v3 中改变了什么，导致压缩视图排序出现问题？ - TemplateRex

@mrks 请查看上面的评论。 - TemplateRex

Answer 2

对于两个容器的情况，这里有一个基于上述论文的适用于 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

---

这段代码不具备可移植性，GCC无法编译。 - Anton

Answer 3

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

- twalberg

---

不必使用O(n)额外的存储空间。 - gnzlbg

Answer 4

很高兴遇到一位互联网考古学家！

如何同时锁定（zipped）排序N个向量？这个问题看起来很通用和常见，所以我猜一定有一个简单的解决方案通过一个可能非常复杂的库，但我就是找不到。

以前，我也曾使用类似的假设进行宝藏寻找……却从未找到宝藏 :(

我跟着你走过的轨迹：

- 浏览常见的boost.iterator/boost.range/boost.fusion/boost.oven等工具，经过大量实验和研究后，发现它们无法解决这个特定的问题。 - 浏览许多关于SO的问题，只发现每一个都被关闭了，要么是答案错误（例如推荐boost::zip_iterator，但正如你指出的那样，在这种情况下它不起作用），要么是采用某些规避方法避免核心问题。 - 浏览许多博客文章、邮件列表，只发现没有人真正解决了这个问题，除了…… - 经过大量研究，最终挖掘出Antonius Wilhelm的旧编码文档，他声称已经制定了一个通用解决方案“TupleIterator”，并将其锁定在某个存档“tupleit.zip”中。这个问题的历史来源如此稀缺，以至于我仍然不确定这个存档是一个神话、一个传说，还是它仍然埋藏在互联网的某个失落层中 :) - 好吧，更严肃地说，Anthony Williams的论文表明这个问题实际上非常困难，所以发现没有现有的库像boost一样解决它并不奇怪。

- Arzar

Answer 5

我很高兴地告诉你，我在类似的寻宝过程中找到了一个解决方案。如果可以使用range-v3，那么这是一个很好的选择，但如果你真的需要一个迭代器，HPX项目创建了一个迭代器，并且它与sort完美地配合使用。

由于一些疏忽，希望能得到修复，目前仍需要链接HPX库，但对我来说没问题，因为整个重点是使用C++17并行算法，而HPX提供了实现。

#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

---

你应该为你的答案添加多个注释。首先，使用 range-v3 迭代器的解决方案非常简单。其次，你使用了需要迭代器符合标准迭代器概念的 std::sort 函数。然而，hpx 的 zip 迭代器并不符合这些概念。也就是说，一个“好”的 STL 实现会拒绝这段代码。使用 hpx::sort 可能会解决这个问题，但是使用 std::sort 代码不具备可移植性，并且只有偶然成功的机会。 - gnzlbg

感谢您的反馈。您能更详细地解释一下range-v3迭代器吗？它只是应用于范围的std::begin/std::end吗？ 至于迭代器建模，我认为HPX的符合标准，但我不确定。希望@K-ballo能进一步发表评论。 - Jeff Trull

range-v3迭代器解决方案是将begin/end应用于范围适配器：auto zip_v = view::zip(rows, cols); auto b = ranges::begin(zip_v); auto e = ranges::end(zip_v);。您可以像使用所有range-v3算法一样使用这些迭代器（它们都有迭代器版本）。HPX zip迭代器不能符合标准，因为C++标准不支持zip迭代器（因此使用它们调用std::sort是未定义的行为）。 - gnzlbg