An interesting data structure with search time O(sqrt n)
This is a very interesting discussion, but I'd like to ask a question about this in particular:<p>> The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative.<p>Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assumption).