Hacker News Reader

Comment by tialaramex | Hacker News Reader

For the containers in particular this makes a lot of sense because the C++ stdlib containers are just not very good. Some of this is because C++ inherited types conceived as pedagogic tools. If you're teaching generic programming you might want both (single and double) extrusive linked list types for your explanation. But for a C++ programmer asking "Which of these do I want?" the answer is almost always neither.

The specification over-specifies std::unordered_map so that no good modern hash table type could implement this specification, but then under-specifies std::deque so that the MSVC std::deque is basically useless in practice. It requires (really, in the standard) that std::vector<bool> is a bitset, even though that makes no sense. It sometimes feels as though nobody on WG21 has any idea what they're doing, which is wild.

View on HN

Linked lists used to be more efficient than dynamic arrays — 40 years ago, before processors had caches.

Intrusive linked lists still firmly have a place in modern code, for reasons other than performance. I don’t know many good reasons for extrusive linked lists, even before caches. There might be a few, but a dynamic array is (and has always been?) usually preferable to an extrusive list.

> I don’t know many good reasons for extrusive linked lists

for one, its iterator won't be invalidated

That depends on which array & extrusive linked list classes you’re talking about. Let me put it another way: in three decades of professional coding in scientific computing, video games, film vfx, web programming, and GPU driver and hardware development, I’ve never had to reach for an extrusive linked list for work. I’ve only ever used them for learning, teaching, and toy projects.

I haven't benchmarked them myself yet, but the C++23 flat map containers are supposed to finally have fixed this. Chrome lists them as TBD: https://chromium.googlesource.com/chromium/src/+/main/styleg... .

When you say "fixed this" which "this" do you think they fixed? Are you imagining this is a hash table? It's not

It's an adaptor which will use two other containers (typically std::vector) to manage the sorted keys and their associated values. The keys are sorted and their values are stored in the corresponding position in their own separate std::vector. If you already have sorted data or close enough then this type can be created almost for free yet it has similar affordances to std::map - if you don't it's likely you will find the performance unacceptable.

Reply on news.ycombinator.com