c++ - 2 つの配列に対する STL 準拠の反復子

Question

同じサイズの 2 つの配列 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 ++が得意ではないということです。初心者が理解できるレベルで誰かが私にヒントを与えることができれば、私は喜んでいます. 私はいくつかの解決策を見つけました：

対応する 2 つの配列を並べ替えますが、提案された両方のソリューションのパフォーマンスが十分ではないようです。

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-返せるかどうかわからないため、operator-> と operator* を実装する方法がわからないという点で立ち往生した完全なソリューション1 つの値 (配列 a の値) のみ。つまり、この値が比較または値の割り当てにのみ使用される場合。また、このスレッドの解決策は、比較演算子のポインター値を比較しますが、これが正しいかどうかはわかりません (ポインターの背後にある値ではないでしょうか?)。

ここに私がこれまでに持っているものがあります.もしあなたが恐ろしい初心者の間違いを見たら、plsは私がどこで間違ったのか教えてください:)

#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」、「参照」、および「ポインター」タイプに混乱しています 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);

}

私はこれを試していませんが、おそらくいくつかの欠点がありますが、この方向に進む必要があります. イテレータは、配列への 2 つのポインタ (より一般的な方法では、コンテナへのイテレータ) で構成され、参照型にはoperator =andが必要operator <であり、両方の配列の要素を割り当てて、1 つの配列の要素のみを比較することができます。

[アップデート]

良いニュース: 私は実際の例を実行しました: ideone

score 0 · Accepted Answer

私はあなたの質問に少し混乱していますが、この質問にリンクしているので、それと同じ問題を解決しようとしていると思います。つまり、配列をソートしaたいのですが、配列のインデックスをb同じ方法で再配置したいのです用でしたa。

これはXY Problemのように思えます。可能であれば、並列配列を持たないようにコードを再設計してください。代わりに、の各要素をのa対応する要素とともにbクラスまたはstd::pairに配置し、それらを配列やベクトルなどのコレクションに配置して、それを並べ替えます (必要に応じて、比較演算子をオーバーロードする可能性があります)。

c++ - 2 つの配列に対する STL 準拠の反復子

2 に答える 2

Related

Reference