Binary Search in Multi Dimensional Vector

[infantheartlyjes]

HI Folks, Is there any option to apply binary_search algorithm for multidimesional (2D) Vector ?

[Script Coder]

How are the elements sorted?

[infantheartlyjes]

the elements are sorted by ascending order. Sorting type is string.

[Script Coder]

If they are stored in ascending order, then why not put them in a 1D vector?
Would you mind giving a sample vector, please?

[JLBorges]

Is there any option to apply binary_search algorithm for multidimesional (2D) Vector ?

If there are no empty vectors in the 2D vector:

template < typename T, typename V >
bool binary_search( const std::vector< std::vector<T> >& outer, const V& v )
{
    static const auto lt = [] ( const std::vector<T>& seq, const T& v )
    { assert( !seq.empty() ) ; return seq.back() < v ; };

    const auto iter = std::lower_bound( outer.begin(), outer.end(), v, lt ) ;
    return iter != outer.end() && std::binary_search( iter->begin(), iter->end(), v ) ;
}

http://coliru.stacked-crooked.com/a/6e42d335c80b7676

[infantheartlyjes]

I have tried the below code for binary search program to find at a specific column.

class BINARY_ON
{
	public:
  explicit BINARY_ON(int column,string fCol) :m_column(column),fColType(fCol) {}
 
  bool operator()(const string& lhs,const vector<string>& rhs)
  {

	if(fColType=="number")
		return atoi(lhs.c_str()) < atoi(rhs[m_column].c_str());					
	else if(fColType=="date")
		return PPCheckTwoDate(lhs, rhs[m_column])<0;
	else
		return lhs < rhs[m_column];	
   }
   private:
   int m_column;
   string fColType;
 
};

int main ()
{
vector<vector<string>> table_data;

// Vector Data Insert

	BINARY_ON compare_column(4,"date");
	
	if (std::binary_search (table_data.begin(), table_data.end(), "01051996", compare_column))
    std::cout << "found!\n"; else std::cout << "not found.\n";
}

I got the below errors.

/usr/include/c++/4.6/bits/stl_algo.h:2416:4: error: no match for call to ‘(PPBINARY_ON) (std::vector<std::basic_string<char> >&, const char [9])’
note: bool PPBINARY_ON::operator()(const string&, const std::vector<std::basic_string<char> >&)
note: no known conversion for argument 1 from ‘std::vector<std::basic_string<char> >’ to ‘const string& {aka const std::basic_string<char>&}’

So I changed the PPBINARY_ON::operator() function definition as
bool operator()(const vector<string>& rhs, const string& lhs)

But now i got the error like this,

/usr/include/c++/4.6/bits/stl_algo.h: In function ‘bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<std::vector<std::basic_string<char> >*, std::vector<std::vector<std::basic_string<char> > > >, _Tp = char [9], _Compare = BINARY_ON]’:
binarysearch.cpp:17:86: instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:2714:56: error: no match for call to ‘(BINARY_ON) (const char [9], std::vector<std::basic_string<char> >&)’
note: bool BINARY_ON::operator()(const std::vector<std::basic_string<char> >&, const string&)
note: no known conversion for argument 1 from ‘const char [9]’ to ‘const std::vector<std::basic_string<char> >&’

What is the error in it ? Did i use the binary search STL function correctly ?

[JLBorges]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct compare_cols
{
    constexpr compare_cols( std::size_t c ) : col(c) {}

    using row_type = std::vector<std::string> ;

    // binary predicate for sort
    bool operator() ( const row_type& a, const row_type& b ) const
    {
        if( a.size() < col ) return b.size() >= col ;
        else if( b.size() < col ) return false ;
        else return a[col] < b[col] ;
    }

    // binary predicate for string < vector<string>
    bool operator() ( const std::string& str, const row_type& row ) const
    {
        if( row.size() < col ) return false ;
        else return str < row[col] ;
    }

    // binary predicate for vector<string> < string
    bool operator() ( const row_type& row, const std::string& str ) const
    {
        if( row.size() < col ) return true ;
        else return row[col] < str ;
    }

    const std::size_t col ;
};

int main()
{
    std::vector< std::vector<std::string> > v2d
    {
       { "zero", "ten", "twenty", "thirty" },
       { "one", "fifteen", "twentythree", "thirtyeight" },
       { "five", "thirteen", "twentynine", "thirtytwo" },
       { "seven", "seventeen", "twentyseven", "thirtyseven" }
    };

    compare_cols comp2(2) ; // compare strings in col two

    std::sort( std::begin(v2d), std::end(v2d), comp2 ) ; // sort on col two
    
    // binary search for string in col2 on sequence sorted on col 2
    bool found = std::binary_search( std::begin(v2d), std::end(v2d), "twentythree", comp2 ) ;
    std::cout << "found? " << std::boolalpha << found << '\n' ;
}

http://coliru.stacked-crooked.com/a/2e8fa75be767ce79

[infantheartlyjes]

Your code is working fine. But It is not working for upper_bound and lower_bound algorithms.

I tried like this below.
bool found = std::lower_bound( v2d.begin(), v2d.end(), "01011991", comp2 ) ;

I got the below error.

error: cannot convert ‘__gnu_cxx::__normal_iterator<std::vector<std::basic_string<char> >*, std::vector<std::vector<std::basic_string<char> > > >’ to ‘bool’ in initialization

[JLBorges]

> error: cannot convert '....' to ‘bool’ in initialization

std::upper_bound() and std::lower_bound() return iterators.
And std::equal_range() returns a pair of the two iterators.

http://coliru.stacked-crooked.com/a/3ea5f7e54a2a98f6