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.

Answer 2

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.

Vectors are good at:

• Accessing individual elements by their position index (constant time).
• Iterating over the elements in any order (linear time).
• Add and remove elements from its end (constant amortized time).

REF

Answer 3

Since at least two of the other answers are pasted from this site, you might also want to read the rest of the description there... :-)

Answer 4

The mathematical vectors you're used to are tensors of rank one; the data structures in computer science don't necessarily obey the tensor transformation rules. They're just arrays that can expand and contract, as noted earlier.

Answer 5

I can understand your confusion from the names (I used to be confused by that too). It's not helped by the idea of a Vector in 3D graphics programming, which is closer to the mathematical definition. In math, a Vector can be thought of as a 1-dimensional matrix of arbitrary length (with the length being the number of dimensions of your coordinate system). In most OO languages, the vectors are essentially 1-dimensional matrices (arrays), hence the name. They don't have anything to do with coordinates unless the programmer decides to use them for that task (which is rare -- I've never seen it). They also don't usually have any mathematical operators for doing matrix multiplication or any similar operations. So the 1-dimensional nature of them is about where the similarity ends. I'll leave it to the other answers to explain the features and uses of the OO container, which they already have a handle on.

Answer 6

In mathematics, a vector can be thought of as a combination of direction and magnitude. However, it can also be thought of as a coordinate. For example, a vector with magnitude 5 and an angle of about 37 degrees from the horizontal represents a point on a 2D plane. This point can also be represented with the Cartesian coordinate pair (3, 4). This pair (3, 4) is also a mathematical vector.

In programming, this name "vector" was originally used to describe any fixed-length sequence of scalar numbers. A vector of length 2 represents a point in a 2D plane, a vector of length 3 represents a point in a 3D space, and so on. A vector of length 100 represents a point in a 100-dimensional space (mathematicians have no trouble thinking about such things).

In modern programming libraries, this name "vector" has come to generally mean a variable sized sequence of values (not necessarily numbers). Changing the size (length, or dimensionality) of a mathematical vector isn't something you would normally do unless you're doing some kind of projection operation. But changing the length of a programming vector that contains a sequence of strings might be a common operation.

Answer 7

From the SICP book:

To model computer memory, we use a new kind of data structure called a vector. Abstractly, a vector is a compound data object whose individual elements can be accessed by means of an integer index in an amount of time that is independent of the index.