What are vectors and how are they used in programming?
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
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.
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.
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