title: What C++ STL class should I use to reduce fragmentation caused by lots of small allocations?
body: <p>My C++ class builds a tree structure over time. Each node in the tree is currently allocated on construction (using new). The node class uses only a few bytes of memory. As the tree grows there may be 100,000s of nodes; the maximum number of nodes is not known on construction of the tree, other than the theoretical maximum of 2^33. I reference nodes in the tree structure by their pointer. All nodes are deallocated on destruction of the tree, and only then.</p>
  
  <p>I'm after a Standard Library container or memory allocator/pool that I can use to allocate and store the nodes within my tree class, in order to reduce memory fragmentation and memory allocation overhead. I'd like to avoid having to write a custom allocator. The container should have the following two properties:</p>
  
  <ol>
  <li>Allocated objects do not move in memory, therefore can referenced by pointers safely.</li>
  <li>The class allocates memory for large blocks of objects, thus reducing memory fragmentation. Note that I do <strong>not</strong> require the entire container to be contiguous in memory.</li>
  </ol>
  
  <p>I do not need the iterator or lookup functionality of the container, as my tree structure stores the pointers. What Standard Library class will provide me with this functionality, and give me the lowest memory overhead?</p>