Finding a lower_bound () column in a 2D array

Question

I have a 2D array in which I want to find the bottom border in a specific column.

How to do this using std::lower_bound?

Answer 1

Introduction

This is not as difficult as you might think, let's first look at the abstract functions of the algorithm applicable to ranges.

Each function, such as std::lower_bound, takes a start and end iterator to know what elements they will look for. The problem in our case, it seems non-trivial, is to create an iterator that iterates over columns, not rows.

Good news; this is not true.

---

Array pointer generation

++ , , .

, , , , . 2D-.

T a[5][3] = { ... };

T(*p)[3] = &a[0]; // is a pointer to an array of three `T`,
                  // currently pointing to a[0]

++p;              // now referring to a[1]

---

#include <iostream>
#include <algorithm>
#include <iterator>

struct not_less_than_column {
  not_less_than_column (unsigned long idx)
    : m_idx (idx)
  { }

  template<class T, unsigned long N>
  bool operator() (T(&arr)[N], T const& needle) const {
    return arr[m_idx] < needle;
  }

  unsigned long m_idx;
};

int main () {
  int a[5][3] = {
    { 0, 24,  1 },
    { 0, 35,  1 },
    { 0, 42,  1 },
    { 0, 66,  1 },
    { 0, 100, 1 }
  };

  auto ptr = std::lower_bound (std::begin (a), std::end (a), 36, not_less_than_column (1));

  for (auto const& e : *ptr)
    std::cout << e << " "; // 0 42 1
}

<sup>: std::begin std::end &a[0] &a[5].

. not_less_than_column(1) , lambdas ++ 11, .</sup>

Answer 2

, . , . , , , :

#include <algorithm>
#include <iostream>

int main()
{
    int array[][3] = {
        {  1,  2,  3 },
        {  4,  5,  6 },
        {  7,  8,  9 },
        { 10, 11, 12 }
    };

    for (int column(0); column < 3; ++ column) {
        int (*lower)[3] = std::lower_bound(std::begin(array), std::end(array),
                                           6, [=](int (&ptr)[3], int value){
                                               return ptr[column] < value; });
        std::cout << "column=" << column << " row=" << (lower - array) << "\n";
    }
}

Answer 3

:

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
class column_iterator
{
    std::size_t _row; //Current position of the iterator
    const std::size_t _column; //The column which the iterator traverses

    T& _array[ROWS][COLUMNS]; //Reference to the array

public:
    column_iterator( T (&array[ROWS][COLUMNS]) , std::size_t column , std::size_t pos = 0) :
        _array{ array } , 
        _row{ pos } ,
        _column{ column }
    {}

    const T& operator*() const
    {
        return _array[_row][_column];
    }

    T& operator*()
    {
        return _array[_row][_column];
    }

    column_iterator& operator++()
    {
        _row++;

        return *this;
    }

    friend bool operator==( const column_iterator& lhs , const column_iterator& rhs )
    {
        return lhs._row == rhs._row && lhs._column == rhs._column;
    }
};

factory, :

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> iterate_column( T (&array[ROWS][COLUMNS]) , std::size_t column , std::size_t row = 0 )
{
    return column_iterator<T,ROWS,COLUMNS>{ array , row , column };
}

:

int main()
{
    int foo[2][2] = { {1,2} , 
                      {3,4} };

    auto iterator = iterate_column( foo , 0 );
}

:

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> column_begin( T (&array[ROWS][COLUMNS]) , std::size_t column )
{
    return iterate_column( array , column , 0 );
}

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> column_end( T (&array[ROWS][COLUMNS]) , std::size_t column )
{
    return iterate_column( array , column , ROWS );
}

:

std::lower_bound( column_begin( foo , 1 ) , column_end( foo , 1 ) , 2 );

( ), 2

Answer 4

:

vector<unsigned> column_lower_bound(const vector<vector<unsigned> >& matrix) {
    size_t rows = matrix.size(), columns = matrix[0].size();
    vector<unsigned> result(columns, ~0);

    for(size_t y = 0; y < rows; y++) {
        const vector<int>& curRow = matrix[y];
        assert(curRow.size() == columns);

        for(size_t x = 0; x < columns; x++) {
            if(result[x] > curRow[x]) result[x] = curRow[x];
        }
    }
    return result;
}

- . , .

---

, C:

void column_lower_bound(size_t width, size_t height, unsigned (*matrix)[width], unsigned* result) {
    for(size_t x = 0; x < width; x++) result[x] = ~0;

    for(size_t y = 0; y < rows; y++) {
        unsigned* curRow = matrix[y];
        for(size_t x = 0; x < columns; x++) {
            if(result[x] > curRow[x]) result[x] = curRow[x];
        }
    }
}

++, 2D- ++. C .