How do I use arrays in C++?
itemprop="text">
C++ inherited arrays from C where they
are used virtually everywhere. C++ provides abstractions that are easier to use and less
error-prone (std::vector since C++98 and href="http://en.cppreference.com/w/cpp/container/array"
rel="noreferrer">std::array since
C++11),
so the need for arrays does not arise quite as often as it does in C. However, when you
read legacy code or interact with a library written in C, you should have a firm grasp
on how arrays work.
This FAQ is split
into five parts:
- href="https://stackoverflow.com/questions/4810668/">arrays on the type level and
accessing elements
- href="https://stackoverflow.com/questions/4984228/">array creation and
initialization
- href="https://stackoverflow.com/questions/4810672/">assignment and parameter
passing
- href="https://stackoverflow.com/questions/4810676/">multidimensional arrays and
arrays of pointers
- href="https://stackoverflow.com/questions/4810664/how-do-i-use-arrays-in-c/7439261#7439261">common
pitfalls when using
arrays
If
you feel something important is missing in this FAQ, write an answer and link it here as
an additional part.
In the following text,
"array" means "C array", not the class template std::array.
Basic knowledge of the C declarator syntax is assumed. Note that the manual usage of
new and delete as demonstrated below
is extremely dangerous in the face of exceptions, but that is the topic of href="https://stackoverflow.com/questions/712639/">another
FAQ.
(Note:
This is meant to be an entry to href="https://stackoverflow.com/questions/tagged/c++-faq"> C++ FAQ. If you
want to critique the idea of providing an FAQ in this form, then href="https://meta.stackexchange.com/questions/68647/setting-up-a-faq-for-the-c-tag">the
posting on meta that started all this would be the place to do that. Answers
to that question are monitored in the href="http://chat.stackoverflow.com/rooms/10/c-lounge">C++ chatroom, where
the FAQ idea started out in the first place, so your answer is very likely to get read
by those who came up with the
idea.)
class="post-text" itemprop="text">
An array
type is denoted as T[n] where T is the
element type and n is a positive
size, the number of elements in the array. The array type is a
product type of the element type and the size. If one or both of those ingredients
differ, you get a distinct
type:
#include
static_assert(!std::is_same float[8]>::value, "distinct element
type");
static_assert(!std::is_same::value, "distinct
size");
Note that the
size is part of the type, that is, array types of different size are incompatible types
that have absolutely nothing to do with each other.
sizeof(T[n]) is equivalent to n *
sizeof(T).
Array-to-pointer
decay
The only "connection" between
T[n] and T[m] is that both types can
implicitly be converted to T*, and the
result of this conversion is a pointer to the first element of the array. That is,
anywhere a T* is required, you can provide a
T[n], and the compiler will silently provide that
pointer:
+---+---+---+---+---+---+---+---+
the_actual_array: | | | | | | | | |
int[8]
+---+---+---+---+---+---+---+---+
^
|
|
|
| pointer_to_the_first_element
int*
This conversion
is known as "array-to-pointer decay", and it is a major source of confusion. The size of
the array is lost in this process, since it is no longer part of the type
(T*). Pro: Forgetting the size of an array on the type level
allows a pointer to point to the first element of an array of any
size. Con: Given a pointer to the first (or any other) element of an array, there is no
way to detect how large that array is or where exactly the pointer points to relative to
the bounds of the array. href="https://stackoverflow.com/questions/4261074/">Pointers are extremely
stupid.
Arrays are not
pointers
The compiler will silently generate a
pointer to the first element of an array whenever it is deemed useful, that is, whenever
an operation would fail on an array but succeed on a pointer. This conversion from array
to pointer is trivial, since the resulting pointer value is simply
the address of the array. Note that the pointer is not stored as
part of the array itself (or anywhere else in memory). An array is not a
pointer.
static_assert(!std::is_same int*>::value, "an array is not a
pointer");
One
important context in which an array does not decay into a pointer
to its first element is when the & operator is applied to
it. In that case, the & operator yields a pointer to the
entire array, not just a pointer to its first element. Although in
that case the values (the addresses) are the same, a pointer to the
first element of an array and a pointer to the entire array are completely distinct
types:
static_assert(!std::is_same int(*)[8]>::value, "distinct element
type");
The following
ASCII art explains this
distinction:
+-----------------------------------+
| +---+---+---+---+---+---+---+---+
|
+---> | | | | | | | | | | | int[8]
| |
+---+---+---+---+---+---+---+---+ |
|
+---^-------------------------------+
| |
| |
|
|
| | pointer_to_the_first_element int*
|
|
pointer_to_the_entire_array
int(*)[8]
Note how the
pointer to the first element only points to a single integer (depicted as a small box),
whereas the pointer to the entire array points to an array of 8 integers (depicted as a
large box).
The same situation arises in classes
and is maybe more obvious. A pointer to an object and a pointer to its first data member
have the same value (the same address), yet they are completely
distinct types.
If you are unfamiliar with the C
declarator syntax, the parenthesis in the type int(*)[8] are
essential:
int(*)[8]
is a pointer to an array of 8
integers.
int*[8] is an array of
8 pointers, each element of type
int*.
C++
provides two syntactic variations to access individual elements of an
array.
Neither of them is superior to the other, and you should familiarize
yourself with both.
Pointer
arithmetic
Given a pointer
p to the first element of an array, the expression
p+i yields a pointer to the i-th element of the array. By
dereferencing that pointer afterwards, one can access individual
elements:
std::cout <<
*(x+3) << ", " << *(x+7) <<
std::endl;
If
x denotes an array, then array-to-pointer
decay will kick in, because adding an array and an integer is meaningless (there is no
plus operation on arrays), but adding a pointer and an integer makes
sense:
+---+---+---+---+---+---+---+---+
x: | | | | | | | | |
int[8]
+---+---+---+---+---+---+---+---+
^ ^ ^
| |
|
| | |
| | |
x+0 | x+3 | x+7 |
int*
(Note that the
implicitly generated pointer has no name, so I wrote x+0 in
order to identify it.)
If, on the
other hand, x denotes a pointer to the
first (or any other) element of an array, then array-to-pointer decay is not necessary,
because the pointer on which i is going to be added already
exists:
+---+---+---+---+---+---+---+---+
| | | | | | | | | int[8]
+---+---+---+---+---+---+---+---+
^ ^ ^
| | |
| |
|
+-|-+ | |
x: | | | x+3 | x+7 | int*
+---+
Note that in the
depicted case, x is a pointer variable
(discernible by the small box next to x), but it could just as
well be the result of a function returning a pointer (or any other expression of type
T*).
Indexing
operator
Since the syntax
*(x+i) is a bit clumsy, C++ provides the alternative syntax
x[i]:
std::cout
<< x[3] << ", " << x[7] <<
std::endl;
Due to the
fact that addition is commutative, the following code does exactly the
same:
std::cout << 3[x]
<< ", " << 7[x] <<
std::endl;
The
definition of the indexing operator leads to the following interesting
equivalence:
&x[i]
== &*(x+i) ==
x+i
However,
&x[0] is generally not equivalent to
x. The former is a pointer, the latter an array. Only when the
context triggers array-to-pointer decay can x and
&x[0] be used interchangeably. For
example:
T* p = &array[0]; //
rewritten as &*(array+0), decay happens due to the addition
T* q = array;
// decay happens due to the
assignment
On the
first line, the compiler detects an assignment from a pointer to a pointer, which
trivially succeeds. On the second line, it detects an assignment from an
array to a pointer. Since this is meaningless (but
pointer to pointer assignment makes sense), array-to-pointer decay
kicks in as
usual.
Ranges
An
array of type T[n] has n elements,
indexed from 0 to n-1; there is no
element n. And yet, to support half-open ranges (where the
beginning is inclusive and the end is
exclusive), C++ allows the computation of a pointer to the
(non-existent) n-th element, but it is illegal to dereference that
pointer:
+---+---+---+---+---+---+---+---+....
x: | | | | | | | | | . int[8]
+---+---+---+---+---+---+---+---+....
^ ^
|
|
| |
| |
x+0 | x+8 |
int*
For example, if
you want to sort an array, both of the following would work equally
well:
std::sort(x + 0, x +
n);
std::sort(&x[0], &x[0] +
n);
Note
that it is illegal to provide &x[n] as the second argument
since this is equivalent to &*(x+n), and the sub-expression
*(x+n) technically invokes href="https://stackoverflow.com/questions/3144904/">undefined behavior in
C++ (but not in C99).
Also note that you could
simply provide x as the first argument. That is a little too
terse for my taste, and it also makes template argument deduction a bit harder for the
compiler, because in that case the first argument is an array but the second argument is
a pointer. (Again, array-to-pointer decay kicks in.)
No comments:
Post a Comment