3 ms·

I got to the "lesser known data structures" section and was already questioning the rest of the article: > B-Tree > Circular Buffer Are either of these "less

I got to the "lesser known data structures" section and was already questioning the rest of the article: > B-Tree > Circular Buffer Are either of these "lesser known"? Maybe if all you ever program in is higher-level languages. B-trees are damn near ubiquitous in OSdev, file systems, databases, or pretty much any indexing system. Ringbuffers are a hard requirement for pretty much any modern hardware interfacing. All Nvidia, AMD, etc graphics commands are issued via constructed ringbuffers. They're also pretty common in network programming, editor/IDE development, gamedev, and certainly OSdev (outside of drivers). > Cuckoo Hash Table, Open-Addressing Hash Tables These have the opposite status to the previous ones. They're not ubiquitous because the alternatives are better. Cuckoo Hash Tables exist almost singularly as a teaching paradigm about what not to do, because it's overly complex for little benefit. Open-Addressing Hash Tables are avoided (but definitely in use out there) because they require a very good hashing algorithm to avoid clustering+collisions and a large static address space. That all being said, it picks up and the later sections are much better.

williamcotton 3y ago
B-trees are damn near ubiquitous in OSdev, file systems, databases, or pretty much any indexing system. Most software developers are not working in any of these domains!
joshuamorton 3y ago
I believe most of the most efficient hash table impls in cpp use open addressing (swisstables and similar). The ones in std:: don't mostly because of pointer stability.
- deaddodo 3y ago
  Thus the: > (but definitely in use out there) Additionally, I didn't say they were less efficient. I said they require more logical complexity and upfront storage to be efficient.
fynfhd 3y ago
> Are either of these "lesser known"? Are any of these? It's odd, I have done a number of the things listed throughout my development as a developer, and for many, I would attribute a great deal of my knowledge to working on them, but, in each instance I came to those projects by my own necessity or transient interest. Something about seeing these all lazily listed here together frustrates me, and leaves me wanting to just say to anyone who questions their interest in programming because they are unable to see themself as someone who does all or even any of the things listed, "forget that, follow your passion".

williamcotton 3y ago

B-trees are damn near ubiquitous in OSdev, file systems, databases, or pretty much any indexing system. Most software developers are not working in any of these domains!

joshuamorton 3y ago

I believe most of the most efficient hash table impls in cpp use open addressing (swisstables and similar). The ones in std:: don't mostly because of pointer stability.

deaddodo 3y ago
Thus the: > (but definitely in use out there) Additionally, I didn't say they were less efficient. I said they require more logical complexity and upfront storage to be efficient.

fynfhd 3y ago

> Are either of these "lesser known"? Are any of these? It's odd, I have done a number of the things listed throughout my development as a developer, and for many, I would attribute a great deal of my knowledge to working on them, but, in each instance I came to those projects by my own necessity or transient interest. Something about seeing these all lazily listed here together frustrates me, and leaves me wanting to just say to anyone who questions their interest in programming because they are unable to see themself as someone who does all or even any of the things listed, "forget that, follow your passion".