title: Comprehensive vector vs linked list benchmark for randomized insertions/deletions
body: <p>So I am aware of <a href="https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl">this</a> question, and others on SO that deal with issue, but most of those deal with the complexities of the data structures (just to copy here, linked this theoretically has O(</p>
  
  <p>I understand the complexities would seem to indicate that a list would be better, but I am more concerned with the real world performance.</p>
  
  <p><strong>Note:</strong> This question was inspired by <a href="http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf" rel="nofollow noreferrer">slides 45 and 46 of Bjarne Stroustrup's presentation at Going Native 2012</a> where he talks about how processor caching and locality of reference really help with vectors, but not at all (or enough) with lists.</p>
  
  <p><strong>Question:</strong> Is there a good way to test this using CPU time as opposed to wall time, and getting a decent way of "randomly" inserting and deleting elements that can be done beforehand so it does not influence the timings?</p>
  
  <p>As a bonus, it would be nice to be able to apply this to two arbitrary data structures (say vector and hash maps or something like that) to find the "real world performance" on some hardware.</p>