[SOLVED] Customizing std::binary_search()

I-sty

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.

moritzg

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

I-sty

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'

Zlatomir

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

I-sty

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

Zlatomir

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

I-sty

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

Thanks your reply.

Zlatomir

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)

I-sty

[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.