Strings, Arrays, Collections, and Generics

Introduction

Programs rarely operate only on individual numbers. They process names, messages, files, sensor readings, records, and groups of related objects. These tasks require data structures that can store several values and operations that can manipulate those values safely and efficiently.

This chapter examines strings, arrays, collections, tuples, iterators, comprehensions, templates, and generics in C++, Java, and Python. Although the syntax differs, the central design questions are similar:

• Is the number of elements fixed or variable?
• Are duplicate values allowed?
• Must values remain ordered?
• Should elements be accessed by position or by key?
• What types of values should an operation accept?
• How should invalid input and missing values be handled?

Selecting an appropriate structure is an important professional programming skill. A technically correct program can still be difficult to maintain or inefficient if it uses an unsuitable data structure.

Learning Objectives

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

1. Create and manipulate strings in C++, Java, and Python.
2. Distinguish arrays from dynamic collections.
3. Use lists, sets, maps, tuples, and iterators appropriately.
4. Apply comprehensions in Python and understand equivalent patterns in other languages.
5. Explain templates and generics as mechanisms for reusable, type-safe code.
6. Select a data structure for a common programming problem.
7. Identify risks involving mutation, aliasing, type errors, and invalid indexes.

1. Strings as Sequences of Characters

A string is a sequence of characters used to represent text. Common operations include construction, concatenation, comparison, searching, extraction of substrings, and conversion between textual and numeric representations.

1.1 String representation

In C++, the standard library provides std::string. Java provides the String class, and Python has the built-in str type.

std::string name = "Amina";
std::string message = "Hello, " + name;

String name = "Amina";
String message = "Hello, " + name;

name = "Amina"
message = "Hello, " + name

Java strings and Python strings are immutable: an operation that appears to modify a string creates another string value. C++ std::string is mutable, although a programmer can treat it as immutable by using const.

Immutability has important consequences. It makes shared strings safer because one part of a program cannot unexpectedly alter a value held by another part. However, repeated concatenation in a loop may create many temporary objects. For substantial text construction, use std::ostringstream in C++, StringBuilder in Java, or a list followed by ''.join(...) in Python.

1.2 Common string operations

Indexes normally begin at zero. Thus, for a sequence of length n, valid indexes are 0 through n − 1. Access outside this range is an error or produces language-specific behavior. Python supports negative indexes, where s[-1] denotes the final character; C++ and Java do not use this convention.

1.3 Comparison and equality

Strings should be compared by content, not merely by object identity. In Java, a.equals(b) compares content, whereas a == b compares references. In Python, a == b compares values. In C++, a == b compares the characters in the strings.

if (username.equals("admin")) {
    System.out.println("Privileged account");
}

A robust program also considers normalization. Text may differ in case, whitespace, Unicode representation, or punctuation while appearing equivalent to a user. Case-insensitive comparison should use an intentional policy rather than casually converting characters, because international text can have language-specific rules.

1.4 String processing example

The following Python function counts words after removing leading and trailing whitespace and splitting on runs of whitespace:

def word_count(text):
    words = text.strip().split()
    return len(words)

The function assumes that a “word” is a token separated by whitespace. It does not provide full natural-language word segmentation, which would require rules for punctuation, hyphens, apostrophes, and Unicode scripts. This illustrates a general principle: a simple string operation is correct only relative to a clearly defined problem.

2. Arrays and Indexed Storage

An array stores elements of the same type in an indexed sequence. Arrays are useful when the number of elements is known or when direct positional access is important.

2.1 Fixed-size arrays

C++ supports built-in arrays and the safer library type std::array. Java arrays have a fixed length once created. Python’s built-in list is dynamic rather than a fixed-size array, although Python implementations internally use resizable array-like storage.

#include <array>
std::array<int, 4> scores = {72, 81, 69, 90};

int[] scores = {72, 81, 69, 90};

scores = [72, 81, 69, 90]

For a sequence with n elements, indexed access is generally constant time, written as O(1), because the address or reference for an element can be calculated directly. Inserting an element in the middle of an array-like sequence usually requires shifting later elements and is therefore O(n), where n is the number of elements.

These complexity statements assume ordinary contiguous or array-backed storage and exclude unusual implementation effects. They describe growth with input size, not an exact execution time.

2.2 Traversing arrays

The traditional indexed loop is useful when the index is needed:

