Arrays & Vectors–Arrays–STRUCTURED PROGRAMMING Course Notes

Arrays & Vectors

Intro

• Data Structures are collections of related 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’re defined are entered & 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 index of the particular element in square brackets ‘[]’.
• The first element in every array has index zero and is sometimes called the zeroth element.
• An index must be an integer or integer expression (using any integral type).
• The brackets used to enclose the index are an operator with the same precedence as parenthesis.

Declaring Arrays

• Arrays occupy space in memory. You specify 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.

Examples Using Arrays

• The elements of an array can be initialized in the array declaration by following the array name with an equals sign and an initializer list–a 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 & initializer list are specified in the array declaration, the number of initializer must be less than or equal to the array size (number of elements).
• Constants must be initialized with a constant expression when they’re declared and cannot be modified thereafter. Constants can be placed anywhere a constant expression is expected.
• C++ has no array bounds checking. We, ourselves, should ensure that all array references remain within the bounds of the array.
• 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 you, each element of that array is initialized to zero by the compiler when the array is created.

Passing Arrays to Functions

• To pass an array argument to a function, specify the name of the array without any brackets.
  • Ex:
    • array declaration:
      • int hourlyTemperatures[24];
    • then the function call is:
      • modifyArray(hourlyTemperatures, 24);
• 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 reference–the called functions can modify the element values in the caller’s 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. *Remember that an array is a consecutive group of memory locations (of the same type!)!
• Individual array elements are passed by value exactly as simple variables are. Such simple single pieces of data are called ‘scalars‘ or ‘scalar quantities‘. (Remember, entire arrays are passed by reference!)
• To receive an array argument, the 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.
  • Ex: void modifyArray ( int b[], int arraySize )
• 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, & any attempt to modify an element of the array in the function body results in a compilation error.
• Note: Following the example of the “principle of least privilege“, functions should not be given the capability to modify an array unless it’s absolutely necessary!
• Class variables (‘static‘ data members) are shared by all objects of the class in which the variables are declared.
• A ‘static‘ data member can be accessed within the class definition and the member-function definitions like any other data member.
• A ‘public static‘ data member can also be accessed outside of the class, even when no objects of the class exist, using the class name followed by the binary scope resolution operator ( :: ) and the name of the data member.

Searching Arrays with Linear Search

• The process of finding a particular element of an array is called ‘searching‘.
• The ‘linear search‘ compares each array element with a search key. Because the array is not in any particular order, it’s just as likely that the value will be found in the first element as the last. On average, a program must compare the search key with half the array elements. 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 or for unsorted arrays (i.e., arrays whose elements are in no particular order). For large arrays, linear searching is inefficient. If the array is sorted (e.g., its elements are in ascending order), we can use the high-speed binary search technique.

Sorting Arrays with Insertion Sort

• Sorting data (i.e.-placing data into some particular order, such as ascending or descending) is one of the most important computing applications!!!
• Insertion Sort–the first iteration of this algorithm takes the second element &, if it’s less than the first element, swaps it with the first element (i.e., the program inserts the 2nd element in front of the 1st element). The second iteration looks at the 3rd element & inserts it into the correct position with respects to the first two elements, so all three elements are now in order. At the ‘i’^th 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’s inefficient compared to more sophisticated sorting algorithms.)

Multi-Dimensional Arrays

Multi-dimensional Arrays with two dimensions are often used to represent tables of values consisting of information arranged in rows & columns.

• Arrays that require two subscripts to identify a particular element are called two-dimensional arrays. An array with ‘m‘ rows & ‘n‘ columns is called an ‘m-by-n‘ array.

• Ex:

3-by-4 array	Column 0	Column 1	Column 2	Column 3
Row 0	a[0][0]	a[0][1]	a[0][2]	a[0][3]
Row 1	a[1][0]	a[1][1]	a[1][2]	a[1][3]
Row 2	a[2][0]	a[2][1]	a[2][2]	a[2][3]
Key:	‘a’ = array name	the 1st index # is the ‘row subscript’	the 2nd index is the ‘column subscript’.

Introduction to C++ Standard Library Class Template ‘Vector’

• Class template ‘vector‘ represents a more robust alternative to arrays, featuring many additional 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’s 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.
• 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.
• Note: As we’ll soon learn, pointer variables (“pointers“) contain memory addresses as their values. Array names are simply pointers to where the arrays begin in memory, and, of course, two arrays will always be at different memory locations!!