What are vectors and how are they used in programming?

Question

I'm familiar with the mathematical/physics concept of a vector as a magnitude and a direction, but I also keep coming across references to vectors in the context of programming (for example C++ seems to have a stl::vector library which comes up fairly frequently on SO).

My intuition from the context has been that they're a fairly primitive construct most often used to represent something along the lines of a variable length array (storing its size as the magnitude, I presume), but it would be really helpful if somebody could provide me with a more complete explanation, preferably including how and why they're used in practice.

Answer 1

From http://www.cplusplus.com/reference/stl/vector/

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.

Furthermore, vectors can typically hold any object - so you can make a class to hold information about vehicles, and then store the fleet in a vector.

Nice things about vectors, aside from resizing, is that they still allow access in constant time to individual elements via index, just like an array.

The tradeoff for resizing, is that when you hit the current capacity it has to reallocate, and sometimes copy to, more memory. However most capacity increasing algorithms double the capacity each time you hit the barrier, so you never hit it more than log2(heap available) which turns out to be perhaps a dozen times in the worst case throughout program operation.

-Adam