Collections, Strings, and Data Representation

Introduction and Context

Software rarely operates on one value at a time. Applications process names, messages, product catalogs, sensor readings, transactions, user permissions, and configuration records. Collections provide structures for storing and organizing multiple values, while strings represent textual data and records combine related values into meaningful entities. Choosing an appropriate representation affects readability, correctness, memory use, performance, and maintainability.

Python and C++ offer overlapping but differently designed collection facilities. Python emphasizes expressive built-in types such as `list`, `tuple`, `dict`, and `set`. C++ provides a broad Standard Library, including `std::vector`, `std::array`, `std::list`, `std::map`, `std::unordered_map`, and `std::set`, together with algorithms and iterators. A professional programmer must understand both the conceptual model and the language-specific behavior of these structures.

Learning Objectives

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

• distinguish scalar values, sequences, mappings, sets, records, and enumerations;
• manipulate strings using indexing, slicing, searching, formatting, and transformation;
• create and process one- and multidimensional collections;
• apply iteration, comprehensions, iterators, and standard algorithms;
• compare Python collections with C++ Standard Library containers;
• select a data structure according to ordering, uniqueness, lookup, mutability, and performance requirements;
• design clear representations for real-world data;
• identify common correctness, security, and maintainability risks.

1. Data Representation and Collection Abstraction

A data representation is the way information is encoded in a program. For example, a temperature may be represented as a floating-point number, while a student may be represented as a record containing an identifier, name, and grade. A collection is an object that groups multiple values and provides operations for accessing or modifying them.

The most important design questions are:

1. Multiplicity: Is there one value or many?

2. Order: Does position matter?

3. Uniqueness: Can duplicate values occur?

4. Association: Are values accessed by position or by a key?

5. Mutability: Should the collection change after creation?

6. Access pattern: Is frequent random access, sequential traversal, insertion, or lookup required?

These questions are more useful than choosing a type merely because it is familiar.

1.1 Common Abstract Data Models

• Sequence: An ordered collection accessed by position, such as a list or array.
• Tuple: An ordered, usually fixed-purpose group of values. In Python, tuples are immutable.
• Mapping: A collection of key–value associations, such as a Python dictionary or C++ map.
• Set: An unordered mathematical collection of unique elements.
• Record: A group of named fields describing one entity.
• Enumeration: A finite set of named symbolic constants.
• Matrix or multidimensional collection: A collection whose elements are themselves collections, such as a list of lists.

2. Strings

A string is a sequence of characters or, more precisely in many systems, a sequence of encoded units representing text. Text processing requires awareness of encoding. ASCII represents a limited character set, whereas UTF-8 can represent Unicode characters using one to four bytes. In Python, strings are Unicode text objects. In C++, `std::string` stores bytes; interpreting those bytes as Unicode requires an appropriate encoding strategy or library.

2.1 Python String Operations

```python

text = "Full Stack Development"

print(text[0]) # F

print(text[-1]) # t

print(text[0:4]) # Full

print(text[5:]) # Stack Development

print(text.lower())

print(text.replace("Development", "Programming"))

```

Python indexing begins at zero. A slice `text[start:stop:step]` includes `start` but excludes `stop`. Omitting a boundary uses the beginning or end of the string. A negative step can reverse a string:

```python

reversed_text = text[::-1]

```

Strings are immutable. An operation such as `replace` returns a new string rather than changing the original object.

Useful operations include:

• `strip()` for removing leading and trailing whitespace;
• `split(separator)` for producing a list of fields;
• `join(iterable)` for combining strings;
• `find(substring)` or `index(substring)` for searching;
• `startswith()` and `endswith()` for prefix and suffix checks;
• `isdigit()`, `isalpha()`, and related predicates for basic classification;
• formatted string literals for readable interpolation.

```python

name = "Amina"

score = 87.5

message = f"{name} achieved {score:.1f}%"

```

The `join` method belongs to the separator string:

```python

fields = ["CS101", "Collections", "6"]

record = ",".join(fields) # CS101,Collections,6

```

A frequent error is to assume that `split()` handles every form of structured data. Delimited text may contain quoted delimiters, escaped characters, or missing fields. Production CSV data should generally be processed with a CSV library rather than manually split on commas.

2.2 C++ Strings

C++ provides several text representations. A character array terminated by the null character `\\0` is a C-style string. Modern C++ code should generally prefer `std::string` for ordinary text:

```cpp

#include <string>

#include <iostream>

std::string text = "Full Stack Development";

std::cout << text.substr(0, 4); // Full

std::cout << text.find("Stack");

```

`std::string` supports indexing, concatenation, comparison, searching, and substrings. `std::string_view` can provide a non-owning view of existing character data, but the referenced data must remain alive and unchanged in ways that invalidate the view. This makes `string_view` efficient but requires careful lifetime management.

Text input also requires care. `std::cin >> word` stops at whitespace, whereas `std::getline(std::cin, line)` reads a complete line. Mixing formatted extraction and `getline` may leave a newline in the input buffer; consuming it deliberately avoids surprising empty reads.

3. Arrays, Lists, and Vectors

An array stores elements in a sequence. In a conventional fixed-size array, the number of elements is determined at creation. A dynamic array can grow, usually by allocating a larger block and copying or moving existing elements.

3.1 Python Lists

Python lists are mutable, ordered collections that may contain values of different types:

```python

numbers = [4, 7, 2]

numbers.append(9)

numbers[1] = 8

numbers.sort()

```

Important operations include `append`, `extend`, `insert`, `remove`, `pop`, `sort`, and `reverse`. Membership testing uses `in`. List indexing is typically constant-time for an existing position, while inserting near the beginning may require shifting many elements.

A shallow copy duplicates the list structure but not necessarily the objects referenced by its elements:

```python

copy_a = numbers.copy()

copy_b = list(numbers)

```

For nested mutable objects, use `copy.deepcopy` when independent recursive copying is genuinely required. Blind deep copying can be expensive and may not be appropriate for objects representing external resources.

3.2 C++ Sequence Containers

`std::array<T, N>` represents a fixed-size array known at compile time. `std::vector<T>` is the usual dynamic contiguous sequence. `std::deque<T>` supports efficient insertion and removal at both ends. `std::list<T>` is a linked list and is useful only for particular insertion and iterator-stability requirements; it is often slower than `vector` because of poor cache locality.

```cpp

#include <vector>

#include <algorithm>

std::vector<int> values{4, 7, 2};

values.push_back(9);

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

```

A vector’s `size()` is the number of elements currently stored, while `capacity()` is the allocated storage available before reallocation is needed. Calling `reserve(n)` can reduce reallocations when the approximate final size is known. Reallocation invalidates references, pointers, and iterators to elements, so these must not be retained carelessly.

4. Tuples, Records, and Enumerations

4.1 Tuples

A tuple is appropriate when values form a fixed conceptual unit. In Python:

```python

location = (51.5072, -0.1276)

latitude, longitude = location

```

Tuple unpacking improves readability when the number and meaning of positions are stable. However, a tuple with many positions can become obscure. Named records are preferable when fields require explicit names.

C++ provides `std::pair` and `std::tuple`:

```cpp

#include <tuple>

auto location = std::make_tuple(51.5072, -0.1276);

auto latitude = std::get<0>(location);

```

For domain data, a `struct` usually communicates intent better than numeric tuple positions.

4.2 Records

A record groups fields describing one entity. Python offers several approaches:

```python

from dataclasses import dataclass

@dataclass

class Student:

student_id: str

name: str

mark: float

student = Student("S104", "Amina", 87.5)

```

A `dataclass` supplies useful representation and comparison behavior while preserving named attributes. A dictionary may be suitable for flexible or externally supplied fields, but a record or class provides clearer expectations for stable application data.