for (int i = 0; i < scores.length; i++) {
    System.out.println(i + ": " + scores[i]);
}

An enhanced loop is clearer when only values are needed:

for (int score : scores) {
    System.out.println(score);
}

Equivalent forms exist in C++ range-based loops and Python for loops. Prefer value-based traversal when the position is irrelevant; it reduces opportunities for index errors.

2.3 Multidimensional arrays

A two-dimensional array can model a table or matrix:

marks = [
    [72, 81, 69],
    [88, 76, 91]
]
print(marks[1][2])   # 91

The expression marks[1][2] selects the third value in the second row. In Java, a two-dimensional array is technically an array of arrays, so rows may have different lengths. C++ can represent a rectangular structure using nested std::array or a vector of vectors.

3. Dynamic Collections

A collection is an object that groups multiple values and provides operations for storing, accessing, searching, and updating them. Dynamic collections are appropriate when the number of elements changes during execution.

3.1 Lists and vectors

A list preserves order and normally permits duplicates.

std::vector<std::string> tasks = {"compile", "test"};
tasks.push_back("deploy");

List<String> tasks = new ArrayList<>();
tasks.add("compile");
tasks.add("test");

tasks = ["compile", "test"]
tasks.append("deploy")

A vector or array-backed list provides fast indexed access. Appending is usually amortized O(1): most appends are constant time, but occasional resizing requires copying elements. The average cost per append over a long sequence remains constant under the usual capacity-growth strategy. Inserting at the beginning or middle remains O(n).

3.2 Linked lists

A linked list stores nodes connected by references or pointers. Insertion can be efficient when the location is already known, but finding a location by index is O(n). Linked lists also use additional memory for links and may have poorer cache performance than arrays.

Consequently, a linked list is not automatically superior for insertion-heavy programs. If insertion positions are not already known, the cost of searching may dominate. In many practical applications, a dynamic array is the better default.

3.3 Sets

A set stores unique values. It is appropriate for membership testing, duplicate removal, and mathematical set-like operations.

visited = {"A", "B", "C"}
if "B" in visited:
    print("Already visited")

C++ std::set and Java TreeSet maintain sorted order, commonly with O(log n) search, insertion, and deletion. C++ std::unordered_set and Java HashSet use hashing and provide expected O(1) operations when the hash function distributes values effectively. Python set is hash-based and normally provides expected O(1) membership operations.

“Expected O(1)” is not a guarantee for every input. Poor hashing or deliberate collision patterns can degrade performance. Set elements must also meet the relevant equality and hashing requirements.

3.4 Maps and dictionaries

A map associates keys with values. It is suitable for lookup by an identifier rather than by position.

prices = {"book": 12.50, "pen": 1.20}
prices["book"] = 13.00

A key is normally unique. If a new value is assigned to an existing key, the old value is replaced. C++ uses std::map and std::unordered_map; Java uses TreeMap and HashMap; Python uses dict.

A sorted map commonly provides O(log n) operations. A hash map normally provides expected O(1) lookup, insertion, and deletion, but it does not use key order as its primary organizing principle. If output must be sorted, sort the keys or use an ordered map explicitly.

4. Tuples and Structured Values

A tuple groups a fixed number of values, potentially of different types. Python has a built-in tuple type:

coordinate = (10.5, 4.0)
x, y = coordinate

Tuples are useful for small, stable records and multiple return values. They are less expressive when field meanings are not obvious. A named class, record, or data class is usually preferable for a public domain model such as Customer, Invoice, or CourseResult.

Java offers records for compact immutable data carriers:

record Point(double x, double y) {}

C++ commonly uses std::pair, std::tuple, or a user-defined struct:

struct Point {
    double x;
    double y;
};

A tuple should not become an excuse for poorly documented positional data. The choice between a tuple and a named type is a choice between compactness and clarity.

5. Iterators and Traversal Abstraction

An iterator provides a generalized way to traverse a collection without exposing its internal representation. In C++, iterators are explicit objects. Java uses the Iterator<T> interface, while Python uses the iterator protocol through iter() and next().

for (auto it = values.begin(); it != values.end(); ++it) {
    std::cout << *it << '\n';
}

Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

it = iter(tasks)
while True:
    try:
        print(next(it))
    except StopIteration:
        break

Usually, a language’s for loop is clearer because it hides iterator mechanics. Explicit iterators become important when removing elements safely, combining traversal with algorithms, or writing reusable collection code.

