Associative Arrays max length? 32bit/64bit

monarch_dodra via Digitalmars-d digitalmars-d at puremagic.com
Sat May 17 14:43:29 PDT 2014


On Saturday, 17 May 2014 at 20:30:30 UTC, bearophile wrote:
> Sorry, I didn't know the linked list is sorted. It's scanned 
> sequentially, because you can't use a binary search on a 
> regular linked list. Perhaps a skiplist is better to avoid 
> O(n^2) behavour in presence of attacks or degenerate cases (in 
> past the AA used a tree there).
>
> Bye,
> bearophile

*Technically*, for a sorted linked list (or forward iterators in 
general), you can find the result with O(N) *walk* iterations, 
but still only O(log(N)) *comparison* iterations.

So saying "you can't use binary search on a regular linked list" 
is not quite 100% accurate. You can still get some bang for your 
buck out of a degenerated algorithm.

http://www.cplusplus.com/reference/algorithm/binary_search/


More information about the Digitalmars-d mailing list