Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding lower_bound() of a column in a 2D array

Tags:

c++

stl

I have a 2D array, in which I want to find the lower bound in a particular column.

How can I do that using std::lower_bound?

like image 542
xennygrimmato Avatar asked Jun 07 '14 12:06

xennygrimmato


People also ask

Can we use Lower_bound in array?

But in Array of Pairs lower_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than or equals x and second value is greater than equals to y.

How do you find the lower bound of an array?

The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number.

How do you find the upper bound of an array?

In order to get the array upperbound of a multidimensional array, we use the length() method. For a 2D array, the length() method returns the number of rows. We can access the number of columns using the array_name[0]. length method.

What is Upperbound in array?

Each element of an array stores one value and is referenced by its index (coordinate position). The index of the first element of an array is called its lower bound, while the index of the last element is called its upper bound.


3 Answers

Introduction

This is not as hard as one might think it is, let us first walk through the abstract of algorithm functions that apply to ranges.

Every such function, like std::lower_bound, accepts a begin and an end iterator to know which elements they are going to search. The problem in our case as it seems non-trivial to create an iterator that iterates over columns, instead of rows.

The good news; it isn't.


Forming a pointer to array

We can create pointers to pretty much anything in C++, and that certainly include arrays.

What's good with pointers is that if we increment one we will get to the next element, no matter what type the pointer is referring to. In our case we'd like to iterate over all the nested arrays in our 2D array.

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]

The implementation

#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
}

Note: Using std::begin and std::end is an clearer alterantive to &a[0] and &a[5].

Note: We could replace not_less_than_column(1) with a lambda, but since generic lambdas are not supported in C++11 the current approach is cleaner.

like image 199
Filip Roséen - refp Avatar answered Sep 20 '22 10:09

Filip Roséen - refp


The simple answer to just stick the column identification into the predicate and use the iterator of the outer array. This assumes a two dimensional array which has enough columns in each row, though. Of course, making sure that array isn't ragged is easy for built-in arrays:

#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";
    }
}
like image 30
Dietmar Kühl Avatar answered Sep 21 '22 10:09

Dietmar Kühl


You could try and write an iterator for columns:

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;
    }
};

Also you could write a factory function to make the creation of such iterators easy:

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 };
}

And use it as follows:

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

    auto iterator = iterate_column( foo , 0 );
}

Or even:

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 );
}

And then:

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

Which (If I have implemented this correctly) should return 2

like image 40
Manu343726 Avatar answered Sep 18 '22 10:09

Manu343726