 <p>As mentioned by @SirDarius, this is implementation dependent and therefore you would need to check on a per implementation basis.</p> <p><em>Usually</em>, <code>std::set</code> is implemented as a red-black tree with lean iterators. This means that for each element in the set, there is <em>one node</em>, and this node roughly contains:</p> <ul> <li>3 pointers: 1 for the parent node, 1 for the left-side child and one for the right-side child</li> <li>a tag: red or black</li> <li>the actual user type</li> </ul> <p>The minimal foot-print of such a node on a 64 bits platform is therefore <code>footprint(node)</code>:</p> <ul> <li>3*8 bytes</li> <li><code>sizeof(MyClass)</code>, rounded to 8 bytes (for alignment reasons: look up "struct padding")</li> </ul> <p><em>Note: it is easy to use an unused bit somewhere to stash the red/black flag at no additional cost, for example taking into account the fact that given node alignments the least-significant bits of the pointers are always <code>0</code>, or inserting in <code>MyClass</code> padding if any.</em></p> <p><em>However</em>, when you allocate an object <code>T</code> via <code>new</code> (which is what <code>std::allocator</code> does under the hood, and which itself uses <code>malloc</code> unless overloaded), you do not allocate <em>just</em> <code>sizeof(T)</code> bytes:</p> <ul> <li>a typical implementation of <code>malloc</code> uses <em>size buckets</em>, meaning that if you have 8 bytes buckets and 16 bytes buckets when you allocate a 9 bytes object it goes into a 16 bytes bucket (wasting 7 bytes)</li> <li>furthermore, the implementation also has some overhead to <em>track</em> those allocated blocks of memory (to know not to reuse that memory until it's freed); though minimal, the overhead can be non-negligible</li> <li>finally, the OS itself has some overhead for each page of memory that the program requests; although that is probably negligible</li> </ul> <p>Therefore, indeed, the use of a <code>set</code> will most likely consume <em>more</em> than just <code>set.size() * sizeof(MyClass)</code>, though the overhead depends on your Standard Library implementation. This overhead will likely be large for small objects (such as <code>int32_t</code>: on a 64-bits platform you are looking at least at a +500% overhead) because the cost of linking the nodes together is usually fixed, whereas for large objects it might not be noticeable.</p> <hr> <p>In order to reduce the overhead, you traditionally use <em>arrays</em>. This is what a B-Tree does for example, though it does so at the cost of <em>stability</em> (ie, each element staying at a fixed memory address regardless of what happens to the others).</p>