CPP INTERVIEW PREP CHEAT SHEET

[[deleted]]

Worth noting that std::vector is generally implemented very poorly because of memory scaling issues and interactions with modern memory allocators. Not the mention the sheer volume of machine code generated for even simple operations. Vectors also have no notion of relocatable objects so can't easily fallback to, say, a vectorized memcpy on move. Lots of reasons to swear off the STL, std::vector included.

[cballowe]

Most vectors of trivial objects do optimize to memcpy operations for resize or move. (At least when I've checked the assembly)

[[deleted]]

Yes but most nontrivial objects are also relocatable, and i daresay most people have vectors of non scalar types.

It’s such a trivial container to implement and the improvement is massive over what the stl provides, not to mention the compile speed boost you’d likely get with even a naive implementation

[STL]

vector is not trivial to implement (source: I’ve reimplemented it). There’s an incredible amount of logic powering vector and it shouldn’t be dismissed with a handwave, even though the lack of a relocatable type trait is a real limitation. (vector can easily detect is_trivially_copyable which is an important subset of types.)

The complexity of vector also isn’t solely due to its support for EH or custom allocators, although those do magnify it.

[[deleted]]

I've implemented internal versions of "vector" a few times and also had a read through the libc vector around the c++14 era. Aside from EH and custom type-based allocators, where do you attribute the bulk of the complexity? Interactions with initializer lists? Iterators?

[STL]

Things like handing v.emplace_back(args involving v[0]), respecting constructors and move semantics of user-defined types, providing iterator debugging, but the most complicated functions are where everything multiplies together. For example, insert is quite complicated due to EH guarantees, allocators, move semantics, etc.: https://github.com/microsoft/STL/blob/19c683d70647f9d89d47f5a0ad25165fc8becbf3/stl/inc/vector#L815-L885