A major danger is modifying a collection while traversing it. Some languages invalidate iterators; Java may throw ConcurrentModificationException; Python may produce skipped elements or unexpected behavior. Safer approaches include filtering into a new collection or using the collection’s supported removal operation.

6. Comprehensions and Transformations

A comprehension constructs a collection from another iterable using a compact expression. Python supports list, set, and dictionary comprehensions.

squares = [x * x for x in range(1, 6)]
evens = {x for x in range(20) if x % 2 == 0}
lengths = {word: len(word) for word in ["C++", "Java", "Python"]}

The first expression creates [1, 4, 9, 16, 25]. A comprehension can be understood as a transformation, optionally followed by a filter:

result = [expression for item in source if condition]

Java streams and C++ algorithms express similar ideas:

List<Integer> squares = numbers.stream()
    .map(x -> x * x)
    .toList();

std::vector<int> squares;
for (int x : numbers) {
    squares.push_back(x * x);
}

Comprehensions should remain readable. A deeply nested comprehension can be less maintainable than an ordinary loop with meaningful variable names.

7. Generics and Templates

Generics and templates allow algorithms and collections to work with multiple types while retaining type checking.

7.1 Java generics

public static <T> T first(List<T> values) {
    if (values.isEmpty()) {
        throw new IllegalArgumentException("Empty list");
    }
    return values.get(0);
}

T is a type parameter. The compiler checks that the list and returned value use a consistent type. Java generics primarily operate with reference types, so primitive values use wrapper classes such as Integer rather than int inside List<Integer>.

A bounded type parameter expresses a requirement:

public static <T extends Comparable<T>> T maximum(List<T> values) {
    if (values.isEmpty()) {
        throw new IllegalArgumentException("Empty list");
    }
    T result = values.get(0);
    for (T value : values) {
        if (value.compareTo(result) > 0) result = value;
    }
    return result;
}

The method requires elements that can be compared with one another.

7.2 C++ templates

C++ templates are instantiated for the types used by a program.

template <typename T>
T maximum(const std::vector<T>& values) {
    if (values.empty()) {
        throw std::invalid_argument("Empty vector");
    }
    T result = values[0];
    for (const T& value : values) {
        if (value > result) result = value;
    }
    return result;
}

The operation requires that T support the > operator. Modern C++ concepts can state such requirements more explicitly, but the underlying principle is the same: reusable code should communicate the operations it needs.

7.3 Python typing

Python is dynamically typed, but type annotations can document intended use and support static analysis tools.

from typing import TypeVar, Sequence

T = TypeVar("T")

def first(values: Sequence[T]) -> T:
    if not values:
        raise ValueError("Empty sequence")
    return values[0]

Python does not normally enforce these annotations at runtime. Tests and validation remain necessary. Static typing is therefore a design and tooling aid rather than a replacement for runtime safeguards.

7.4 Why generic code matters

Generic code reduces duplication and exposes errors early. Without generics, a collection may store unrelated values and force casts at retrieval time. Casts can fail at runtime and obscure the intended design.

Generics do not mean that every function should accept every type. Good generic code identifies a genuine common operation and states its constraints. Over-generalization can make an API difficult to understand.

8. Choosing a Suitable Structure

A practical selection process is:

1. Identify the required operations: lookup, insertion, deletion, ordering, iteration, or uniqueness.
2. Identify constraints: fixed size, memory limits, type restrictions, and concurrency requirements.
3. Estimate the dominant workload rather than optimizing an imaginary one.
4. Prefer the simplest structure that satisfies the requirements.
5. Confirm behavior with tests and, when necessary, measurements.

For example, a student attendance system may use a map from student ID to attendance record, a set of dates for which attendance was recorded, and a list for displaying students in registration order. One structure need not serve every purpose.

Applied Case: Inventory and Order Processing

Background

This illustrative case concerns a small online stationery shop. The system receives orders containing product codes and quantities, verifies stock, calculates totals, and reports unavailable products.

Problem

The original design stores product records in a list and searches the entire list for every order line. It also permits duplicate product codes and uses strings inconsistently, so " pen-01 " and "PEN-01" may be treated as different products.

Analysis

Product codes are unique identifiers, so a map is more suitable than a list for primary lookup. Product codes in an order should be normalized before lookup. The order lines themselves should remain ordered because the receipt displays them in the customer’s submitted order.

