Am I the only one confused by the C++ referential naming / the only C-but-not-C++ developer here? I have no idea what a shared_ptr is, or how a priority_queue behaves (is that a heap?)
The C++ envy does seem a bit peculiar, yes, but more so because my dissatisfaction with doing simple data structures in C is that I’m always doing a thousand twisty variations of the damn things, all just a little different, (usually to make allocations come out like I want them,) and it doesn’t feel like an STL-alike would solve that.
A priority queue is usually implemented as a heap (binary or otherwise) and frequently called that as well, but in more precise usage the gadget (abstract data type) you do INSERT and REMOVE-MIN to is the “priority queue”, and the implementation device of a(n implicit or explicit) tree where the value in any node is smaller than the values in its children is the “heap”. Roughly, “priority queue” is to “heap” like “ordered dictionary / map” is to “search tree”.
(I can’t think of any data structures that use heaps not for a priority queue except for treaps, but then my algorithm-fu is not particularly strong.)
As for shared_ptr, it’s just a refcounted pointer, but that bit of terminology is STL-specific so there might not be much value in learning it.
Just to clarify, the intent in my comment is that a whole bunch of the terms used there aren't "fluid associations" for me as a C developer. There's no issue looking them up, but they aren't what I would choose to name these containers.
(e.g. I would just call it "refcnt_ptr" and "heap" [if it is one], respectively)
shared_ptr is more special than a simple ref count though, it performs some level of mandatory thread synchronization for example; it's a C++-specific concept.
The STL was designed by A. Stepanov, who I suspect is simply too intelligent for this world. I have no idea what he's talking about half the time, but the rest is brilliant. Long story short; it's trying to solve a much bigger problem using a tool that wasn't built for it.
if stepanov would be too intelligent for this world, he would have designed proper iterators, not iterators which can run away. safe iterators are a thing, just not in the STL.
also he could have designed proper sets and usets. nobody really needs red-black trees when you have b- trees. likewise nobody needs linked-list usets, when you have open addressing or even swisstables.
you cannot copy from one container to another type. even the simpliest self-respecting libs support that.
you still have no string library, only memory buffers. many, many misdesigns in C++. just look at it, you'll get eyeblead
Don’t use macros for this. The better way to do it is to have headers that are designed to be included multiple times, each time with a different type. You end up with code that is possible to step through in a debugger instead of a macro-expanded mess.
For those who are interested in faster hashmaps, I tried bunch of hashmaps and this one performs better than others. This is for C. Maybe C++ has better hashmaps.
In a "hold my beer"-moment, I've ported GNU Trove's hash map to use memory mapped files instead of allocated memory. With good reason, granted, and it's not commonly used, but compared to almost anything else, it is fairly slow.
I basically need a mapping from arbitrary short strings to unique integer identifiers, with a cardinality in the billions. Too much to keep in memory, most db solutions keel over as well.
for this I would use CHM, ordered minimal perfect hashes with external mmap'ed keys. still constant lookup, just the position needs to be stored in the value also.
Problem is I don't know the items beforehand, instead I need to build the hash as I encounter new pages. I don't know any way of reconcile that with a minimal perfect hash.
https://github.com/FRRouting/frr/blob/master/lib/typesafe.h
https://github.com/FRRouting/frr/blob/master/doc/developer/l...
(disclaimer: it's my work.)