boost zip_iterator 和 std::sort

Question

我有两个长度相同的数组 values 和 keys 。 我想使用 keys 数组作为键对 values 数组进行键排序。 我被告知 boost 的 zip 迭代器正是锁定两个数组在一起并同时对它们执行操作的正确工具。

这是我尝试使用 boost::zip_iterator 来解决无法用 gcc 编译的排序问题。有人可以帮我修复这个代码吗？

问题出在行

std::sort ( boost::make_zip_iterator(keys, values ), boost::make_zip_iterator(keys+N , value+N ));

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>



int main(int argc, char *argv[])
{
  int N=10;
  int    keys[N];
  double values[N];
  int M=100;

  //Create the vectors.
  for (int i = 0; i < N; ++i)
   {
     keys[i]   = rand()%M;
     values[i] = 1.0*rand()/RAND_MAX;
   }


  //Now we use the boost zip iterator to zip the two vectors and sort them "simulatneously"
  //I want to sort-by-key the keys and values arrays
   std::sort ( boost::make_zip_iterator( keys, values  ), 
               boost::make_zip_iterator( keys+N  , values+N    )
             );
    //The values array and the corresponding keys in ascending order. 
   for (int i = 0; i < N; ++i)
    {
      std::cout << keys[i]   <<  "\t"  << values[i]    << std::endl;  
     }
  return 0;
}

注意：编译时出现错误消息

g++ -g -Wall boost_test.cpp 
boost_test.cpp: In function ‘int main(int, char**)’:
boost_test.cpp:37:56: error: no matching function for call to ‘make_zip_iterator(int [(((unsigned int)(((int)N) + -0x00000000000000001)) + 1)], double [(((unsigned int)(((int)N) + -0x00000000000000001)) + 1)])’
boost_test.cpp:38:64: error: no matching function for call to ‘make_zip_iterator(int*, double*)’

Answer 1

您无法对一对 zip_iterator 进行排序。

首先， make_zip_iterator 将迭代器元组作为输入，因此您可以调用：

boost::make_zip_iterator(boost::make_tuple( ... ))

但这也不会编译，因为 keys 和 keys+N 不具有相同的类型。我们需要强制 keys 成为一个指针：

std::sort(boost::make_zip_iterator(boost::make_tuple(+keys, +values)),
          boost::make_zip_iterator(boost::make_tuple(keys+N, values+N)));

这会编译，但排序结果仍然是错误的，因为 zip_iterator 只模拟 可读迭代器，但 std::sort 也需要输入为 可写为此处描述< /a>，因此无法使用 zip_iterator 进行排序。

Answer 2

关于这个问题的一个很好的讨论可以在这里找到：https://web.archive.org/web/20120422174751/http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html

这是此问题的可能重复项:<一href="https://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl">使用 boost 或 c++ 对 C++ 中的压缩（锁定）容器进行排序STL

上面链接中的方法使用 std::sort，并且没有额外的空间。它不使用 boost::zip_iterator，只使用 boost 元组和 boost 迭代器外观。如果您有最新的编译器，std::tuples 也应该可以工作。

如果您很高兴拥有一个额外的向量（size_t 元素），那么以下方法将在 ~ o(n log n) 时间平均情况下工作。这相当简单，但是如果您搜索的话，将会有更好的方法。

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

using namespace std;

template <typename T1, typename T2>
void sortByPerm(vector<T1>& list1, vector<T2>& list2) {
  const auto len = list1.size();
  if (!len || len != list2.size()) throw;

  // create permutation vector
  vector<size_t> perms;
  for (size_t i = 0; i < len; i++) perms.push_back(i);
  sort(perms.begin(), perms.end(), [&](T1 a, T1 b){ return list1[a] < list1[b]; });

  // order input vectors by permutation
  for (size_t i = 0; i < len - 1; i++) {
    swap(list1[i], list1[perms[i]]);
    swap(list2[i], list2[perms[i]]);

    // adjust permutation vector if required
    if (i < perms[i]) {
      auto d = distance(perms.begin(), find(perms.begin() + i, perms.end(), i));
      swap(perms[i], perms[d]);
    }
  }
}

int main() {
  vector<int> ints = {32, 12, 40, 8, 9, 15};
  vector<double> doubles = {55.1, 33.3, 66.1, 11.1, 22.1, 44.1};

  sortByPerm(ints, doubles);   

  copy(ints.begin(), ints.end(), ostream_iterator<int>(cout, " ")); cout << endl;
  copy(doubles.begin(), doubles.end(), ostream_iterator<double>(cout, " ")); cout << endl;
}

Answer 3

在另一个答案中看到您的另一条评论后。

我想我会向您介绍 std::map。这是一个键值容器，保留键顺序。 （它基本上是一棵二叉树，通常是红黑树，但这并不重要）。

size_t elements=10;
std::map<int, double> map_;
for (size_t i = 0; i < 10; ++i)
{
    map_[rand()%M]=1.0*rand()/RAND_MAX;
}
//for every element in map, if you have C++11 this can be much cleaner
for (std::map<int,double>::const_iterator it=map_.begin(); 
         it!=map_.end(); ++it) 
{
    std::cout << it->first   <<  "\t"  << it->second  << std::endl;  
}

未经测试，但任何错误都应该是简单的语法错误

Answer 4

boost::make_zip_iterator 采用 boost::tuple。

#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

int main(int argc, char *argv[])
{
  std::vector<int> keys(10);      //lets not waste time with arrays
  std::vector<double> values(10);
  const int M=100;

  //Create the vectors.
  for (size_t i = 0; i < values.size(); ++i)
   {
     keys[i]   = rand()%M;
     values[i] = 1.0*rand()/RAND_MAX;
   }


  //Now we use the boost zip iterator to zip the two vectors and sort them "simulatneously"
  //I want to sort-by-key the keys and values arrays
   std::sort ( boost::make_zip_iterator(
                    boost::make_tuple(keys.begin(), values.begin())), 
               boost::make_zip_iterator(
                     boost::make_tuple(keys.end(), values.end()))
             );
    //The values array and the corresponding keys in ascending order. 
   for (size_t i = 0; i < values.size(); ++i)
    {
      std::cout << keys[i]   <<  "\t"  << values[i]    << std::endl;  
     }
  return 0;
}