How We Beat C++ STL Binary Search

Post by arbre » Wed, Aug 12, 2015, 3:41 AM UTC

lhecker wrote: post #23

Noughmad wrote: post #7

There is no mention of the fact that the STL implementation is very generic, it only assumes operator++ and operator* on the iteration, and operator The "optimized" versions here all make more assumptions on the iterator, starting from operator+(int) in Version 1, so it no longer works on iterators with just "forward_iterator_tag". Further versions even restrict vector sizes (albeit to a very high number) and assign…

Just a nitpick: Assigning a negative value to an unsigned integer is perfectly safe and well defined (i.e. integer overflow for unsigned integers is well defined in the C++ spec). Using -1 for size_t is sometimes even prefered to assign it's maximum value, since there is no cross-platform #define for it (most use either SIZE_T_MAX or SIZE_MAX). In fact llvm's libc++ uses it for it's std::numeric_limits implementation…

Post by cautious_int » Wed, Aug 12, 2015, 5:38 AM UTC

banachtarski wrote: post #36

cautious_int wrote: post #13

Earlier quoted context omitted.

That blog is wrong. The program won't be undefined( unsigned wrap is defined ), but the offset will not be correct.

That's not true. Unsigned wrap is well-defined and wraps around to 0. Signed wrap is undefined.

Post by zubairsaif007 » Wed, Aug 12, 2015, 6:26 AM UTC

Post by lhecker » Wed, Aug 12, 2015, 1:14 PM UTC

Joky wrote: post #32

lhecker wrote: post #23

Earlier quoted context omitted.

Just a nitpick: Assigning a negative value to an unsigned integer is perfectly safe and well defined (i.e. integer overflow for unsigned integers is well defined in the C++ spec). Using -1 for size_t is sometimes even prefered to assign it's maximum value, since there is no cross-platform #define for it (most use either SIZE_T_MAX or SIZE_MAX). In fact llvm's libc++ uses it for it's std::numeric_limits implementation…

I believe there is a standard cross-platform maximum value, and you mention it in your last sentence: std::numeric_limits!

Post by dastbe » Wed, Aug 12, 2015, 2:47 PM UTC

cautious_int wrote: post #45

dastbe wrote: post #41

Earlier quoted context omitted.

So the article isn't wrong, but its misleading you into thinking this should be correct for the wrong reasons. They are using signed integers as their indices, which means that the signed bit is always 0. Thus the addition after casting to unsigned will never overflow, and you can divide by two (shift by 1) and then recast to a signed integer, no harm no foul.

Actually it is misleading by them( and you ) to assume that in C, an unsigned int can represent values larger than the largest signed int value. In other words, C allows that UINT_MAX == INT_MAX, in which case you will overflow. If they made that assumption, they should explicitly mention it, but they didn't. > Update 17 Feb 2008:... ...Now that we've made this change, we know that the program is correct;) It seems t…