2 ms·

Thanks everyone; I actually heard of this algorithm before but wasn't thinking of it today and missed this when I wrote the above post. >It's not clear to me h

Thanks everyone; I actually heard of this algorithm before but wasn't thinking of it today and missed this when I wrote the above post. >It's not clear to me how you're supposed to "tack the item on to the end of the array", though The algorithm mentions pointers so I think it means temporarily change a value in memory that is after the array with the array value. I'd be worried about how this would work if there are multiple threads, though, in case another thread wants to access the memory that was temporarily swapped out. (Edit: as other poster mentions, would be helpful to have an extra entry in the array for this purpose.) If the 'array' is internally something like a vector, then you can add it on to the end quickly by appending a node to the tail of a linked list.

vidarh 7y ago
It'd be problematic for some operations, but if your access is dominated by reads, then setting aside an extra entry for a sentinel value 'only' requires serialising operations that needs the sentinel value and mutations. You'll need to protect against mutations during the search anyway, so then it boils down to if its better to wait or fall back to a bounds-checking version. Though I'd question if it's worthwhile vs. some unrolling (you might even have a use for Duffs device...) to just do whatever number of iterations you want per bounds check.