c++ - 两个数组的 STL 兼容迭代器

Question

我想按以下方式对两个大小相同的数组 a 和 b 进行排序：数组 b 的排序方式与数组 a 的排序方式相同。示例输入：

a = {3, 1, 5}
b = {2, 6, 4}

示例输出

a = {1, 3, 5}
b = {6, 2, 4}

这样 b 的值与它们的重新排序无关，而是遵循数组 a 的重新排序。

我想使用 stl::sort 来做到这一点，我需要尽可能高效地做到这一点。因此，我不想将所有元素复制到结构中或使用索引对数组进行排序，然后我可以使用该索引对数组 a 和 b 进行排序。我认为开销最小的应该是 RandomAccessIterator （因为排序需要随机访问）。现在我的问题是，我真的不太擅长 C++。如果有人可以在菜鸟可以理解的水平上给我提示，我会很高兴。我找到了一些解决方案：

对两个对应的数组进行排序，但两个提议的解决方案似乎都不够高效，

http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html它使用了我认为违反 stl 的 boost 东西（老实说，我不明白那里使用的所有模板东西，我有一个 double 和一个 int 数组以及两者的大小 n，所以我认为我不需要模板），最后这个

http://www.c-plusplus.de/forum/313698-full解决方案我被困在我不知道如何实现 operator-> 和 operator* 因为我不知道我是否可以返回只有一个值（数组 a 中的值），即如果该值仅用于比较或也用于赋值。该线程中的解决方案还比较了比较运算符的指针值，我不确定这是否正确（不应该是指针后面的值吗？）。

这是我到目前为止所拥有的，如果你看到可怕的菜鸟错误，请告诉我我哪里出错了:)

#include "DoubleArrayRAccIterator.h"


DoubleArrayRAccIterator::~DoubleArrayRAccIterator() {
    // TODO Auto-generated destructor stub
}
struct doubleValue{
    double* a_val;
    int* b_val;
};

double::DoubleArrayRAccIterator::DoubleArrayRAccIterator(double& a_arr,int& b_arr, int size) {
    a_begin = &a_arr;
    b_begin = &b_arr;
    a = &a_arr;
    b = & b_arr;
    n = size;
}

DoubleArrayRAccIterator::DoubleArrayRAccIterator() {
    a = 0;
    b = 0;
    n = 0;
}

DoubleArrayRAccIterator::DoubleArrayRAccIterator(const DoubleArrayRAccIterator& it) {
    a = it.a;
    b = it.b;
    n = it.n;
}

DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator=(const DoubleArrayRAccIterator& it) {
    a = it.a;
    b = it.b;
    n = it.n;
    return *this;
}

DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator++() {
    ++a;
    ++b;
    return *this;
}


DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator--() {
    --a;
    --b;
    return *this;
}

DoubleArrayRAccIterator DoubleArrayRAccIterator::operator++(int) {
    DoubleArrayRAccIterator it(*this);
    ++a;
    ++b;
    return it;
}


DoubleArrayRAccIterator DoubleArrayRAccIterator::operator--(int) {
    --a;
    --b;
    return *this;
}

DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator+=(diff_type x) {
    a += x;
    b += x;
    return *this;
}


DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator-=(diff_type x) {
    a += x;
    b += x;
    return *this;
}

DoubleArrayRAccIterator DoubleArrayRAccIterator::operator+(diff_type x) const {
    a += x;
    b += x;
    return *this;
}


typename DoubleArrayRAccIterator DoubleArrayRAccIterator::operator-(diff_type x) const {
    a -= x;
    b -= x;
    return *this;
}


DoubleArrayRAccIterator DoubleArrayRAccIterator::operator+(const DoubleArrayRAccIterator& it) const {
    a += it.a;
    b += it.b;
    return *this;
}


DoubleArrayRAccIterator DoubleArrayRAccIterator::operator-(const DoubleArrayRAccIterator& it) const {
    a -= it.a;
    b -= it.b;
    return *this;
}


DoubleArrayRAccIterator::reference DoubleArrayRAccIterator::operator*() const {
    // this MUST be wrong, only return value of array a?
    doubleValue result;
    result.a_val=a;
    result.b_val=b;
    return *result;
}

DoubleArrayRAccIterator::pointer DoubleArrayRAccIterator::operator->() const {
    // this MUST be wrong, only return value of array a?
    doubleValue result;
    result.a_val=a;
    result.b_val=b;
    return &result;
}


DoubleArrayRAccIterator::reference DoubleArrayRAccIterator::operator[](diff_type x) const {
    // this MUST be wrong, only return value of array a?
    doubleValue result;
    result.a_val=a_begin+x;
    result.b_val=b_begin+x;
    return *result;
}


bool DoubleArrayRAccIterator::operator==(const DoubleArrayRAccIterator& it) const {
    return a == it.a;
    //compare indices or values here?
}


bool DoubleArrayRAccIterator::operator!=(const DoubleArrayRAccIterator& it) const {
    return a != it.a;
    //compare indices or values here?
}


