title: Why is it so slow iterating over a big std::list?
body: <p>As title suggests, I had problems with a program of mine where I used a std::list as a stack and also to iterate over all elements of the list. The program was taking way too long when the lists became very big.</p>
  
  <p>Does anyone have a good explanation for this? Is it some stack/cache behavior?</p>
  
  <p>(Solved the problem by changing the lists to std::vector and std::deque (an amazing data structure by the way) and everything suddenly went so much faster)</p>
  
  <p>EDIT: I'm not a fool and I don't access elements in the middle of the lists. The only thing I did with the lists was to remove/add elements at the end/beginning and to iterate through <strong>all</strong> elements of the list.
  And I always used iterators to iterate over the list. </p>