ChatGPT解决这个技术问题 Extra ChatGPT

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.

Vectors (Magnitute + direction) in physics is the first thing which hits my mind the moment I hear the word vectors.

A
Arno van Wyk

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.


But array will also don't use heap allocation which makes moving it less efficiently. We also have std::valarray, btw.
Nice to know that they learned that lesson even though it's too late. Although ... typedef or #define can fix it too.
There are only two hard things in Computer Science: cache invalidation and naming things -- Phil Karlton
if you are going to claim "[Alex Stepanov] admits now that he made a mistake" in your answer, would you please provide a citation?
@TrevorBoydSmith The comment about it being a mistake can be found in his book "From mathematics to Generic programming"
m
mmx

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.


Vectors are only typically considered 2-3 dimensional because of their use in physics. But more generally in mathematics, they just mean a set of numbers that has an order (mathematical sets are orderless, they're like a bag filled with stuff). A vector can have any number of elements.
vartec, can't a Euclidean vector be represented as a coordinate vector and vice versa? They're just different representations of the same thing (a tuple) in Euclidian space versus the more general vector space.
@Joseph Garvin: Vectors don't even need to have components that are numbers. For example, certain sets of functions can be used to form vector spaces where the components are functions.
A vector is literally a "carrier". The same word is used for (e.g.) insects that transmit disease, and comes from the same Latin root as "vehicle". So it's something that takes you from one place to another. Incidentally, the word "matrix" is also from Latin, meaning "womb".
These seems unsatisfactory because: 1. Mathematical vectors don't change in dimension, 2. Mathematical vectors have operations that std::vector does not provide, 3. The argument that std::vector is an ordered sequence of values could apply to std::list, std::deque, std::basic_string, etc.
a
aib

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."


Pfftt.. what does that guy know. I've never even heard of this "Bjarne Stroustrup" person.
I just wonder how many of the upvotes of the previous comment are actually a result of an underflow...
Well, no, Bjarne. Array is very clearly a stack-allocated (unless declared static) fixed size (unless VLA) contiguous (at least in virtual memory) region of memory usually used to store elements of a single type. A better idea would be to call it da or dyarr or dyarray as it is a dynamically allocated array. Simply calling it an "array" would be no good.
v
vartec

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


F
Fernando Pelliccioni

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.


J
Johannes Schaub - litb

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 };

Has that new C++ standard been released yet?
this isn't much of an answer, since a vector has fixed size too. vectors are pure values, they are elements in a set that together with some additional structure form an abstract vector space. the notion of "changing the size" of a vector is complete nonsense.
@kai i think there's a confusion here. I have merely argued for why it is not called array. I have not tried to explained why it's specifically called vector. An array in C++ even before standardisation of the language has always had a fixed size, so naming the resizable class std::array would be no good.
now you can rightly complain that this isn't much of an answer, but a valid comment. Insofar I agree with the first half-sentence (up to the comma) of your comment. However, now it's too late to move my answer into a comment on the question, because these useful comments of you and @user12 would be lost.
As a compromise to solve the dilemma, I have made the answer community wiki. This removes all upvote points and downvote losses I got from my account. If anyone still wants to thanks me for my ingenious comment-in-disguise, they can upvote this representational comment.
4
4pie0

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.


No container in C++ have that kind of arithmetic defined so there are no vectors in C++. In particular a std::vector does not support arithmetic operations, and therefore, all of these properties are undefined for a std::vector. So a std::vector does not qualify as a vector. I would have called it dynamic_array or resizable_array which tells you what it is.
Or simply "list". But noooooo ... it had to be "vector" because that's what everyone uses, right?
@LearnCocos2D, well, a list is typically understood to be a linked list. In fact, there already is a container called list in the C++ standard library - it's a doubly linked list.
F
FrankHB

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, 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".


u
unwind

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.


In linear algebra, where "vector" comes from in mathematics, everything is about operations, with all vectors being the same size. The linear algebra, so the operations, is what makes a bunch of numbers a vector in mathematics.
J
James Matta

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.


this is blatantly false, that is not what a vector is en.wikipedia.org/wiki/Vector_space
@kai You will find these conflicts in other areas aswell. Real numbers in some programming languages will not be able to store 0.1, wheras in mathematics, this value is a member of the set of real numbers. In the Java programming language (docs.oracle.com/javase/7/docs/api/java/util/Vector.html) a vector is "The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created."
As for what a vector is, it depends on whose definition you use. As this question was asked on stackoverflow.com, rather than on math.stackexchange.com, I would argue for a less math-biased approach here.
@kai I am quite familiar with the definition of vector with regards to vector spaces. I am also familiar with the computer science definitions, where a vector is merely a list of number adjacent in memory, i.e. an array. Note that in the disambiguation page for vector in wikipedia that they show one meaning to be a 1D array. This is precisely the same meaning that is used for vector processors, which have been around since at least the 70s. Therefore, while the definition I gave is not the strict mathematical definition, it is a computer science definition, albeit older.
u
user137

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.


sure mathematical vectors are considered in many dimensions. If by being dynamic you mean that vector changes it's size then it may easily correspond to mathematical "consider this vector in dimension x" by adding or truncating coordinates. A simple linear transformation may map vectors from n-dim space to vectors in m-dim space. Mathematical vectors are VERY dynamic.
佚名

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


z
zaug

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.


R
Robert Gould

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.


r
rama-jka toti

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.


a
adir

it comes from the structure of matrix which build from vectors