3 ms·

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

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.

menaerus 9mo ago
[flagged]
direwolf20 9mo ago
Linked lists used to be more efficient than dynamic arrays — 40 years ago, before processors had caches.
- dahart 9mo ago
  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.
  - mshockwave 9mo ago
    > I don’t know many good reasons for extrusive linked lists for one, its iterator won't be invalidated
    - dahart 9mo ago
      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.
boulos 9mo ago
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/styleguide/c++/c++-features.md#std_flat_map_std_flat_multimap_std_flat_set_std_flat_multiset-tbd https://chromium.googlesource.com/chromium/src/+/main/styleg... .
- tialaramex 9mo ago
  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.

menaerus 9mo ago

[flagged]

direwolf20 9mo ago

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

dahart 9mo ago
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.
- mshockwave 9mo ago
  > I don’t know many good reasons for extrusive linked lists for one, its iterator won't be invalidated
  - dahart 9mo ago
    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.

boulos 9mo ago

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/styleguide/c++/c++-features.md#std_flat_map_std_flat_multimap_std_flat_set_std_flat_multiset-tbd https://chromium.googlesource.com/chromium/src/+/main/styleg... .

tialaramex 9mo ago
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.