Arrays, Strings, and Aggregate Data

Introduction

Programs frequently process collections rather than isolated values. A payroll system stores salaries for many employees, a sensor application records measurements over time, and a text-processing program examines sequences of characters. Arrays, strings, enumerations, structures, unions, and type aliases provide the fundamental tools for representing such related data in C and C++.

This chapter develops both the conceptual and practical foundations required to declare, initialize, traverse, search, sort, and analyze collections. It also explains how aggregate types improve program organization and how C-style strings differ from the safer and more expressive C++ std::string class.

Learning Objectives

By the end of this chapter, you should be able to:

• declare, initialize, access, and traverse one- and multidimensional arrays;
• apply linear search, binary search, selection sort, and related operations;
• perform basic numerical data analysis using arrays;
• explain null-terminated C-style strings and use common string functions safely;
• use std::string for modern C++ text processing;
• define and apply enumerations, structures, unions, and type aliases;
• select appropriate aggregate data types for practical applications; and
• identify common errors involving bounds, initialization, ownership, and type safety.

1. Arrays as Contiguous Collections

An array is a fixed-size sequence of objects of the same type stored in contiguous memory. If an array is declared as:

int scores[5];

it contains five int elements. C and C++ use zero-based indexing, so the valid indices are 0 through 4. The expression scores[i] denotes the element at index i.

For an array with a known number of elements, the declaration can include an initializer:

int scores[5] = {72, 81, 65, 90, 88};

If fewer initializers are supplied, the remaining elements are value-initialized. For example, int a[5] = {1, 2}; produces {1, 2, 0, 0, 0}. An array may also omit its size when an initializer is present:

int primes[] = {2, 3, 5, 7, 11};

The compiler determines the size as five.

1.1 Memory and indexing

For an array a with element size s, the address of element a[i] is conceptually the base address plus i × s bytes. This explains why indexing is efficient: accessing an element requires constant time, written as O(1), when the index is known. The index must satisfy:

where a is not being used as an address here but represents the lower bound; more practically, for a zero-based array of length n, the condition is 0 ≤ i < n. Access outside this range is undefined behavior in C and C++.

The array length should therefore be preserved explicitly or computed before the array is passed to a function:

int values[] = {4, 8, 15, 16, 23, 42};
const std::size_t n = sizeof(values) / sizeof(values[0]);

This expression works only where values is actually an array, not after it has decayed to a pointer in a function parameter.

1.2 Traversal

Traversal means visiting each element, usually once. The traditional indexed loop is:

for (std::size_t i = 0; i < n; ++i) {
    std::cout << values[i] << ' ';
}

A range-based for loop is clearer when the index is unnecessary:

for (int value : values) {
    std::cout << value << ' ';
}

Use a reference when the elements must be modified:

for (int& value : values) {
    value *= 2;
}

The loop variable const int& avoids copying while preventing modification.

2. One-Dimensional Array Algorithms

2.1 Aggregation and basic analysis

A common data-analysis task is computing the sum and arithmetic mean of n observations. If the observations are x₁, x₂, …, xₙ, the sum is:

and the arithmetic mean is:

Here, n must be positive, and all observations should represent comparable quantities in the same units. The mean has the same unit as each observation.

double sum = 0.0;
for (double x : readings) {
    sum += x;
}
double mean = sum / readings.size();

For an array rather than a container, the size must be supplied separately. Other useful operations include minimum, maximum, counting values satisfying a condition, and computing a frequency table.

A single-pass minimum algorithm is:

int minimum = values[0];
for (std::size_t i = 1; i < n; ++i) {
    if (values[i] < minimum) {
        minimum = values[i];
    }
}

This requires n > 0. A frequent error is initializing minimum to zero, which fails when all valid values are positive or when all values are negative.

2.2 Linear search

Linear search examines elements sequentially until the target is found or the collection ends.