A suitable conceptual model is:

• dict or HashMap: product code → product record.
• List: ordered order lines.
• Set: codes already reported as unavailable.
• Tuple or record: one immutable order line containing code and quantity.

Approach

products = {
    "PEN-01": {"name": "Blue pen", "price": 1.20, "stock": 40},
    "NOTE-02": {"name": "Notebook", "price": 3.50, "stock": 12}
}

order = [(" pen-01 ", 3), ("NOTE-02", 2), ("MUG-99", 1)]
unavailable = set()
total = 0.0

for raw_code, quantity in order:
    code = raw_code.strip().upper()
    product = products.get(code)
    if product is None or product["stock"] < quantity:
        unavailable.add(code)
        continue
    product["stock"] -= quantity
    total += product["price"] * quantity

The map supports direct lookup by code. The list preserves order, and the set prevents duplicate unavailable-code messages. In production, prices should normally be represented with a decimal currency type rather than binary floating-point values, because exact monetary rounding rules matter.

Outcome

The revised design separates responsibilities and makes the data rules visible. It also scales better for lookup than repeatedly scanning a list. A production implementation would add validation for non-positive quantities, transaction handling so stock is not partially updated, authorization, audit logs, and tests for normalization and stock boundaries.

Learning points

The case demonstrates that structure selection follows domain meaning. A list is not a universal replacement for a map, and a set is not merely a faster list. Each structure communicates a different invariant: order, key uniqueness, or value uniqueness.

Challenges, Safety, and Professional Practice

Mutation and aliasing

Two variables may refer to the same mutable collection. Updating one reference can change what the other reference observes. Copy collections deliberately when independent ownership is required. In Python, a shallow copy duplicates the outer collection but not nested objects; a deep copy has different cost and semantic implications.

Input validation

Never assume that strings, indexes, quantities, or keys are valid merely because they came from a user interface. Validate format, length, range, and authorization. Avoid constructing SQL queries or shell commands by concatenating untrusted strings; use parameterized APIs and appropriate escaping.

Unicode and privacy

Text may contain multiple scripts, combining characters, and visually confusable symbols. Identifiers should be normalized according to the application’s policy. Sensitive strings such as passwords should not be stored in ordinary collections in plaintext. Use established password-hashing mechanisms and minimize retention of personal data.

Performance and readability

Big-O analysis helps compare scalability, but memory usage, cache behavior, allocation cost, and data size also matter. Measure representative workloads before replacing a clear structure with a complicated optimization. Use meaningful type names, document ownership, and avoid exposing mutable internal collections unnecessarily.

Contemporary Practice

Modern software frequently combines language collections with database result sets, JSON objects, data-processing pipelines, and concurrent services. Generic APIs are central to standard libraries and frameworks. Static analysis, linters, property-based tests, and integrated development environments can detect many incorrect type uses and boundary errors before deployment.

AI-assisted programming tools can suggest collection transformations or generic functions, but generated code must be reviewed. Particular risks include incorrect assumptions about mutability, unsafe string handling, inefficient nested searches, and subtle type conversions. The programmer remains responsible for correctness, security, licensing compliance, and protection of personal data.

Best Practices

• Choose a structure from required operations and invariants.
• Use a map for key-based lookup and a set for uniqueness.
• Use arrays or vectors for ordered, index-oriented data.
• Prefer enhanced loops or comprehensions when they improve clarity.
• Compare string contents using language-correct operations.
• Validate indexes, keys, quantities, and external text.
• Avoid modifying collections during traversal unless the operation is explicitly supported.
• Use generics or templates when a common algorithm genuinely applies to multiple types.
• State generic constraints clearly.
• Test empty, boundary, duplicate, invalid, and large inputs.
• Use decimal arithmetic or a suitable money type for financial values.

Chapter Summary

Strings represent textual sequences and require careful treatment of indexing, equality, normalization, immutability, and Unicode. Arrays provide fixed-size indexed storage, while dynamic lists or vectors support changing ordered data. Sets represent uniqueness and support membership operations; maps associate unique keys with values and are appropriate for identifier-based lookup. Tuples group small fixed records, although named classes or records often provide better domain clarity.

Iterators abstract traversal, while comprehensions and stream-style transformations express filtering and mapping compactly. Generics in Java, templates in C++, and type annotations in Python support reusable code while reducing type-related errors. Their value depends on clear constraints rather than unrestricted generality. Effective software design selects structures according to required operations, performance expectations, ownership, validation, and domain meaning.

