Why Is a C++ Vector Called a Vector

Why is a C++ Vector called a Vector?

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

Why use c() to define vector?

Owen's answer is perfect, but one other thing to note is that c() can concatenate more than just vectors.

> x = list(a = rnorm(5), b = rnorm(7))
> y = list(j = rpois(3, 5), k = rpois(4, 2), l = rbinom(9, 1, .43))
> foo = c(x,y)
> foo
$a
[1]  0.280503895 -0.853393705  0.323137905  1.232253725 -0.007638861

$b
[1] -2.0880857  0.2553389  0.9434817 -1.2318130 -0.7011867  0.3931802 -1.6820880

$j
[1]  5 12  5

$k
[1] 3 1 2 1

$l
[1] 1 0 0 1 0 0 1 1 0

> class(foo)
[1] "list"

Second Example:

> x = 1:10
> y = 3*x+rnorm(length(x))
> z = lm(y ~ x)
> is.vector(z)
[1] FALSE
> foo = c(x, z)
> foo
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 3

[[4]]
[1] 4

[[5]]
[1] 5

[[6]]
[1] 6

[[7]]
[1] 7

[[8]]
[1] 8

[[9]]
[1] 9

[[10]]
[1] 10

$coefficients
(Intercept)           x 
   0.814087    2.813492 

$residuals
         1          2          3          4          5          6          7 
-0.2477695 -0.3375283 -0.1475338  0.5962695  0.5670256 -0.5226752  0.6265995 
         8          9         10 
 0.1017986 -0.4425523 -0.1936342 

$effects
 (Intercept)            x                                                     
-51.50810097  25.55480795  -0.05371226   0.66592081   0.61250676  -0.50136423 

  0.62374031   0.07476915  -0.49375185  -0.26900403 

$rank
[1] 2

$fitted.values
        1         2         3         4         5         6         7         8 
 3.627579  6.441071  9.254562 12.068054 14.881546 17.695038 20.508529 23.322021 
        9        10 
26.135513 28.949005 

$assign
[1] 0 1

$qr
$qr
   (Intercept)            x
1   -3.1622777 -17.39252713
2    0.3162278   9.08295106
3    0.3162278   0.15621147
4    0.3162278   0.04611510
5    0.3162278  -0.06398128
6    0.3162278  -0.17407766
7    0.3162278  -0.28417403
8    0.3162278  -0.39427041
9    0.3162278  -0.50436679
10   0.3162278  -0.61446316
attr(,"assign")
[1] 0 1

$qraux
[1] 1.316228 1.266308

$pivot
[1] 1 2

$tol
[1] 1e-07

$rank
[1] 2

attr(,"class")
[1] "qr"

$df.residual
[1] 8

$xlevels
named list()

$call
lm(formula = y ~ x)

$terms
y ~ x
attr(,"variables")
list(y, x)
attr(,"factors")
  x
y 0
x 1
attr(,"term.labels")
[1] "x"
attr(,"order")
[1] 1
attr(,"intercept")
[1] 1
attr(,"response")
[1] 1
attr(,".Environment")
<environment: R_GlobalEnv>
attr(,"predvars")
list(y, x)
attr(,"dataClasses")
        y         x 
"numeric" "numeric" 

$model
           y  x
1   3.379809  1
2   6.103542  2
3   9.107029  3
4  12.664324  4
5  15.448571  5
6  17.172362  6
7  21.135129  7
8  23.423820  8
9  25.692961  9
10 28.755370 10

How can a std::vector name be treated like a C-type array name?

If you can't change the function signature than you can pass the vector's data() and size() properties, which are compatible with the function:

foo(v.data(), v.size());

How to sum up elements of a C++ vector?

Actually there are quite a few methods.

int sum_of_elems = 0;

C++03

Classic for loop:

 for(std::vector<int>::iterator it = vector.begin(); it != vector.end(); ++it)
     sum_of_elems += *it;

Using a standard algorithm:
```
 #include <numeric>

 sum_of_elems = std::accumulate(vector.begin(), vector.end(), 0);
```
Important Note: The last argument's type is used not just for the initial value, but for the type of the result as well. If you put an int there, it will accumulate ints even if the vector has float. If you are summing floating-point numbers, change 0 to 0.0 or 0.0f (thanks to nneonneo). See also the C++11 solution below.

C++11 and higher

b. Automatically keeping track of the vector type even in case of future changes:

 #include <numeric>

 sum_of_elems = std::accumulate(vector.begin(), vector.end(),
                                decltype(vector)::value_type(0));

Using std::for_each:

 std::for_each(vector.begin(), vector.end(), [&] (int n) {
     sum_of_elems += n;
 });

Using a range-based for loop (thanks to Roger Pate):

 for (auto& n : vector)
     sum_of_elems += n;

C++17 and above

Using std::reduce which also takes care of the result type, e.g if you have std::vector<int>, you get int as result. If you have std::vector<float>, you get float. Or if you have std::vector<std::string>, you get std::string (all strings concatenated). Interesting, isn't it?
```
auto result = std::reduce(v.begin(), v.end());
```
There are other overloads of this function which you can run even parallelly, in case if you have a large collection and you want to get the result quickly.

Are std::vector elements guaranteed to be contiguous?

This was missed from C++98 standard proper but later added as part of a TR. The forthcoming C++0x standard will of course contain this as a requirement.

From n2798 (draft of C++0x):

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized)
constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage
management is handled automatically, though hints can be given to improve efficiency. The elements of a
vector are stored contiguously, meaning that if v is a vector where T is some type other
than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Using arrays or std::vectors in C++, what's the performance gap?

Using C++ arrays with new (that is, using dynamic arrays) should be avoided. There is the problem that you have to keep track of the size, and you need to delete them manually and do all sorts of housekeeping.

Using arrays on the stack is also discouraged because you don't have range checking, and passing the array around will lose any information about its size (array to pointer conversion). You should use std::array in that case, which wraps a C++ array in a small class and provides a size function and iterators to iterate over it.

Now, std::vector vs. native C++ arrays (taken from the internet):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Note: If you allocate arrays with new and allocate non-class objects (like plain int) or classes without a user defined constructor and you don't want to have your elements initialized initially, using new-allocated arrays can have performance advantages because std::vector initializes all elements to default values (0 for int, for example) on construction (credits to @bernie for reminding me).

Why Is a C++ Vector Called a Vector