C++’s standard library containers are extremely convenient, as standard library components should be. They’re so convenient that you’ve probably only ever needed to remember their Big-O notations for insertion, deletion, and search after your data structures final exam. However, beyond their cold, clean, bare, templated masks, C++ container templates are quite complex.
Most of the time, when you’re using a container, you don’t care about how it allocates or frees memory. But, because the specifics of allocation can sometimes matter, C++ exposes the allocation backend to you through a default template parameter. The default allocator most of the standard library uses for its containers is std::allocator<T>
on the type you’re allocating.
Now, from a programming perspective, this is great. C++ is well-known for the control it allows you to have over memory, alongside other primitives. It provides this control while still trying to be user-friendly by hiding options most programmers will never need to use. Unfortunately, as reverse engineers, these things are no longer hidden from us. And, since even default templates are a form of code reuse and generation, those default parameters can balloon into type signatures of insane sizes at compile time.
This begs the question: What does something as simple as vector<string>
really look like? And how bad can it get?
Read more...