C++ uses `struct` or `class`:

```cpp

struct Student {

std::string student_id;

std::string name;

double mark;

};

```

Records should preserve invariants. For example, if a mark must be between 0 and 100, validation should occur at the boundary where the record is created or updated.

4.3 Enumerations

An enumeration represents a finite set of named alternatives. Python’s `Enum` avoids unclear magic numbers:

```python

from enum import Enum

class Status(Enum):

PENDING = "pending"

PAID = "paid"

CANCELLED = "cancelled"

```

C++ offers scoped enumerations:

```cpp

enum class Status { Pending, Paid, Cancelled };

```

Scoped enumerations reduce accidental conversion to integers and prevent name collisions. Enumerations improve readability, but external serialization must define stable representations. Reordering enumeration declarations should not silently change stored database or network values.

5. Dictionaries, Maps, and Sets

5.1 Mappings

A mapping associates keys with values. Python dictionaries are mutable hash tables:

```python

prices = {"book": 12.50, "pen": 1.20}

prices["notebook"] = 4.75

for item, price in prices.items():

print(item, price)

```

Dictionary keys must be hashable. Strings, numbers, and tuples containing hashable values can normally be keys; mutable lists cannot. Modern Python preserves insertion order as part of the language specification, but a dictionary should still be chosen primarily for key-based access rather than positional meaning.

Use `get` when a missing key is expected:

```python

count = frequencies.get("python", 0)

```

`collections.defaultdict` and `collections.Counter` are useful specialized tools for grouping and frequency analysis.

C++ offers ordered and unordered mappings. `std::map` maintains keys in sorted order, typically with logarithmic lookup, insertion, and removal. `std::unordered_map` uses hashing and offers average constant-time lookup under suitable hashing conditions, but it does not provide sorted traversal and can have degraded worst-case behavior. The exact performance depends on implementation, hash quality, load, and workload.

5.2 Sets

Sets store unique elements. They are useful for membership, deduplication, and mathematical operations:

```python

required = {"id", "email", "password"}

received = {"id", "email", "password", "phone"}

missing = required - received

extra = received - required

```

Python sets support union (`|`), intersection (`&`), difference (`-`), and symmetric difference (`^`). Set elements must be hashable. A `frozenset` is immutable and can itself be used as a dictionary key.

C++ provides `std::set`, which maintains sorted unique keys, and `std::unordered_set`, which uses hashing. A set is not a substitute for a list when duplicate occurrences or meaningful order must be preserved.

6. Iteration, Slicing, Comprehensions, and Algorithms

Iteration visits elements according to a collection’s traversal protocol. Python’s `for` loop works with iterable objects:

```python

for index, name in enumerate(["Ada", "Linus", "Grace"], start=1):

print(index, name)

```

`zip` traverses corresponding elements:

```python

names = ["Ada", "Linus"]

marks = [95, 91]

for name, mark in zip(names, marks):

print(name, mark)

```

A list comprehension expresses transformation and filtering compactly:

```python

squares_of_even = [n * n for n in range(10) if n % 2 == 0]

```

This produces `[0, 4, 16, 36, 64]`. Comprehensions are best when the expression remains easy to read. Nested comprehensions should not replace a clearly structured loop when the logic becomes difficult to understand.

Dictionary and set comprehensions are also available:

```python

lengths = {word: len(word) for word in ["map", "set", "list"]}

unique_lengths = {len(word) for word in ["map", "set", "list"]}

```

An iterator produces values one at a time and supports streaming or lazy processing. Python generators use `yield`:

```python

def positive(values):

for value in values:

if value > 0:

yield value

```

Generators reduce memory usage when the complete result need not be stored. They are consumable: after traversal, they generally do not restart automatically.

C++ iterators act as generalized pointers. Containers expose `begin()` and `end()`, and standard algorithms operate on iterator ranges:

