I've recently (last 3 years) moved my bare-metal embedded software development from C to C++ so I've actually run into issues of STL adding too much to the binary size.

To give a real-world example, I'm working on a custom device that is a type of data cartridge. I have a "big" ARM-A5(Atmel SAMA5D36) processor running embedded linux that does all the heavy lifting but goes down when main power is removed. I have a small ARM-Cortex-M0(LPC824) that is always running on a battery and manages power, watches for button-presses, and a few other janitorial items on the device. The small processor has 32kB of program space and 8kB of RAM, and my project is mostly C++. Here are some specific examples of how using any STL will bloat program size:

Using std::string, and touching any of the STL string handling immediately adds 20kB to my binary. Using stl::list is 6-10kB of program space (actually not that bad and std::vector is pretty efficient). Adding exception handling adds 5kB of code and a single exception adds 6kB of code (not stl but just an example).

I've worked on a lot of embedded projects and my general rule of thumb for, "How big of a part do I need to use fully-featured C++?" is 256kB of program space -- something most bare-metal embedded software engineers would call a large amount of program memory. On projects where I have less than that I don't use STL and basically use C++ as C with classes, function/operator overloading and templates.