Key Terms

String: A sequence of characters representing text.

Immutable: Unable to be changed after creation.

Array: Fixed-size indexed storage for elements of a related type.

List: An ordered collection that normally permits duplicates.

Vector: A resizable array-like sequence, especially in C++.

Set: A collection whose elements are unique.

Map: A collection associating keys with values.

Dictionary: A key-value mapping, especially in Python.

Tuple: A fixed group of possibly different typed values.

Iterator: An abstraction used to traverse a collection.

Comprehension: A compact expression for constructing a collection.

Generic: Code parameterized by one or more types.

Template: C++ mechanism for generating type-specific code.

Type parameter: A placeholder representing a type in generic code.

Hashing: Converting a key into a value used for hash-based lookup.

Aliasing: A situation in which multiple references designate the same object.

Normalization: Converting equivalent input forms into a consistent representation.

Amortized complexity: Average cost per operation over a sequence of operations.

Review Questions

Short Answer Questions

1. What is the principal difference between a list and a set?
2. Why should Java strings normally be compared with equals rather than ==?
3. What does a map use as its primary lookup mechanism?
4. Define an iterator.
5. What problem do generics and templates help solve?

Long Answer Questions

1. Compare arrays, vectors, linked lists, sets, and maps in terms of ordering, duplication, access, and common use.
2. Explain string immutability in Java and Python and discuss one advantage and one possible performance concern.
3. Describe how Python comprehensions relate to filtering and transformation operations.
4. Explain the role of constraints in generic or templated functions.
5. Discuss why modifying a collection while iterating can be unsafe and describe safer alternatives.

Analytical / Application Questions

1. Design suitable data structures for a library system that must find books by ISBN, preserve a borrower’s checkout order, and prevent duplicate ISBN values in a recommendation list. Justify each choice.
2. A program repeatedly searches a list of 100,000 product codes for each incoming order line. Analyze the likely performance issue and propose a revised design.
3. Design a generic function that returns the maximum element of a non-empty collection. State the type constraint, empty-input behavior, and how the design would differ in C++, Java, and Python.

Multiple Choice Questions with Answers

Question 1

Which structure is most appropriate for testing whether a value has already been seen, when duplicate values are not required?

A. Set

B. Tuple

C. Array

D. Map

Correct Answer: A. Set

Question 2

What is the usual complexity of indexed access in an array-backed sequence?

A. O(log n)

B. O(n)

C. O(1)

D. O(n²)

Correct Answer: C. O(1)

Question 3

In Java, which operation compares the contents of two String objects?

A. ==

B. equals

C. sameReference

D. compareReference

Correct Answer: B. equals

Question 4

What is the primary purpose of a map or dictionary?

A. Store only duplicate values

B. Associate keys with values

C. Guarantee positional access

D. Store values without any lookup rule

Correct Answer: B. Associate keys with values

Question 5

Which Python expression creates the squares of integers from 1 through 5?

A. [x + x for x in range(1, 6)]

B. [x * x for x in range(1, 6)]

C. {x / x for x in range(1, 6)]

D. (x * 2 for x in range(1, 5)]

Correct Answer: B. [x * x for x in range(1, 6)]

Question 6

What does a generic type parameter such as T represent?

A. A fixed integer value

B. A placeholder for a type

C. A database table

D. A loop counter

Correct Answer: B. A placeholder for a type

Question 7

Why can inserting into the middle of an array-backed list be O(n)?

A. The list must hash every element

B. The list may need to shift later elements

C. The list always sorts itself

D. The list converts every element to text

Correct Answer: B. The list may need to shift later elements

Question 8

Which structure best represents a product lookup by unique product code?

A. Map

B. Tuple

C. Plain string

D. Stack only

Correct Answer: A. Map

Question 9

What is a significant risk of modifying a collection during traversal?

A. It always makes values immutable

B. It can invalidate traversal state or skip elements

C. It guarantees sorted output

D. It changes all values to strings

Correct Answer: B. It can invalidate traversal state or skip elements

Question 10

In the inventory case, why was a set used for unavailable product codes?

A. To preserve every duplicate report

B. To prevent duplicate unavailable-code messages

C. To calculate currency exactly

D. To replace all product records

Correct Answer: B. To prevent duplicate unavailable-code messages