http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46139
Summary: bug in std::binary_search realisation
Product: gcc
Version: 4.4.4
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
AssignedTo: unassig...@gcc.gnu.org
ReportedBy: emathe...@gmail.com
Created attachment 22128
--> http://gcc.gnu.org/bugzilla/attachment.cgi?id=22128
files with problem cpps, workarounds and patches
Platform:
Using built-in specs.
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla
--enable-bootstrap --enable-shared --enable-threads=posix
--enable-checking=release --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-languages=c,c++,objc,obj-c++,java,fortran,ada --enable-java-awt=gtk
--disable-dssi --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre
--enable-libgcj-multifile --enable-java-maintainer-mode
--with-ecj-jar=/usr/share/java/eclipse-ecj.jar --disable-libjava-multilib
--with-ppl --with-cloog --with-tune=generic --with-arch_32=i686
--build=x86_64-redhat-linux
Thread model: posix
gcc version 4.4.4 20100630 (Red Hat 4.4.4-10) (GCC)
Problem:
1) it is unable to compile std::binary_search with compare function, if type of
searched value mismatch container::value_type (see binary_search_*.cpp in
attached archive)
Compile Error for binary_search_left.cpp:
g++ -Wall -o "binary_search_left" "binary_search_left.cpp" (in directory:
/home/hotdox/tmp)
In file included from
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/algorithm:62,
from binary_search_left.cpp:2:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:
In function ‘bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare)
[with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = bool (*)(int, const
TStruct&)]’:
binary_search_left.cpp:30: instantiated from here
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2798:
error: cannot convert ‘const TStruct’ to ‘int’ in argument passing
Compilation failed.
Compile Error for binary_search_rigth.cpp:
g++ -Wall -o "binary_search_rigth" "binary_search_rigth.cpp" (in directory:
/home/hotdox/tmp)
In file included from
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/algorithm:62,
from binary_search_rigth.cpp:2:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:
In function ‘_FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)
[with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = bool (*)(const TStruct&,
int)]’:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2797:
instantiated from ‘bool std::binary_search(_FIter, _FIter, const _Tp&,
_Compare) [with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = bool (*)(const TStruct&,
int)]’
binary_search_rigth.cpp:30: instantiated from here
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2495:
error: invalid initialization of reference of type ‘const TStruct&’ from
expression of type ‘int’
Compilation failed.
2) it is unable to compile std::binary_search with compare functor with one
nameless operator, if type of searched value mismatch container::value_type
(see binary_search_functor_*.cpp in attached archive)
Compile Error for binary_search_functor_left.cpp:
g++ -Wall -o "binary_search_functor_left" "binary_search_functor_left.cpp" (in
directory: /home/hotdox/tmp)
In file included from
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/algorithm:62,
from binary_search_functor_left.cpp:2:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:
In function ‘bool std::binary_search(_FIter, _FIter, const _Tp&, _Compare)
[with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = TComparator]’:
binary_search_functor_left.cpp:32: instantiated from here
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2798:
error: no match for call to ‘(TComparator) (const TStruct&, int&)’
binary_search_functor_left.cpp:14: note: candidates are: bool
TComparator::operator()(int, const TStruct&)
Compilation failed.
Compile Error for binary_search_functor_rigth.cpp:
g++ -Wall -o "binary_search_functor_rigth" "binary_search_functor_rigth.cpp"
(in directory: /home/hotdox/tmp)
In file included from
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/algorithm:62,
from binary_search_functor_rigth.cpp:2:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:
In function ‘_FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)
[with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = TComparator]’:
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2797:
instantiated from ‘bool std::binary_search(_FIter, _FIter, const _Tp&,
_Compare) [with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, _Tp = TStruct, _Compare = TComparator]’
binary_search_functor_rigth.cpp:32: instantiated from here
/usr/lib/gcc/x86_64-redhat-linux/4.4.4/../../../../include/c++/4.4.4/bits/stl_algo.h:2495:
error: no match for call to ‘(TComparator) (int&, const TStruct&)’
binary_search_functor_rigth.cpp:14: note: candidates are: bool
TComparator::operator()(const TStruct&, int)
Compilation failed.
Workaround: create compare functor with both left and rigth nameless operators
(see binary_search_workaround.cpp in attached archive)
Fix:
change bits/stl_algo.h:2495 for:
if (__comp(__val, *__middle))
(patch_1.diff)
or
change bits/stl_algo.h:2978 for:
return __i != __last && !bool(__comp(*__i, __val));
(patch_2.diff)