```cpp

#include <algorithm>

#include <vector>

std::vector<int> values{3, 1, 4, 1};

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

int count = std::count(values.begin(), values.end(), 1);

```

The range-based `for` loop is often clearer:

```cpp

for (const int value : values) {

// process value

}

```

Use `const` when an operation does not need modification. In modern C++, algorithms such as `std::ranges::sort` can improve composability, subject to the selected language standard and compiler support.

7. Multidimensional Collections

A two-dimensional collection can represent a table or grid. In Python, a list of lists is straightforward:

```python

grid = [

[1, 2, 3],

[4, 5, 6]

]

print(grid[1][2]) # 6

```

Avoid creating rows through repeated references:

```python

bad = [[0] 3] 2

bad[0][0] = 9 # changes both apparent rows

```

The correct independent-row construction is:

```python

good = [[0 for _ in range(3)] for _ in range(2)]

```

Nested lists may be jagged, meaning rows have different lengths. This flexibility is useful for irregular data but requires validation before assuming rectangular dimensions. Numerical applications often benefit from specialized array libraries, whose storage and operations may differ substantially from ordinary Python lists.

In C++, nested vectors are common:

```cpp

std::vector<std::vector<int>> matrix(2, std::vector<int>(3, 0));

```

This creates two independent rows. For a fixed rectangular structure, `std::array<std::array<int, 3>, 2>` communicates dimensions at compile time. Contiguous flattened storage can provide better cache behavior for large numerical grids, but indexing logic becomes an additional design responsibility.

8. Choosing a Structure by Use Case

| Requirement | Appropriate choice | Main reason |

|---|---|---|

| Ordered, changeable sequence | Python `list`, C++ `vector` | Efficient indexing and iteration |

| Fixed-size homogeneous sequence | Python tuple or C++ `array` | Stable structure and clear intent |

| Key-based lookup | Python `dict`, C++ `unordered_map` | Direct association between key and value |

| Sorted key traversal | C++ `map` or Python sorted processing | Ordered output and range operations |

| Unique membership | Python `set`, C++ `unordered_set` | Efficient duplicate elimination and tests |

| Sorted unique values | C++ `set` | Maintains ordering automatically |

| Named entity fields | Python `dataclass`, C++ `struct` | Readable domain representation |

| Finite symbolic states | Python `Enum`, C++ `enum class` | Prevents unclear magic values |

| Streaming large results | Python generator, C++ iterator/range | Avoids storing all results |

Complexity is one consideration, not the only one. A hash table may offer average constant-time lookup, but a small vector can be faster in practice because of locality and low overhead. Benchmarking representative workloads is preferable to relying only on asymptotic labels.

9. Worked Example: Word-Frequency Analysis

Suppose an application must count words in a short document while ignoring case and punctuation.

```python

import re

from collections import Counter

text = "Code, test, and deploy. Test code carefully!"

words = re.findall(r"[A-Za-z]+", text.lower())

frequencies = Counter(words)

print(frequencies)

print(frequencies["test"])

```

The regular expression extracts alphabetic words, and `lower()` normalizes case. The resulting sequence is:

```text

['code', 'test', 'and', 'deploy', 'test', 'code', 'carefully']

```

The frequency mapping is therefore:

```text

code: 2

test: 2

and: 1

deploy: 1

carefully: 1

```

A list is appropriate for the extracted sequence because order is retained. A dictionary-like counter is appropriate for aggregation by word. A set could answer whether a word has appeared, but it would lose frequency information. This illustrates that one task may legitimately use multiple structures at different stages.

10. Applied Case: Course Enrollment Service

This is an illustrative case.

Background

A university enrollment service receives student enrollment requests. Each request contains a student identifier, course code, requested status, and a list of prerequisite course codes.

Problem

The service must reject duplicate course codes, verify that prerequisites are satisfied, maintain student records, and produce a sorted report. Poor representation could permit duplicate enrollments or make validation inconsistent.

Analysis

