[tialaramex]

So, a few things (aside from the whole nomenclature argument already in another reply)

1. Stepanov's generic programming is a good idea. Every language you've seen with "generics" that's his idea, to the extent "The STL" is generic programming, everybody agreed it's a good idea.

2. But the STL is very old now, so while the idea is good, this is one of the oldest (Stepanov had tried this in other languages before C++) implementations and so other implementations are often better, because they've learned from experience

3. As well as pretty good generic algorithms, the STL also provides a lot of container types (what Rust would call collection types) and these vary not between "excellent" and "mediocre" but between "mediocre" and "inexplicably terrifying". The most charitable explanation is that they're just intended for teaching. If you teach DS&A to a Computer Science class you want the Extrusive Doubly Linked List to teach in class. If you write software you almost certainly never need this type, but it's front an centre in the C++ STL.

There's a single "I guess I would use this" container type, std::vector. It has an insane special case for bool, because WG21 are idiots, but it's otherwise a good enough growable array type and it's not worth building your own instead given the constraints.

Everything else is silly, or bad, or both. std::unordered_map feels like a hash table I made in class in the mid 1990s, but it's actually the provided standard hash table container in C++ 11 onwards. std::list is just that extrusive linked list for some insane reason. The Microsoft standard library maintainer STL could not offer me any justification for what std::deque is actually supposed to be for.

[bernds74]

I would argue that even the basic concept behind STL is misguided. The rationale I often see is "you only need N algorithms for M container type, instead of N*M". This ignores the fact that algorithms and data structures are not independent of each other, and also that most of the time these days you're operating on vectors, so M ~= 1.

Case in point: list::sort. You don't want to try running quicksort on a linked list. Or remove_if: great we've abstracted the difficult task of removing things without erasing them, except we can't do it on maps. (C++20 seems to add an erase_if, apparently admitting that the two-step remove/erase is silly).

Then there's the fact that C++ iterators are basically pointers into the data structure, where for vectors (your common case) you'd do much better with index/container pairs, both for stability and bounds checking.

[SJC_Hacker]

List::sort is present exactly for this reason

STD::sort only works on a random access iterator, it won’t even compile if you try it on a list

[einpoklum]

> There's a single "I guess I would use this" container type, std::vector.

About that one... I would claim that in a majority of cases where an std::vector is used, what the author really wanted was a similar type, but whose size and capacity are fixed on construction and never change. The standard C++ library does not offer such a type - so people use vector because it's handy.

Agree with your takes on most of the containers. I also dislike how optionals are never used with containers as they were standardized later (and even then, problematically w.r.t. references). Thus, for example, if I lookup an object in a map of T's, the result should IMNSHO be an optional reference to a T.

[Joker_vD]

> a similar type, but whose size and capacity are fixed on construction and never change.

There is std::array for that. Also, for a type with fixed capacity but variable (up to that capacity) size, we're getting std::inplace_vector soon™.

[einpoklum]

std::array requires the size to be set at compile-time, while I was talking about arrays whose size is determined at construction-time. Of course std::array is also quite the useful class :-)

[SJC_Hacker]

You can construct the vector with a given size. As long as you don’t push_back, beyond capacity, these should be o dynamic allocations.

If you want to get f cy you can also give it a custam allocator and throw an exception if you do this by mistake

[einpoklum]

> As long as you don’t push_back

But that's the point. You _can_ push_back, or resize, or reserve, etc. etc. My claim is that the more common use case is the one where this _cannot_ happen.

> If you want to get f cy you can also give it a custam allocator

And then nobody will want to use it, because that's not interchangeable with containers vector with the default allocator, and also difficult to understand. I mean, look at PMR allocators, which are not even that custom. They see very little use I'm afraid.

[Joker_vD]

Well, if you want to, I can write you a forwarder-wrapper around a std::vector that would inhibit allocation-inducing operations. Now, getting it into stdlib, that's a different matter entirely...

Also, do I understand correctly that you want both the capacity and the size fixed, i.e., the container's elements have to be pre-constructed and supplied to the constructor via an initializer list?

[afdbcreid]

What operations could such frozen vector offer that std::vector does not? If there are none, it doesn't need a separate data structure.

[einpoklum]

Oh, on the contrary, the separate structure is needed and useful because it offers _less_, not more:

* APIs/function signatures explain more clearly what are the intended uses of the structure that's passed.

* More potential for compiler optimization

* Some potential for having these on the stack (if the compiler deduces the size already at compile-time)

* More convenient for static analysis

* No plethora of confusing constructors (including the infernal two-element ctors which can be misinterpreted super-easily)

etc.

[nemetroid]

How are any of these achieved by a vector-like type with capacity frozen at construction time?

[quuxplusone]

The reason I'd want "frozen-size vector" is to replace pairs of data members of the form `T* foos; size_t foos_len;` without paying another 8 bytes to store a useless capacity that's never going to change.

But I don't think that makes such a container worth adding to the STL. So far, it hasn't even been worth writing in our own code. But that's the reason I've thought about writing it.

[uecker]

This is how I designed my vector in C. Note it is still not frozen as you can use realloc just fine (even with good performance) and/or external tracking of the capacity in tight loops.

https://uecker.codeberg.page/2025-07-20.html

I probably will still add a version with capacity, because people may insist on it, but personally I like the one without much more so far.

[ahartmetz]

AFAIK, std::map is also OK for what it is: an ordered, node-based (tree) map. These are (almost) always slower than hash tables. Of course, std::unordered_map, the std hash table, sucks because of unforced errors. For that, there is boost::unordered_flat_map.

[tialaramex]

std::map will be a Red Black Tree, as with most of the other container types this really likes pointer chasing

Unlike in std::unordered_map you are getting some value here, the RB tree is able to achieve meaningful efficiency gains from its use of pointers. The trouble is that your computer isn't a PDP-11, a hybrid which does fewer dereferences but has more locality will trade well here on a real computer built this century.

So, I'm torn, it's not awful but it's a problem that std::map is basically obliged to be a Red Black Tree even though that's not a good fit for today's machines.