bool DoubleArrayRAccIterator::operator<(const DoubleArrayRAccIterator& it) const {
    //compare indices or values here?
}


bool DoubleArrayRAccIterator::operator>(const DoubleArrayRAccIterator& it) const {
    //compare indices or values here?
}


bool DoubleArrayRAccIterator::operator<=(const DoubleArrayRAccIterator& it) const {
    //compare indices or values here?
}


bool DoubleArrayRAccIterator::operator>=(const DoubleArrayRAccIterator& it) const {
    //compare indices or values here?
}


DoubleArrayRAccIterator begin() {
    return DoubleArrayRAccIterator(a_begin, b_begin, n);
}


DoubleArrayRAccIterator end() {
    return DoubleArrayRAccIterator(a_begin + n, b_begin + n, n);
}

如果有人还没有停止阅读并且仍然有耐心，我对我刚刚从这里复制的“diff_type”、“reference”和“pointer”类型感到困惑http://www.c-plusplus.de/forum /313698-full，它们应该是什么？

score 4 · Accepted Answer

如果我对您的理解正确，您会遇到这种情况：

[a1][a2][a3]....[an]
[b1][b2][b3]....[bn]

您想按数组 a 排序，这两个数组都以相同的方式，所以结果是：

[ax1][ax2][ax3]....[axn]
[bx1][bx2][bx3]....[bxn]

两个数组的索引在哪里xi相同。

考虑这个例子：

class SIter {
public:


   SIter(int* aIter, double* bIter) : aIter(aIter), bIter(bIter) {}

  // we move to next position is just moving both:
  SIter& operator ++() {
     ++aIter; ++bIter;
     return *this;
  }
  SIter operator ++(int) {
     SIter rv = *this;
     ++aIter; ++bIter;
     return rv;
  }
  SIter& operator --() {
     --aIter; --bIter;
     return *this;
  }
  SIter operator --(int) {
     SIter rv = *this;
     --aIter; --bIter;
     return rv;
  }
  SIter operator + (std::ptrdiff_t cc) const
  {
      SIter rv = *this;
      rv.aIter += cc;
      rv.bIter += cc;
      return rv;
  }
  SIter operator - (std::ptrdiff_t cc) const
  {
      SIter rv = *this;
      rv.aIter -= cc;
      rv.bIter -= cc;
      return rv;
  }
  std::ptrdiff_t operator - (SIter other) const
  {
      return aIter - other.aIter;
  }
   struct value_type {
      int a; double b;
      bool operator < (const value_type& other) const {
          return a < other.a; // this is the place where way of sorting is defined!!!!
      }
   };
  struct reference {
     int* a;
     double* b;
     reference& operator = (const value_type& o) 
     {
       *a = o.a;
       *b = o.b;
       return *this;
     }
     operator value_type() const {
         value_type rv = { *a, *b };
         return rv;
     }
     reference& operator = (const reference& other)
     {
        *a = *other.a;
        *b = *other.b;
        return *this;
     }
     bool operator < (const reference& other) const {
        return *a < *other.a; 
     }
     bool operator < (const value_type& other) const {
        return *a < other.a; 
     }
  };

  reference operator * () {
     reference rv = { aIter, bIter };
     return rv;
  }
  bool operator == (const SIter& other) const
  {
      return aIter == other.aIter; // don't need to compare bIter - shall be in sync
  }
  bool operator != (const SIter& other) const
  {
      return aIter != other.aIter; // don't need to compare bIter - shall be in sync
  }
  bool operator < (const SIter& other) const
  {
      return aIter < other.aIter; // don't need to compare bIter - shall be in sync
  }
  // I bet you don't need pointer operator -> ()
   typedef std::random_access_iterator_tag iterator_category;
   typedef std::ptrdiff_t difference_type;
   typedef reference pointer;


private:
  int* aIter; 
  double* bIter;
};

然后像这样使用：

int main() {
   int a[100] = {};
   double b[100] = {};

   SIter beginIter(a, b);
   SIter endIter(a + 100, b + 100);

   std::sort(beginIter, endIter);

}

我没有尝试这个，可能它有一些缺点，但你应该朝这个方向走。您的迭代器应包含两个指向您的数组的指针（以更一般的方式 - 指向您的容器的迭代器），并且您的引用类型应具有operator =并且operator <能够分配两个数组的元素并仅比较一个数组的元素。

[更新]

好消息：我做了一个工作示例：ideone

score 0 · Accepted Answer

我对你的问题有点困惑，但是由于你链接到这个问题，我假设你正在尝试解决相同的问题，即你想要对数组进行排序a并且你希望数组的索引b以与它们相同的方式重新排列是为了a。

在我看来，这可能是一个XY 问题。如果可能的话，重新设计你的代码，这样你就没有并行数组了。取而代之的是，将每个元素a与其对应的元素b放在一个类中或std::pair，将它们放在一个集合中，例如数组或向量，然后对其进行排序（如果需要，可能会重载比较运算符）。

c++ - 两个数组的 STL 兼容迭代器

2 回答 2

Related

Reference