In my experience the C mindset is to write those yourself. The lack of templates means that it's very difficult to write proper generic containers. You either end up with macro soup, void * soup or code tailored to your needs. Or a lot of the time a combination of all three.

But I'm like you, if I know that I'm going to need "advanced" data structures I'll pick C++ over C (or these days more likely Rust).

I think that holds for any program written in any language. If the abstractions are confusing then it will be hard to read, be it layers of C macros, over-use of template programming or bad class hierarchy. BTW C++'s standard library is mostly functional (having roots in scheme), which makes it pretty easy to reason about.