A student identifier is a string key. A student’s enrolled courses are naturally a set because a course should not appear twice. Student information is a record. Enrollment status is an enumeration. A mapping from student ID to record supports direct lookup. A list is suitable for displaying a selected ordering, but not for enforcing uniqueness.

Approach

A Python design might use:

```python

from dataclasses import dataclass

from enum import Enum

class EnrollmentStatus(Enum):

ACTIVE = "active"

COMPLETED = "completed"

@dataclass

class Student:

student_id: str

name: str

courses: set[str]

students: dict[str, Student] = {}

```

When processing a request, the service validates the student identifier, converts incoming course codes to a normalized form such as uppercase, checks prerequisite membership using set operations, and adds the course only if the request is valid. The service should not trust client-supplied status values or assume that textual input is already normalized.

Outcome

The representation makes several rules explicit: identifiers index records, sets prevent duplicate courses, and enumerations limit status values. Reports can use `sorted(student.courses)` without changing the underlying set.

Learning Points

• Data structures can enforce domain rules.
• Normalization should occur before comparison.
• External input requires validation.
• Internal sets need not determine presentation order.
• Stable records are clearer than unstructured nested dictionaries.

11. Challenges, Safety, and Best Practices

Common problems include off-by-one slicing errors, modifying a collection during iteration, aliasing nested mutable objects, assuming dictionary order expresses business meaning, and using a list where uniqueness is required. In C++, iterator invalidation, dangling references, and incorrect ownership can produce undefined behavior. In Python, mutable default arguments and accidental shared references can produce subtle state errors.

Text also creates security concerns. Never construct SQL, shell commands, or HTML by directly concatenating untrusted strings. Use parameterized queries, safe subprocess interfaces, and context-appropriate output escaping. Unicode normalization and case conversion can affect identity comparisons; security-sensitive systems should define and test normalization rules rather than assuming that visually similar strings are equivalent.

For reliable collection code:

• choose the narrowest structure that expresses the requirement;
• validate external data at boundaries;
• preserve invariants in constructors or controlled update methods;
• use meaningful names rather than positional conventions;
• avoid premature optimization but measure important workloads;
• document ordering and duplicate policies;
• use immutable representations where mutation is not required;
• test empty, duplicate, missing, unusually large, and malformed inputs;
• use type hints, static analysis, compiler warnings, and automated tests;
• serialize records and enumerations with stable, documented formats.

Contemporary software increasingly processes large streams, distributed events, and semi-structured data. Iterators, generators, views, and lazy pipelines can reduce memory consumption, while schema-aware records and validation tools improve reliability. AI-assisted coding can suggest collection operations, but generated code must still be reviewed for aliasing, complexity, encoding, privacy, and input-validation errors. An assistant may produce syntactically valid code that uses a list where a set or validated record is required.

Chapter Summary

Collections are abstractions for organizing multiple values. Sequences preserve order, mappings associate keys with values, sets enforce uniqueness, records describe entities, and enumerations represent finite symbolic states. Python supplies expressive built-in collections, comprehensions, generators, and dataclasses. C++ supplies specialized Standard Library containers, iterators, algorithms, and strong control over storage and lifetime.

Strings require attention to immutability, indexing, formatting, parsing, and character encoding. Multidimensional structures require care with independent storage and dimensions. Structure selection should follow requirements for order, uniqueness, mutability, lookup, memory, and traversal rather than habit. Correct collection design also includes validation, security, stable serialization, testing, and awareness of language-specific behavior.

Key Terms

String: A sequence of text characters or encoded units.

Unicode: A standard for representing characters from many writing systems.

Sequence: An ordered collection accessed by position.

List: A mutable, ordered Python collection.

Array: A fixed-size or contiguous indexed collection.

Vector: A resizable contiguous C++ sequence container.

Tuple: An ordered fixed-purpose collection, immutable in Python.

Mapping: A key–value association structure.

Dictionary: Python’s hash-based mutable mapping.

Set: A collection of unique elements.