int findIndex(const int a[], std::size_t n, int target) {
    for (std::size_t i = 0; i < n; ++i) {
        if (a[i] == target) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

The algorithm takes at most n comparisons and has worst-case time complexity O(n). It requires no ordering and is suitable for small or unsorted collections. The value -1 conventionally indicates failure, but an unsigned index type should not be used if -1 is required as a sentinel.

2.3 Binary search

Binary search is faster for a sorted array. It repeatedly compares the target with the middle element and discards half of the remaining interval.

int binarySearch(const int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

The precondition is that a[0] through a[n−1] are sorted in ascending order. Its worst-case time complexity is O(log n), while its space complexity is O(1) for the iterative version. Binary search must not be applied to unsorted data merely because it is theoretically faster.

2.4 Sorting

Sorting rearranges elements according to an ordering relation. Selection sort repeatedly selects the smallest remaining element and places it at the next position.

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int smallest = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        std::swap(a[i], a[smallest]);
    }
}

Selection sort performs O(n²) comparisons in the best, average, and worst cases. It uses constant auxiliary space and is easy to understand, but production software normally uses the standard library:

std::sort(values.begin(), values.end());

The standard algorithm is generally much more efficient and has average complexity O(n log n) for random-access ranges. The exact implementation is library-dependent, so programmers should rely on the documented complexity rather than assume a particular sorting method.

3. Multidimensional Arrays

A two-dimensional array represents data arranged in rows and columns:

int marks[3][4] = {
    {70, 82, 91, 76},
    {65, 88, 79, 84},
    {90, 73, 86, 95}
};

The first index identifies a row and the second identifies a column. Traversal normally uses nested loops:

for (int row = 0; row < 3; ++row) {
    for (int column = 0; column < 4; ++column) {
        std::cout << marks[row][column] << ' ';
    }
    std::cout << '\n';
}

C++ stores the elements in row-major order: all elements of row 0 precede those of row 1. This representation makes row-wise traversal cache-friendly. A matrix with r rows and c columns contains r × c elements and traversal requires O(rc) time.

A function parameter must preserve the column dimension for built-in multidimensional arrays:

void printMatrix(const int matrix[][4], int rows) {
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < 4; ++j) {
            std::cout << matrix[i][j] << ' ';
        }
        std::cout << '\n';
    }
}

For flexible dimensions, std::vector<std::vector<int>> or a one-dimensional vector with an indexing formula is often preferable. For a row-major matrix with c columns, element (i, j) is stored at linear position i × c + j, provided 0 ≤ i < r and 0 ≤ j < c.

4. C-Style Strings

A C-style string is an array of characters terminated by the null character \0. The declaration:

char word[] = "Hello";

creates six characters: H, e, l, l, o, and \0. The null terminator is not the same as the character '0'.

Because string functions search for the terminator, a character array must have sufficient capacity:

char name[6] = "Alice";

A declaration such as char name[5] = "Alice"; cannot store the terminator and is ill-formed in standard C++.

The header <cstring> provides functions such as std::strlen, std::strcmp, std::strcpy, and std::strcat. Functions that copy or concatenate strings require particular care because they do not automatically prevent buffer overflow in all uses. The destination must have enough space, and the source must be properly terminated.

char first[20] = "Ada";
char second[] = " Lovelace";
std::strcat(first, second);

After concatenation, first contains Ada Lovelace, including a terminating null character. Input with std::cin >> name stops at whitespace and can overflow an inadequately sized character array. If C-style input is unavoidable, use bounded operations and validate lengths.

5. std::string: Modern C++ Text

The C++ std::string class, declared in <string>, manages a sequence of characters and automatically handles storage and length.

std::string name = "Ada Lovelace";
std::cout << name.length();

Useful operations include concatenation with +, comparison with relational operators, indexed access using [] or bounds-checked at(), substring extraction, and searching:

std::string text = "programming";
std::size_t position = text.find("gram");
if (position != std::string::npos) {
    std::cout << "Found at " << position;
}

std::string::npos is a special value indicating that a search failed. at() throws an exception for an invalid index, whereas operator[] does not perform bounds checking. A string's size() and length() return the number of characters, excluding any internal implementation details; they are equivalent for std::string.

Use std::getline when spaces should be retained:

std::string sentence;
std::getline(std::cin, sentence);

After formatted extraction such as std::cin >> number, a pending newline may need to be consumed before calling getline. Modern C++ should normally use std::string rather than raw character arrays unless interoperability with a C API, embedded constraint, or low-level memory requirement justifies C-style strings.

6. Enumerations

An enumeration defines a type with a restricted set of named values. An unscoped enumeration is written:

enum Day { Monday, Tuesday, Wednesday, Thursday, Friday };
Day today = Wednesday;

By default, enumerators receive successive integer values beginning at zero. Explicit values may be assigned:

enum class Status { Pending = 1, Approved = 2, Rejected = 3 };

A scoped enumeration (enum class) does not implicitly convert to an integer and avoids name collisions. Its values are referred to as Status::Approved. Scoped enumerations are generally safer because they provide stronger type checking.

Enumerations are useful when a variable should represent one choice from a defined set, such as status, direction, or category. They should not be used as an unrestricted replacement for arbitrary integers.

7. Structures and Aggregate Records

A structure groups related values, potentially of different types, into one object:

struct Student {
    int id;
    std::string name;
    double average;
};

Student s{101, "Mira", 84.5};

Members are accessed using the dot operator. A pointer to a structure uses ->:

Student* p = &s;
std::cout << p->name;

Structures model records. An array of structures represents a collection of records:

std::vector<Student> classList = {
    {101, "Mira", 84.5},
    {102, "Jon", 78.0}
};

Such data can be sorted with a comparison function or lambda:

std::sort(classList.begin(), classList.end(),
          [](const Student& a, const Student& b) {
              return a.average > b.average;
          });

The comparison establishes descending order by average. In professional applications, a structure should maintain meaningful invariants—for example, an average should be within its permitted range—and input validation should occur before records are stored.

8. Unions

A union stores different members in the same memory location. Only one member should be treated as active at a time:

union Measurement {
    int count;
    double value;
    char code;
};

The size of a union is sufficient for its largest member, subject to alignment requirements. This can save memory when a record may contain one of several alternative representations. However, unions can be error-prone because the program must track which member is active. A tagged union combines a discriminating enumeration with a union:

struct Token {
    enum class Kind { Integer, Real } kind;
    union {
        int integerValue;
        double realValue;
    } data;
};

In modern C++, std::variant is usually safer because it records the active alternative and provides checked access:

std::variant<int, double> value = 3.14;

Unions are appropriate for low-level representations, memory-constrained systems, and interoperability, but ordinary business records are usually clearer as structures or classes.

9. Type Aliases

A type alias gives a type a meaningful alternative name:

using StudentScores = std::vector<int>;
StudentScores scores;

Aliases improve readability and make implementation changes easier. They do not create a distinct new type; StudentScores remains a std::vector<int>.

The older typedef syntax is also valid:

typedef unsigned long Identifier;

The using form is generally preferred, especially for templates:

using Matrix = std::vector<std::vector<double>>;

An alias should communicate a domain concept rather than conceal an already obvious type without purpose.

10. Worked Application: Student Performance Analysis

Consider an illustrative university application that records four assessment scores for each student and reports each student's average and the highest-performing student.

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

struct Student {
    int id;
    std::string name;
    double scores[4];
    double average() const {
        double total = 0.0;
        for (double score : scores) total += score;
        return total / 4.0;
    }
};

int main() {
    std::vector<Student> students = {
        {101, "Mira", {78, 85, 91, 88}},
        {102, "Jon",  {84, 76, 80, 82}},
        {103, "Lea",  {92, 89, 94, 90}}
    };

    auto best = std::max_element(
        students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.average() < b.average();
        });

    for (const Student& student : students) {
        std::cout << student.name << ": "
                  << std::fixed << std::setprecision(2)
                  << student.average() << '\n';
    }
    std::cout << "Highest: " << best->name << '\n';
}

Mira's total is 342, so her average is 85.50. Jon's total is 322, giving 80.50. Lea's total is 365, giving 91.25. Therefore, Lea has the highest average. The application combines a structure, an array, traversal, aggregation, a standard-library algorithm, and a comparison lambda.

Analysis and design lessons

The fixed four-element array is suitable because the number of assessments is known and constant. If assessments could be added dynamically, a std::vector<double> would be more appropriate. The program computes each average more than once during the search and output; for a small class this is insignificant, but a large system could store the computed result or calculate all averages once. Real systems should also validate that scores are within the permitted range, protect student information, and define how missing assessments are handled.

11. Common Errors and Best Practices

1. Off-by-one errors: Use i < n, not i <= n, for zero-based arrays.
2. Uninitialized values: Initialize arrays and variables before reading from them.
3. Invalid dimensions: Ensure every multidimensional index is within its corresponding bound.
4. Array decay: When passed to a function, a built-in array commonly becomes a pointer; pass its length separately or use a container.
5. Buffer overflow: Prefer std::string and standard containers; validate C-style string capacity.
6. Empty data: Do not compute a mean or access element zero when the collection may be empty.
7. Unsorted binary search: Sort first and preserve the ordering invariant.
8. Incorrect union use: Track the active member or use std::variant.
9. Unnecessary copying: Use const references when traversing large structures without modification.
10. Unclear ownership: Prefer RAII-based containers such as std::vector and std::string over manually allocated arrays.

12. Contemporary C++ Practice

Although built-in arrays remain important for understanding memory and interfacing with low-level systems, modern C++ favors std::array for fixed-size collections and std::vector for dynamically sized collections. These types expose their size, integrate with standard algorithms, and reduce memory-management errors. The C++ standard library also provides ranges, views, iterators, and algorithms that support expressive collection processing.

Artificial intelligence and data-intensive software depend heavily on aggregate data. Training records, feature vectors, token sequences, and matrices are all organized collections. Nevertheless, the same principles remain essential: define valid dimensions, preserve type meaning, check boundaries, validate input, and document assumptions. A library or AI framework does not remove the need for correct data representation.

Chapter Summary

