C++ - Sort multidimensional vector by its contained object property

Question

Hi guys,

I've got a bidimensional array of objects (a 2D vector containing GridCell instances) as in here:

typedef vector<GridCell> CellArray;
typedef vector<CellArray> TwoDCellArray;
TwoDCellArray CellArr2D;

I am currently drawing all the cells like this:

for (int i = 0; i < rows; i++){
    for (int j = 0; j < cols; j++){
        CellArr2D[i][j].draw()
    }
}

However, I've got a depth problem and I should draw the instances depending on its size (size property, CellArr2D[i][j].size).

What should I do to sort this array without changing it's i,j values? Copying all the objects to a secondary array and sort that one? And more imporntant, hence this post... how can I sort an Array (Vector) by it's contained object property?

Thanks in advanced.

Answer 1

Create a vector of pairs (i,j) and sort it by size property.

typedef std::pair<int, int> int_pair_t;
typedef std::vector< int_pair_t > size_index_t;

namespace {
struct sort_helper {
    sort_helper( const TwoDCellArray& arr ) : arr_(arr) {}      
    bool operator()( const int_pair_t& ind1, const int_pair_t& ind2 ) { 
      return arr_[ind1.first][ind1.second].size > arr_[ind2.first][ind2.second].size; 
    }
private:
    const TwoDCellArray& arr_;
};

struct draw_helper {
    draw_helper( TwoDCellArray& arr ) : arr_(arr) {}        
    void operator()( const int_pair_t& ind ) { 
        arr_[ind.first][ind.second].draw();
    }
private:
    TwoDCellArray& arr_;
};
}

void some_func()
{
    // initialize helper array of indices
    size_index_t index;
    index.reserve( rows*cols );
    for ( int i = 0; i < rows*cols; ++i )
        index.push_back( make_pair( i/cols%rows, i%cols ) );

    // sort according to the `size` field
    std::sort( index.begin(), index.end(), sort_helper( CellArr2D ) );

    // draw
    std::for_each( index.begin(), index.end(), draw_helper( CellArr2D ) );
}

Answer 2

Use std::sort and supply a custom comparison function object to sort by a user-defined property or other relation.

As for how it should be sorted, if you want to sort it but not change it, then you will have to copy the array. The best way to do this is store your GridCells on the heap and store smart pointers to them in the vectors. This way, sorting and copying them will involve less overhead.

Answer 3

You can put references in a secondary array and sort that one:

struct CellRef
{
  CellRef(GridCell& cell) : m_c(cell) {}
  bool operator<(const CellRef& r) const { return m_c.size < r.m_c.size; }
  GridCell& data() { return m_c; }
private:
  GridCell& m_c;
};

vector<CellRef> refs;
for (int i = 0; i < rows; i++){
    for (int j = 0; j < cols; j++){
        refs.push_back(CellArr2D[i][j]);
    }
}
std::sort(refs.begin(), refs.end());
for(vector<CellRef>::iterator it=refs.begin(), end=refs.end(); it!=end; ++it)
  it->data().draw();