4 ms·
Just to be clear, I never meant to suggest "only a b-tree", simply the option in the stdlib as per zug_zug (who I did not also take it as suggesting "only"). D
by cb321 2y ago
Just to be clear, I never meant to suggest "only a b-tree", simply the option in the stdlib as per zug_zug (who I did not also take it as suggesting "only"). Different data structures for different use cases as always.
JavaScript famously implemented arrays in terms of hash tables and.. In a similar vein, I've also known people who also mistakenly thought B-trees could replace a good hash table as the default &| go-to "associative container", but "order costs" (on one side or another) as you said elsewhere.
It's hard to say how much choice needs to be in a stdlib. Hence my exploring how to better say it. :-) E.g., Go has no b-tree in the stdlib, but has a bunch of crypto stuff. Nim has little to no crypto stuff, but has a critbits trie.
EDIT: Oh, and FWIW, at least abc-unix used B-trees for list & tables, not AVL trees.
- kragen 2y agothank you for the correction about abc! b-trees can sometimes replace a general hash table as the default associative array type. in part it depends on programming style and other parts of the language; in lisp, for example, the default associative array type was alists (linked lists of key-value pairs) for a long time, and emacs lisp still uses them pretty extensively. and i think you would be hard-pressed to find an sql implementation for which associative arrays are not usually b-trees—in part because in sql you tend to ask questions like 'which values correspond to these 1000 keys?' more often than 'which value corresponds to this key?', and in part for hysterical raisins. (when they wrote system r, oracle, and ingres, main memory was small, so locality of access was more important than it is now.)