Arrays provide contiguous, indexed storage for objects of one type. Their zero-based indexing makes direct access efficient, but every index must be within bounds. Traversal supports aggregation, searching, sorting, and basic analysis. Linear search works on unsorted data with O(n) worst-case time; binary search requires sorted data and operates in O(log n) worst-case time. Selection sort is simple but quadratic, while standard-library sorting is normally preferred.

Two-dimensional arrays represent rows and columns and are traversed with nested loops. C-style strings are null-terminated character arrays and require careful capacity management. std::string provides safer, flexible text processing and should be the default choice in modern C++. Enumerations represent restricted choices, structures group heterogeneous fields into records, unions share storage among alternatives, and type aliases improve readability without creating new types. Robust programs combine these tools with validation, clear invariants, standard containers, and appropriate algorithms.

Key Terms

Array: A fixed-size contiguous collection of objects of one type.

Index: The position used to access an array element.

Traversal: Systematic visitation of collection elements.

Linear search: Sequential search through a collection.

Binary search: Search that repeatedly halves a sorted search interval.

Sorting: Rearranging elements according to an ordering relation.

Row-major order: Storage order in which complete rows precede later rows.

C-style string: A character array terminated by \0.

Null character: The character \0 marking the end of a C-style string.

std::string: The standard C++ dynamically managed string type.

Enumeration: A type containing a defined set of named values.

Scoped enumeration: An enum class whose values are qualified and strongly typed.

Structure: A user-defined type that groups related fields.

Union: A type whose members share the same storage.

Type alias: An alternative name for an existing type.

Sentinel: A special value used to signal a condition such as search failure.

Invariant: A condition that should remain true throughout an operation.

Undefined behavior: Program behavior for which the language imposes no requirements.

Review Questions

Short Answer Questions

1. Why are valid indices for an array of length n from 0 through n−1?
2. State the precondition that must hold before binary search is used.
3. What role does the null character play in a C-style string?
4. How does an enum class differ from an unscoped enumeration?
5. Why is std::string generally safer than a raw character array?

Long Answer Questions

1. Explain array storage, indexing, traversal, and the principal causes of out-of-bounds access.
2. Compare linear search, binary search, selection sort, and standard-library sorting in terms of assumptions and complexity.
3. Explain the representation and traversal of a two-dimensional array, including row-major order.
4. Compare structures and unions, and discuss when std::variant may be preferable to a union.
5. Develop a design for storing and analyzing student records using structures and an appropriate collection type.

Analytical / Application Questions

1. A temperature-monitoring program receives 24 hourly readings. Design an algorithm to compute the minimum, maximum, and mean while handling the possibility of no readings.
2. A library stores 50,000 sorted book identification numbers. Decide whether linear or binary search is more appropriate and justify the decision, including the cost of maintaining sorted order.
3. A survey record may contain either an integer response or a decimal measurement. Propose a safe C++ representation and explain how the program can determine which alternative is active.

Multiple Choice Questions with Answers

Question 1

What is the valid index range for an array containing n elements?

A. 1 through n

B. 0 through n−1

C. 0 through n

D. 1 through n−1

Correct Answer: B. 0 through n−1

Question 2

Which condition is required for binary search?

A. The array must contain only positive values

B. The array must have an even number of elements

C. The array must be sorted according to the search ordering

D. The array must contain unique values

Correct Answer: C. The array must be sorted according to the search ordering

Question 3

What terminates a C-style string?

A. The character '0'

B. A newline character

C. The null character \0

D. The space character

Correct Answer: C. The null character \0

Question 4

What is the worst-case time complexity of linear search over n elements?

A. O(1)

B. O(log n)

C. O(n)

D. O(n²)

Correct Answer: C. O(n)

Question 5

Which C++ type is generally preferred for ordinary text processing?

A. std::string

B. union

C. enum class

D. double

Correct Answer: A. std::string

Question 6

For the scores 70, 80, 90, and 100, what is the arithmetic mean?

A. 80

B. 85

C. 90

D. 95

Correct Answer: B. 85

Question 7

Which feature distinguishes a union from a structure?

A. A union cannot contain numeric fields

B. All union members occupy separate storage

C. Union members share the same storage

D. A union must contain only one member

Correct Answer: C. Union members share the same storage

Question 8

Which syntax accesses the member name through a pointer p to a structure?

A. p.name

B. p::name

C. p->name

D. p[name]

Correct Answer: C. p->name

Question 9

What does a type alias do?

A. Creates an alternative name for an existing type

B. Automatically allocates memory

C. Converts every value to a string

D. Sorts a collection

Correct Answer: A. Creates an alternative name for an existing type

Question 10

What is the usual worst-case complexity of iterative binary search?

A. O(n²)

B. O(n)

C. O(log n)

D. O(2ⁿ)

Correct Answer: C. O(log n)