This chapter is from the book
This chapter is from the book
This chapter is from the book
18.6 Arrays
For a while, we have used array to refer to a sequence of objects allocated on the free store. We can also allocate arrays elsewhere as named variables. In fact, they are common
- As global variables (but global variables are most often a bad idea)
- As local variables (but arrays have serious limitations there)
- As function arguments (but an array doesn’t know its own size)
- As class members (but member arrays can be hard to initialize)
Now, you might have detected that we have a not-so-subtle bias in favor of vectors over arrays. Use std::vector where you have a choice — and you have a choice in most contexts. However, arrays existed long before vectors and are roughly equivalent to what is offered in other languages (notably C), so you must know arrays, and know them well, to be able to cope with older code and with code written by people who don’t appreciate the advantages of vector.
So, what is an array? How do we define an array? How do we use an array? An array is a homogeneous sequence of objects allocated in contiguous memory; that is, all elements of an array have the same type and there are no gaps between the objects of the sequence. The elements of an array are numbered from 0 upward. In a declaration, an array is indicated by “square brackets”:
const int max = 100;
int gai[max]; // a global array (of 100 ints); “lives forever”
void f(int n)
{
char lac[20]; // local array; “lives” until the end of scope
int lai[60];
double lad[n]; // error: array size not a constant
// . . .
}
Note the limitation: the number of elements of a named array must be known at compile time. If you want the number of elements to be a variable, you must put it on the free store and access it through a pointer. That’s what vector does with its array of elements.
Just like the arrays on the free store, we access named arrays using the subscript and dereference operators ([ ] and *). For example:
void f2()
{
char lac[20]; // local array; “lives” until the end of scope
lac[7] = 'a';
*lac = 'b'; // equivalent to lac[0]='b'
lac[–2] = 'b'; // huh?
lac[200] = 'c'; // huh?
}
This function compiles, but we know that “compiles” doesn’t mean “works correctly.” The use of [ ] is obvious, but there is no range checking, so f2() compiles, and the result of writing to lac[–2] and lac[200] is (as for all out-of-range access) usually disastrous. Don’t do it. Arrays do not range check. Again, we are dealing directly with physical memory here; don’t expect “system support.”
But couldn’t the compiler see that lac has just 20 elements so that lac[200] is an error? A compiler could, but as far as we know no production compiler does. The problem is that keeping track of array bounds at compile time is impossible in general, and catching errors in the simplest cases (like the one above) only is not very helpful.
18.6.1 Pointers to array elements
A pointer can point to an element of an array. Consider:
double ad[10]; double* p = &ad[5]; // point to ad[5]
We now have a pointer p to the double known as ad[5]:
)
We can subscript and dereference that pointer:
*p =7; p[2] = 6; p[–3] = 9;
We get
)
That is, we can subscript the pointer with both positive and negative numbers. As long as the resulting element is in range, all is well. However, access outside the range of the array pointed into is illegal (as with free-store-allocated arrays; see §17.4.3). Typically, access outside an array is not detected by the compiler and (sooner or later) is disastrous.
Once a pointer points into an array, addition and subscripting can be used to make it point to another element of the array. For example:
p += 2; // move p 2 elements to the right
We get
)
And
p –= 5; // move p 5 elements to the left
We get
)
Using +, –, +=, and –= to move pointers around is called pointer arithmetic. Obviously, if we do that, we have to take great care to ensure that the result is not a pointer to memory outside the array:
p += 1000; // insane: p points into an array with just 10 elements
double d = *p; // illegal: probably a bad value
// (definitely an unpredictable value)
*p = 12.34; // illegal: probably scrambles some unknown data
Unfortunately, not all bad bugs involving pointer arithmetic are that easy to spot. The best policy is usually simply to avoid pointer arithmetic.
The most common use of pointer arithmetic is incrementing a pointer (using ++) to point to the next element and decrementing a pointer (using ––) to point to the previous element. For example, we could print the value of ad’s elements like this:
for (double* p = &ad[0]; p<&ad[10]; ++p) cout << *p << '\n';
Or backward:
for (double* p = &ad[9]; p>=&ad[0]; ––p) cout << *p << '\n';
This use of pointer arithmetic is not uncommon. However, we find the last (“backward”) example quite easy to get wrong. Why &ad[9] and not &ad[10]? Why >= and not >? These examples could equally well (and equally efficiently) be done using subscripting. Such examples could be done equally well using subscripting into a vector, which is more easily range checked.
Note that most real-world uses of pointer arithmetic involve a pointer passed as a function argument. In that case, the compiler doesn’t have a clue how many elements are in the array pointed into: you are on your own. That is a situation we prefer to stay away from whenever we can.
Why does C++ have (allow) pointer arithmetic at all? It can be such a bother and doesn’t provide anything new once we have subscripting. For example:
double* p1 = &ad[0]; double* p2 = p1+7; double* p3 = &p1[7]; if (p2 != p3) cout << "impossible!\n";
Mainly, the reason is historical. These rules were crafted for C decades ago and can’t be removed without breaking a lot of code. Partly, there can be some convenience gained by using pointer arithmetic in some important low-level applications, such as memory managers.
18.6.2 Pointers and arrays
The name of an array refers to all the elements of the array. Consider:
char ch[100];
The size of ch, sizeof(ch), is 100. However, the name of an array turns into (“decays to”) a pointer with the slightest excuse. For example:
char* p = ch;
Here p is initialized to &ch[0] and sizeof(p) is something like 4 (not 100).
This can be useful. For example, consider a function strlen() that counts the number of characters in a zero-terminated array of characters:
int strlen(const char* p) // similar to the standard library strlen()
{
int count = 0;
while (*p) { ++count; ++p; }
return count;
}
We can now call this with strlen(ch) as well as strlen(&ch[0]). You might point out that this is a very minor notational advantage, and we’d have to agree.
One reason for having array names convert to pointers is to avoid accidentally passing large amounts of data by value. Consider:
int strlen(const char a[]) // similar to the standard library strlen()
{
int count = 0;
while (a[count]) { ++count; }
return count;
}
char lots [100000];
void f()
{
int nchar = strlen(lots);
// . . .
}
Naively (and quite reasonably), you might expect this call to copy the 100,000 characters specified as the argument to strlen(), but that’s not what happens. Instead, the argument declaration char p[] is considered equivalent to char* p, and the call strlen(lots) is considered equivalent to strlen(&lots[0]). This saves you from an expensive copy operation, but it should surprise you. Why should it surprise you? Because in every other case, when you pass an object and don’t explicitly declare an argument to be passed by reference (§8.5.3–6), that object is copied.
Note that the pointer you get from treating the name of an array as a pointer to its first element is a value and not a variable, so you cannot assign to it:
char ac[10]; ac = new char [20]; // error: no assignment to array name &ac[0] = new char [20]; // error: no assignment to pointer value
Finally! A problem that the compiler will catch!
As a consequence of this implicit array-name-to-pointer conversion, you can’t even copy arrays using assignment:
int x[100]; int y[100]; // . . . x = y; // error int z[100] = y; // error
This is consistent, but often a bother. If you need to copy an array, you must write some more elaborate code to do so. For example:
for (int i=0; i<100; ++i) x[i]=y[i]; // copy 100 ints memcpy(x,y,100*sizeof(int)); // copy 100*sizeof(int) bytes copy(y,y+100, x); // copy 100 ints
Note that the C language doesn’t support anything like vector, so in C, you must use arrays extensively. This implies that a lot of C++ code uses arrays (§27.1.2). In particular, C-style strings (zero-terminated arrays of characters; see §27.5) are very common.
If we want assignment, we have to use something like the standard library vector. The vector equivalent to the copying code above is
vector<int> x(100); vector<int> y(100); // . . . x = y; // copy 100 ints
18.6.3 Array initialization
An array of chars can be initialized with a string literal. For example:
char ac[] = "Beorn"; // array of 6 chars
Count those characters. There are five, but ac becomes an array of six characters because the compiler adds a terminating zero character at the end of a string literal:
A zero-terminated string is the norm in C and many systems. We call such a zero-terminated array of characters a C-style string. All string literals are C-style strings. For example:
char* pc = "Howdy"; // pc points to an array of 6 chars
Graphically:
Note that the char with the numeric value 0 is not the character '0' or any other letter or digit. The purpose of that terminating zero is to allow functions to find the end of the string. Remember: An array does not know its size. Relying on the terminating zero convention, we can write
int strlen(const char* p) // similar to the standard library strlen()
{
int n = 0;
while (p[n]) ++n;
return n;
}
Actually, we don’t have to define strlen() because it is a standard library function defined in the <string.h> header (§27.5, §B.11.3). Note that strlen() counts the characters, but not the terminating 0; that is, you need n+1 chars to store n characters in a C-style string.
Only character arrays can be initialized by literal strings, but all arrays can be initialized by a list of values of their element type. For example:
int ai[] = { 1, 2, 3, 4, 5, 6 }; // array of 6 ints
int ai2[100] = {0,1,2,3,4,5,6,7,8,9}; // the last 90 elements are initialized to 0
double ad[100] = { }; // all elements initialized to 0.0
char chars[] = {'a', 'b', 'c'}; // no terminating 0!
Note that the number of elements of ai is six (not seven) and the number of elements for chars is three (not four) — the “add a 0 at the end” rule is for literal character strings only. If an array isn’t given a size, that size is deduced from the initializer list. That’s a rather useful feature. If there are fewer initializer values than array elements (as in the definitions of ai2 and ad), the remaining elements are initialized by the element type’s default value.
18.6.4 Pointer problems
Like arrays, pointers are often overused and misused. Often, the problems people get themselves into involve both pointers and arrays, so we’ll summarize the problems here. In particular, all serious problems with pointers involve trying to access something that isn’t an object of the expected type, and many of those problems involve access outside the bounds of an array. Here we will consider
- Access through the null pointer
- Access through an uninitialized pointer
- Access off the end of an array
- Access to a deallocated object
- Access to an object that has gone out of scope
In all cases, the practical problem for the programmer is that the actual access looks perfectly innocent; it is “just” that the pointer hasn’t been given a value that makes the use valid. Worse (in the case of a write through the pointer), the problem may manifest itself only a long time later when some apparently unrelated object has been corrupted. Let’s consider examples:
Don’t access through the null pointer:
int* p = nullptr; *p = 7; // ouch!
Obviously, in real-world programs, this typically occurs when there is some code in between the initialization and the use. In particular, passing p to a function and receiving it as the result from a function are common examples. We prefer not to pass null pointers around, but if you have to, test for the null pointer before use:
int* p = fct_that_can_return_a_nullptr();
if (p == nullptr) {
// do something
}
else {
// use p
*p = 7;
}
and
void fct_that_can_receive_a_nullptr(int* p)
{
if (p == nullptr) {
// do something
}
else {
// use p
*p = 7;
}
}
Using references (§17.9.1) and using exceptions to signal errors (§5.6 and §19.5) are the main tools for avoiding null pointers.
Do initialize your pointers:
int* p; *p = 9; // ouch!
In particular, don’t forget to initialize pointers that are class members.
Don’t access nonexistent array elements:
int a[10]; int* p = &a[10]; *p = 11; // ouch! a[10] = 12; // ouch!
Be careful with the first and last elements of a loop, and try not to pass arrays around as pointers to their first elements. Instead use vectors. If you really must use an array in more than one function (passing it as an argument), then be extra careful and pass its size along.
Don’t access through a deleted pointer:
int* p = new int{7};
// . . .
delete p;
// . . .
*p = 13; // ouch!
The delete p or the code after it may have scribbled all over *p or used it for something else. Of all of these problems, we consider this one the hardest to systematically avoid. The most effective defense against this problem is not to have “naked” news that require “naked” deletes: use new and delete in constructors and destructors or use a container, such as Vector_ref (§E.4), to handle deletes.
Don’t return a pointer to a local variable:
int* f()
{
int x = 7;
// . . .
return &x;
}
// . . .
int* p = f();
// . . .
*p = 15; // ouch!
The return from f() or the code after it may have scribbled all over *p or used it for something else. The reason for that is that the local variables of a function are allocated (on the stack) upon entry to the function and deallocated again at the exit from the function. In particular, destructors are called for local variables of classes with destructors (§17.5.1). Compilers could catch most problems related to returning pointers to local variables, but few do.
Consider a logically equivalent example:
vector& ff()
{
vector x(7); // 7 elements
// . . .
return x;
} // the vector x is destroyed here
// . . .
vector& p = ff();
// . . .
p[4] = 15; // ouch!
Quite a few compilers catch this variant of the return problem.
It is common for programmers to underestimate these problems. However, many experienced programmers have been defeated by the innumerable variations and combinations of these simple array and pointer problems. The solution is not to litter your code with pointers, arrays, news, and deletes. If you do, “being careful” simply isn’t enough in realistically sized programs. Instead, rely on vectors, RAII (“Resource Acquisition Is Initialization”; see §19.5), and other systematic approaches to the management of memory and other resources.