2

我有一个二维矩形网格，我需要将不同的函数应用于该网格中的节点子集。子集由矩形边界给出，例如行和列分隔符。由于我不想一遍又一遍地用 2 for 循环编写迭代代码，我正在考虑两种方法来解决这个问题：

首先创建一个自定义迭代器提供程序，该提供程序使用矩形限制进行初始化，然后在迭代时保留它们。虽然这是可行的，但要使这个迭代器与标准 stl 算法兼容似乎还需要做很多工作。

第二种方法是将函数指针传递给遍历 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

从设计的角度来看，我会说迭代器方法更好，因为它在循环体上的复杂性较低（并且可能比迭代中的复杂性更高）。

但我希望函子方法有更好的性能。特别是如果您将使用 STL 样式（带有预期 operator() 的模板参数）。

于 2012-12-11T13:29:28.260 回答
1

为什么不直接将二维子集数组复制到临时数组，然后将指向数组开头的指针传递给不同的函数呢？

如果同一个子集多次传递给不同的函数，它应该会减少缓存未命中，从而减少子集迭代所花费的时间。

于 2012-12-11T13:07:05.710 回答