Comment by tialaramex
15 days ago
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.
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
1 reply →
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.
[flagged]