title: If I want maximum speed, should I just use an array over a std::vector?
body: <p>I am writing some code that needs to be as fast as possible without sucking up all of my research time (in other words, no hand optimized assembly).</p>
  
  <p>My systems primarily consist of a bunch of 3D points (atomic systems) and so the code I write does lots of distance comparisons, nearest-neighbor searches, and other types of sorting and comparisons.  These are large, million or billion point systems, and the naive O(n^2) nested for loops just won't cut it.</p>
  
  <p>It would be easiest for me to just use a <code>std::vector</code> to hold point coordinates.  And at first I thought it will probably be about as fast an array, so that's great!  However, this question (<a href="https://stackoverflow.com/questions/3664272/stdvector-is-so-much-slower-than-plain-arrays">Is std::vector so much slower than plain arrays?</a>) has left me with a very uneasy feeling.  I don't have time to write all of my code using both arrays and vectors and benchmark them, so I need to make a good decision right now.</p>
  
  <p>I am sure that someone who knows the detailed <em>implementation</em> behind <code>std::vector</code> could use those functions with very little speed penalty.  However, I primarily program in C, and so I have no clue what <code>std::vector</code> is doing behind the scenes, and I have no clue if <code>push_back</code> is going to perform some new memory allocation every time I call it, or what other "traps" I could fall into that make my code very slow.</p>
  
  <p>An array is simple though; I know exactly when memory is being allocated, what the order of all my algorithms will be, etc.  There are no blackbox unknowns that I may have to suffer through.  Yet so often I see people criticized for using arrays over vectors on the internet that I can't but help wonder if I am missing some more information.</p>
  
  <p><strong>EDIT</strong>: To clarify, someone asked "Why would you be manipulating such large datasets with arrays or vectors"?  Well, ultimately, everything is stored in memory, so you need to pick <em>some</em> bottom layer of abstraction.  For instance, I use kd-trees to hold the 3D points, but even so, the kd-tree needs to be built off an array or vector.</p>
  
  <p>Also, I'm not implying that compilers cannot optimize (I know the best compilers can outperform humans in many cases), but simply that they cannot optimize better than what their constraints allow, and I may be unintentionally introducing constraints simply due to my ignorance of the implementation of vectors.</p>