2

2Dの長方形グリッドがあり、このグリッドのノードのサブセットにさまざまな関数を適用する必要があります。サブセットは、行と列の区切り文字などの長方形の境界で指定されます。2つのforループを繰り返し使用して反復をコーディングしたくないので、この問題を解決するために2つのアプローチを検討しています。

最初に、長方形の制限を使用して初期化され、反復される間それらを保持するカスタムイテレータープロバイダーを作成します。これは実行可能ですが、このイテレータを標準のstl aglorithmsなどに準拠させるには、かなりの作業が必要になるようです。

2番目のアプローチは、関数ポインターを関数に渡して、forループの両方をトラバースし、内側のループで実行することです。これも実行可能ですが、メンバー関数を渡す必要があるため、非常に醜い構文が作成される可能性があります。

通常はどちらの方法が望ましいですか?そして、私が車輪の再発明をしないようにするために、そのようなユースケースの明確な例はありますか?

注:コードは頻繁に実行されるため、この操作はパフォーマンスにとって非常に重要です。

4

3 に答える 3

2

ここで価値があるのは、私が最終的に実装したアルゴリズムです。コードは完全ではありませんが、おそらく他の誰かにとって有用です:

//forward declarations
template <typename T> class Grid;
template <typename T> class rectIterator;

//friend forward declarations
template<class T>
bool operator!=(rectIterator<T> const& left, rectIterator<T> const& right);


template<class T>
class rectIterator: public std::iterator<std::forward_iterator_tag, GridTile<T> >{

public:
  typedef GridTile<T> const& const_reference;
  typedef GridTile<T>& reference;
  typedef GridTile<T> const* const_pointer;
  typedef GridTile<T>* pointer;

private:
  Grid<T>* mpGrid;
  int mRow;
  int mCol;
  int mMinRow;
  int mMinCol;
  int mMaxRow;
  int mMaxCol;


public:
  rectIterator(Grid<T>& grid,Rectangle const& rect):
    mpGrid(&grid){
    mpGrid->getRowCol(mpGrid->getTileId(rect.bottomLeft()),mMinRow,mMinCol);
    mpGrid->getRowCol(mpGrid->getTileId(rect.topRight()),mMaxRow,mMaxCol);
    mRow = mMinRow;
    mCol = mMinCol;
  }

  rectIterator():
    mpGrid(0){
    mMinRow= -1;
    mMinCol=-1;
    mMaxRow =-1;
    mMaxCol =-1;
    mCol = 0;
    mRow = 0;
  }

  rectIterator<T>& operator++(){
    if(mCol<=mMaxCol){
      ++mCol;
    }else if(mRow<=mMaxRow){
      ++mRow;
      mCol = mMinCol;
    }else{
      mCol = mpGrid->getCols();
      mRow = mpGrid->getRows();
      mpGrid=0;
    }
    return *this;
  }

  reference operator*() const throw(std::out_of_range, std::runtime_error){
    return mpGrid->at(mRow,mCol);
  }

  pointer operator->() const throw(std::out_of_range, std::runtime_error){
    return &(mpGrid->at(mRow,mCol));
  }

  int row()const{
    return mRow;
  }

  int col()const{
    return mCol;
  }

  friend bool operator!=<>(rectIterator<T> const& left, rectIterator<T> const& right);

};

template<class T>
bool operator!=  (rectIterator<T> const& left, rectIterator<T> const& right){
  return (left.mpGrid != right.mpGrid);
  //DIRTY this is no full compare but fast and sufficient at the moment
}
于 2012-12-14T12:53:11.993 に答える
1

2Dサブセット配列を一時配列にコピーしてから、配列の先頭へのポインターを別の関数に渡してみませんか?

同じサブセットが異なる関数に複数回渡される場合、キャッシュミスが改善されるため、サブセットの反復に費やされる時間が改善されます。

于 2012-12-11T13:07:05.710 に答える
1

設計の観点からは、ループ本体の複雑さが軽減されるため、イテレーターアプローチの方が優れていると思います(反復よりも複雑になる可能性があります)。

しかし、ファンクターアプローチを使用するとパフォーマンスが向上することを期待しています。特に、STLスタイルで作成する場合(期待されるoperator()を使用したテンプレートパラメーター)。

于 2012-12-11T13:29:28.260 に答える