How much extra memory (if any) does a std::set take to store its elements v.s. a std::vector?
c++, set, std, stl, vector
Solution
A `std::set` is implemented as a binary tree, so has nodes with left and right pointers as well as a data element. The allocation for each of these may be rounded up by your dynamic memory library functions. So yes - for elements of a machine word or three, the overhead's going to be "significant" as a ratio/percentage (e.g. 2 64-bit pointers + a `char` could easily round up to e.g. 32 bytes... a 32x overhead), and may or may not be significant from an system/application behaviour perspective. If you care, always measure on your own system.
For average-9-char `string`s, overall memory usage will be not only a factor of whether you use `set` or `vector`, but also how many `string`'s text will fit into any Short-String-Optimisation buffer (internal to the `string` object; if you implementation provides such an optimisation), rather than needing further dynamic memory allocated to store the text.
Problem
It must be implementation dependent, but is there any sort of significant memory overhead to using std::set ? EDIT: In my case, I have a set of std::string, with average string length of 9 letters.