Why is a C++ Vector called a Vector?

The question's pretty self-explanatory really. I know vaguely about vectors in maths, but I don't really see the link to C++ vectors.

It's called a vector because Alex Stepanov, the designer of the Standard Template Library, was looking for a name to distinguish it from built-in arrays. He admits now that he made a mistake, because mathematics already uses the term 'vector' for a fixed-length sequence of numbers. C++11 compounds this mistake by introducing a class 'array' that behaves similarly to a mathematical vector.

Alex's lesson: be very careful every time you name something.

Mathematical definition of a vector is a member of the set Sn, which is an ordered sequence of values in a specific set (S). This is what a C++ vector stores.

An excerpt from The C++ Programming Language by Bjarne Stroustrup:

> "One could argue that valarray > should have been called vector > because it is a traditional > mathematical vector and that vector > should have been called array. > However, this is not the way the > terminology evolved."

The name comes from the linear algebra, where vector is matrix with only one column or only one row.

To complement the excellent response from @MarkRuzon:

Alex said that to give a name to what is now called std::vector he observed the name that Scheme and Common Lisp ​​had given to similar data structures.

Later he admits he was wrong because C++ vector has nothing to do with the vectors in mathematics.

He also says that he introduced an error of a community of 50 people to a community of 5 million people, so the error is likely to remain forever.

Just to say why it probably isn't called array: Because std::vector has a dynamic size. An array conceptually is fixed in length. Next C++ Standard by the way has a std::array template, which is fixed in size and should be preferred over a plain array:

std::array<int, 4> f = { 1, 2, 3, 4 };

It is just the name. C++ vector could very well (or maybe even more accurate) be called dynamic array or resizable array but this name was simply chosen. This vector is not the same as vector from methematics because in mathematics vectors are members of any set V such that there are two important operations defined on this set: + (addition of vectors) and x (multiplication of a vector by a scalar from field F) and these operations satisfy 8 axioms:

---

Associativity of addition

u + (v + w) = (u + v) + w

Commutativity of addition

u + v = v + u

Identity element of addition

There exists an element 0 ∈ V, called the zero vector, such that v + 0 = v for all v ∈ V.

Inverse elements of addition

For every v ∈ V, there exists an element −v ∈ V, called the additive inverse of v, such that v + (−v) = 0

Compatibility of scalar multiplication with field multiplication

a(bv) = (ab)v

Identity element of scalar multiplication

1 v = v, where 1 denotes the multiplicative identity in F.

Distributivity of scalar multiplication with respect to vector addition  

a(u + v) = au + av

Distributivity of scalar multiplication with respect to field addition

(a + b)v = av + bv

---

C++ std::vector supports all of them (not directly, but via C++ features), so it can somehow be called a vector, but it is just colloquialism and for example Vallaray pointed out by Bjarne Stroustrup in "C++ Programming Language" supports some of them directly.

Long time ago, in the B language there are vector types. Then the C language called them "arrays". Then the C with Classes and the C++ language just derived it ...

This is certainly not the whole story. As mentioned above, Stepanov made the actual decision. But if "vector" was still used in C, the result maybe looks quite different.

PS. I wonder why C renames "array". What was the exact reason?

PS2. IMO for a language as C++, an array is better meaning "a type hold elements to be reasonably accessed via operator[]" (i.e. not 42[some_array_object]), e.g. an instantiation of std::map as an "associative array".

A vector is simply a sequence of values, all of the same type. This is pretty much in line with the use in mathematics. I guess the mathematical idea that vectors should support some common operations (such as adding, and scaling by a scalar) are not carried over, the important aspect is mainly the structure.

Also if you make it store integers or floating points it does make an excellent type for storing N dimensional vectors. After all all a vector is, is a list of numbers kept in a specific order.

but mathematical vectors aren't dynamic, I've never seen one change from 2D to 3D or anything else, if anything traditional arrays make for better vectors.

I'd guess it comes from the term row vector. Also, computer scientists love thinking up new names for things...

Think of a C++ vector as a dynamic array, which size can be altered by inserting or removing elements. They are not related to the vector's mathematical definition.

Vectors in Mathematics

Consider an nxm matrix called A, where n corresponds to the number of rows, and m corresponds to the number of columns. In a mathematical context, once you introduce a matrix like this, then later, you can't do any operations outside of A's range and you can't extend A's size either. What this means is you can't refer to an index of [n + 1] and/or [m + 1].

Now, a vector of A derives these attributes as well, while their dimensions will always be 1xm (any [i] row selected within A) or nx1 (any [j] column selected within A). A vector also cannot be specified as 2xn, because a collection of vectors cannot be interpreted as one vector, while one vector - let that be the [i] column vector of A with the dimensions of 1xm - can be interpreted as a matrix.

The important takeaway is that you cannot change the dimensions of a vector once it is introduced in terms of mathematics.

Vectors in C++

In C++, vectors are just like vectors in mathematics, but unlike in mathematics their size can be altered. Size as a term applies here because it implies the element count that one particular vector contains.

You use the term dimensions in terms of C++ vectors, when you have a vector of vectors: std::vector<std::vector<T>>> ragged_array. In this example, I called that vector "ragged", because it demonstrates how the size of each vector of that vector can be altered independently. It not only violates the rules of how the dimensions cannot be changed once a particular vector is introduced in mathematics, but it also demonstrates, how it cannot be used as a matrix.

No idea about the real reason, but C++ calling it a vector instead of an array, reduces confusion between the C and C++ structures, although they fulfill the same roles.

Wonders that parametrisation on types does to names..

here a column gets blasted.. (view source for some server-side ASP.NET HTML encoding skills)

or was it a row?

Then again, thinking of it in MIMD or even SSE vector machine context, the name still sounds damn good.

it comes from the structure of matrix which build from vectors