Data structures are collections of related data items. Arrays are data structures consisting of related data items of the same type. Arrays are "static" entities in that they remain the same size throughout program execution. (They may, of course, be of automatic storage class and hence be created and destroyed each time the blocks in which they are defined are entered and exited.)
An array is a consecutive group of memory locations that share the same type.
To refer to a particular location or element in an array, we specify the name of the array and the position number of the particular element in the array.
A program refers to any one of an array's elements by giving the name of the array followed by the position number of the particular element in square brackets (). The position number is more formally called a subscript or index (this number specifies the number of elements from the beginning of the array).
The first element in every array has subscript zero and is sometimes called the zeroth element.
A subscript must be an integer or integer expression (using any integral type).
It is important to note the difference between the "seventh element of the array" and "array element 7." Array subscripts begin at 0, so the "seventh element of the array" has a subscript of 6, while "array element 7" has a subscript of 7 and is actually the eighth element of the array. This distinction frequently is a source of off-by-one errors.
The brackets used to enclose the subscript of an array are an operator in C++. Brackets have the same level of precedence as parentheses.
Arrays occupy space in memory. The programmer specifies the type of each element and the number of elements required by an array as follows:
type arrayName[ arraySize ];
and the compiler reserves the appropriate amount of memory.
Arrays can be declared to contain any data type. For example, an array of type char can be used to store a character string.
The elements of an array can be initialized in the array declaration by following the array name with an equals sign and an initializer lista comma-separated list (enclosed in braces) of constant initializers. When initializing an array with an initializer list, if there are fewer initializers than elements in the array, the remaining elements are initialized to zero.
If the array size is omitted from a declaration with an initializer list, the compiler determines the number of elements in the array by counting the number of elements in the initializer list.
If the array size and an initializer list are specified in an array declaration, the number of initializers must be less than or equal to the array size. Providing more initializers in an array initializer list than there are elements in the array is a compilation error.
Constants must be initialized with a constant expression when they are declared and cannot be modified thereafter. Constants can be placed anywhere a constant expression is expected.
C++ has no array bounds checking to prevent the computer from referring to an element that does not exist. Thus, an executing program can "walk off" either end of an array without warning. Programmers should ensure that all array references remain within the bounds of the array.
A character array can be initialized using a string literal. The size of a character array is determined by the compiler based on the length of the string plus a special string-termination character called the null character (represented by the character constant '\0').
All strings represented by character arrays end with the null character. A character array representing a string should always be declared large enough to hold the number of characters in the string and the terminating null character.
Character arrays also can be initialized with individual character constants in an initializer list.
Individual characters in a string can be accessed directly with array subscript notation.
A string can be input directly into a character array from the keyboard using cin and >>.
A character array representing a null-terminated string can be output with cout and <<.
A static local variable in a function definition exists for the duration of the program but is visible only in the function body.
A program initializes static local arrays when their declarations are first encountered. If a static array is not initialized explicitly by the programmer, each element of that array is initialized to zero by the compiler when the array is created.
To pass an array argument to a function, specify the name of the array without any brackets. To pass an element of an array to a function, use the subscripted name of the array element as an argument in the function call.
Arrays are passed to functions by referencethe called functions can modify the element values in the callers' original arrays. The value of the name of the array is the address in the computer's memory of the first element of the array. Because the starting address of the array is passed, the called function knows precisely where the array is stored in memory.
Individual array elements are passed by value exactly as simple variables are. Such simple single pieces of data are called scalars or scalar quantities.
To receive an array argument, a function's parameter list must specify that the function expects to receive an array. The size of the array is not required between the array brackets.
C++ provides the type qualifier const that can be used to prevent modification of array values in the caller by code in a called function. When an array parameter is preceded by the const qualifier, the elements of the array become constant in the function body, and any attempt to modify an element of the array in the function body results in a compilation error.
The linear search compares each element of an array with a search key. Because the array is not in any particular order, it is just as likely that the value will be found in the first element as the last. On average, therefore, a program must compare the search key with half the elements of the array. To determine that a value is not in the array, the program must compare the search key to every element in the array. The linear searching method works well for small arrays and is acceptable for unsorted arrays.
An array can be sorted using insertion sort. The first iteration of this algorithm takes the second element and, if it is less than the first element, swaps it with the first element (i.e., the program inserts the second element in front of the first element). The second iteration looks at the third element and inserts it into the correct position with respect to the first two elements, so all three elements are in order. At the ith iteration of this algorithm, the first i elements in the original array will be sorted. For small arrays, the insertion sort is acceptable, but for larger arrays it is inefficient compared to other more sophisticated sorting algorithms.
Multidimensional arrays with two dimensions are often used to represent tables of values consisting of information arranged in rows and columns.
Arrays that require two subscripts to identify a particular element are called two-dimensional arrays. An array with m rows and n columns is called an m -by-n array.
C++ Standard Library class template vector represents a more robust alternative to arrays featuring many capabilities that are not provided for C-style pointer-based arrays.
By default, all the elements of an integer vector object are set to 0.
A vector can be defined to store any data type using a declaration of the form
vector< type > name( size );
Member function size of class template vector returns the number of elements in the vector on which it is invoked.
The value of an element of a vector can be accessed or modified using square brackets ().
Objects of standard class template vector can be compared directly with the equality (==) and inequality (!=) operators. The assignment (=) operator can also be used with vector objects.
An unmodifiable lvalue is an expression that identifies an object in memory (such as an element in a vector), but cannot be used to modify that object. A modifiable lvalue also identifies an object in memory, but can be used to modify the object.
Standard class template vector provides bounds checking in its member function at, which "throws an exception" if its argument is an invalid subscript. By default, this causes a C++ program to terminate.