[SOLVED] Customizing std::binary_search()



  • Hi,

    @bool MainWindow::myFuncForBinarySearch (const theList left, const theList right){
    return (left.procID < right.procID);
    }

    void MainWindow::hasChanged(QString & procname, short pid, short i)
    {
    if (std::binary_search(actualList.begin(), actualList.end(), pid, myFuncForBinarySearch))
    {
    //exist = 1
    actualList[pid].exist = 1;
    }
    else
    {
    //add pid to the vector
    tmpVector.push_back(pid);

        //add process to the actualList
        tmpClass.set_value(procname, pid, 1);
        actualList.push_back(tmpClass);
    }
    

    }
    @

    My problem that is the search() doesn't work with this cmp function.



  • myFuncForBinarySearch needs to take a @short@ as second argument, because you are comparing @short pid@ to the elements of the list.

    Try:
    @
    bool MainWindow::myFuncForBinarySearch (const listItem leftVal, const short rightVal){
    return (leftVal.procID < rightVal);
    }
    @



  • Thank moritzg.
    But I got these errors:

    ..\task-killer\mainwindow.cpp: In member function 'void MainWindow::hasChanged(QString, short int, short int)':
    ..\task-killer\mainwindow.cpp:87: error: argument of type 'bool (MainWindow::)(theList, short int)' does not match 'bool (MainWindow::)(theList, short int)'
    In file included from f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/algorithm:62,
    from f:\QtSDK\Desktop\Qt\4.8.1\mingw\include/QtCore/qglobal.h:68,
    from f:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qalgorithms.h:45,
    from f:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/QtAlgorithms:1,
    from ..\task-killer\mainwindow.cpp:1:
    f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_algo.h: In function 'bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<theList
    , std::vector<theList, std::allocator<theList> > >, _Tp = short int, _Compare = bool (MainWindow::)(theList, short int)]':
    ..\task-killer\mainwindow.cpp:87: instantiated from here
    f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_algo.h:2798: error: must use '.
    ' or '->' to call pointer-to-member function in '__comp (...)', e.g. '(... -> __comp) (...)'
    f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_algo.h: In function '_FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<theList*, std::vector<theList, std::allocator<theList> > >, _Tp = short int, _Compare = bool (MainWindow::)(theList, short int)]':
    f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_algo.h:2797: instantiated from 'bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<theList
    , std::vector<theList, std::allocator<theList> > >, _Tp = short int, _Compare = bool (MainWindow::)(theList, short int)]'
    ..\task-killer\mainwindow.cpp:87: instantiated from here
    f:\qtsdk\mingw\bin../lib/gcc/mingw32/4.4.0/include/c++/bits/stl_algo.h:2495: error: must use '.
    ' or '->' to call pointer-to-member function in '__comp (...)', e.g. '(... -> _comp) (...)'
    mingw32-make.exe[1]: Leaving directory `D:/Programozas/proba/with QT/task-killer-build-desktop-Qt_4_8_1_for_Desktop
    -_MinGW__Qt_SDK__Debug'
    mingw32-make.exe[1]: *** [debug/mainwindow.o] Error 1
    mingw32-make.exe: *** [debug] Error 2
    18:36:54: The process "F:\QtSDK\mingw\bin\mingw32-make.exe" exited with code 2.
    Error while building project task-killer (target: Desktop)
    When executing build step 'Make'



  • Use a free function as compare function, not a member function.



  • [quote author="Zlatomir" date="1342713135"]Use a free function as compare function, not a member function.[/quote]

    I changed. I have just one error.

    invalid initialization of reference of type 'const theList&' from expression of type 'const short int'

    @bool myFuncForBinarySearch (const theList & left, const short right){
    return (left.procID < right);
    }@



  • Well use the "normal" comparison:
    @
    bool MainWindow::myFuncForBinarySearch (const listItem& leftVal, const listItem& rightVal){ //don't forget references &
    return (leftVal.procID < rightVal.procID);
    }
    @ //because i guess that binary_search find equality by using (leftValue < rightValue) && (rightValue < leftValue) else it would required your type an operator== ;)
    And then create a temporary object in the search function (an object that only has the right id since you are not searching for anything else)
    @
    void MainWindow::hasChanged(QString & procname, short pid, short i)
    {
    listItem tempObj;
    tempObj.set_value("dummyText", pid, 0); /i don't know the exact definition of your set data - but i think you got the point/
    if (std::binary_search(actualList.begin(), actualList.end(), tempObj, myFuncForBinarySearch))
    {
    //exist = 1
    actualList[pid].exist = 1;
    }
    @



  • Yes, this is the solution :D
    I tired 5 minutes ago, and worked. ;)

    Thanks your reply.



  • Just a comment, since now i see that you use push_back in the search function: you need to make sure that the vector stays sorted (binary_search needs sorted array). So push_back add a copy of the element at the end of the vector (it doesn't care about your "sorted" vector)



  • [quote author="Zlatomir" date="1342767014"]Just a comment, since now i see that you use push_back in the search function: you need to make sure that the vector stays sorted (binary_search needs sorted array). So push_back add a copy of the element at the end of the vector (it doesn't care about your "sorted" vector)[/quote]

    Thanks. I known it. I have sorting "algorithm":http://qt-project.org/forums/viewthread/18910/P15/#92190.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.