Record: A group of named fields describing an entity.

Enumeration: A finite set of named symbolic constants.

Iterator: An object or protocol for producing collection elements sequentially.

Comprehension: Compact syntax for constructing a collection from an iterable.

Generator: A lazy Python producer that yields values on demand.

Slicing: Selecting a range of sequence elements.

Hashing: Transforming a key into a value used for hash-table organization.

Serialization: Converting data into a format suitable for storage or transmission.

Iterator invalidation: The loss of validity of a C++ iterator after collection changes.

Review Questions

Short Answer Questions

1. Why is a set preferable to a list when duplicate values must be prevented?

2. Explain the difference between a Python string and a Python list regarding mutability.

3. What is the purpose of a record or dataclass?

4. Distinguish `std::map` from `std::unordered_map`.

5. Why can a generator use less memory than a list?

Long Answer Questions

1. Compare Python lists, tuples, and dictionaries in terms of ordering, mutability, access, and typical use.

2. Explain how Python comprehensions and C++ standard algorithms support expressive collection processing.

3. Discuss the major design considerations when choosing a collection for an application.

4. Explain common aliasing and iterator-invalidation errors and how programmers can avoid them.

5. Describe how strings, encodings, normalization, and input validation affect reliable text processing.

Analytical / Application Questions

1. Design suitable Python and C++ representations for a library catalog containing books, authors, unique ISBNs, and availability states. Justify each structure.

2. A program must process a ten-gigabyte log file and report the five most frequent error codes. Explain which structures and processing strategy you would select and why.

3. Analyze a proposed design that stores a student’s courses in a list, status as an integer, and student records in parallel arrays. Identify risks and redesign it using appropriate collections and records.

Multiple Choice Questions with Answers

Question 1

Which Python collection is most appropriate for enforcing unique course codes?

A. list

B. set

C. tuple

D. string

Correct Answer: B. set

Question 2

What does the Python slice text[1:4] include?

A. Characters at indices 1, 2, and 3

B. Characters at indices 1, 2, 3, and 4

C. Characters at indices 0, 1, 2, and 3

D. Only the character at index 4

Correct Answer: A. Characters at indices 1, 2, and 3

Question 3

Which C++ container is normally the default choice for a resizable contiguous sequence?

A. std::vector

B. std::map

C. std::set

D. std::list

Correct Answer: A. std::vector

Question 4

What is a principal advantage of a Python generator?

A. It automatically sorts every result

B. It stores all results permanently

C. It can produce values lazily

D. It prevents all runtime errors

Correct Answer: C. It can produce values lazily

Question 5

Which structure is designed primarily for key-based lookup?

A. Python dict

B. Python tuple

C. C++ array

D. Python string

Correct Answer: A. Python dict

Question 6

Why is [[0] 3] 2 problematic for a mutable two-dimensional Python grid?

A. It creates rows with different lengths

B. It creates repeated references to the same row

C. It sorts the rows automatically

D. It prevents indexing

Correct Answer: B. It creates repeated references to the same row

Question 7

Which C++ type best represents a fixed-size sequence known at compile time?

A. std::unordered_map

B. std::array

C. std::set

D. std::string_view

Correct Answer: B. std::array

Question 8

What does a Python dictionary comprehension construct?

A. A mapping from expressions evaluated over an iterable

B. An immutable character sequence only

C. A C++ iterator range

D. A sorted mathematical matrix

Correct Answer: A. A mapping from expressions evaluated over an iterable

Question 9

Which representation best communicates a finite set of states such as Pending, Paid, and Cancelled?

A. An enumeration

B. A floating-point number

C. A raw memory address

D. A list of unrelated strings

Correct Answer: A. An enumeration

Question 10

What is a key concern when using C++ iterators after vector growth causes reallocation?

A. They may become invalid

B. They automatically become sorted

C. They convert into strings

D. They guarantee constant memory use

Correct Answer: A. They may become invalid