title: Efficient linked list in C++?
body: <p>This <a href="http://llvm.org/docs/ProgrammersManual.html#list" rel="noreferrer">document</a> says <code>std::list</code> is inefficient:</p>
  
  <blockquote>
    <p>std::list is an extremely inefficient class that is rarely useful. It performs a heap allocation for every element inserted into it, thus having an extremely high constant factor, particularly for small data types.</p>
  </blockquote>
  
  <p>Comment: that is to my surprise. <code>std::list</code> is a doubly linked list, so despite its inefficiency in element construction, it supports insert/delete in O(1) time complexity, but this feature is completely ignored in this quoted paragraph.</p>
  
  <p><strong>My question:</strong> Say I need a <strong>sequential</strong> container for small-sized homogeneous elements, and this container should support element <strong>insert/delete in O(1)</strong> complexity and does <strong>not</strong> need random access (though supporting random access is nice, it is not a must here). I also don't want the high constant factor introduced by heap allocation for <strong>each element's construction</strong>, at least when the number of element is small. Lastly, <strong>iterators</strong> should be invalidated only when the <strong>corresponding element</strong> is deleted. Apparently I need a custom container class, which might (or might not) be a variant of doubly linked list. How should I design this container?</p>
  
  <p>If the aforementioned specification cannot be achieved, then perhaps I should have a custom memory allocator, say, bump pointer allocator? I know <code>std::list</code> takes an allocator as its second template argument.</p>
  
  <p>Edit: I know I shouldn't be too concerned with this issue, from an engineering standpoint - fast enough is good enough. It is just a <strong>hypothetical question</strong> so I don't have a more detailed use case. Feel free to relax some of the requirements!</p>
  
  <p>Edit2: I understand two algorithms of <em>O</em>(1) complexity can have entirely different performance due to the difference in their constant factors.</p>