Generic Programming and the C++ Standard Library

Introduction

Large software systems are rarely built by writing each operation separately for every data type. A sorting operation, for example, should not need one implementation for integers, another for strings, and a third for user-defined objects. Generic programming addresses this problem by expressing algorithms and data structures in terms of requirements rather than fixed types.

C++ supports generic programming through function templates, class templates, iterators, algorithms, lambdas, functors, ranges, and utility types. The C++ Standard Library applies these ideas in a coherent framework. It provides reusable containers such as vector, list, map, and unordered_map, together with algorithms such as sort, find, copy, and accumulate.

The central engineering question is not simply “Which container is available?” It is “Which representation and operation model best satisfy the program’s performance, correctness, and maintainability requirements?”

Learning Objectives

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

• explain the purpose and structure of generic programming;
• write and use function and class templates;
• select suitable standard containers for common requirements;
• use iterators, algorithms, lambdas, and function objects;
• describe the role of ranges and views in modern C++;
• use utility types such as pair, tuple, optional, and variant;
• compare data structures using complexity, memory, and maintainability considerations;
• design reusable solutions using the C++ Standard Library.

1. Generic Programming as an Abstraction Technique

Generic programming separates an algorithm from the particular data type on which it operates. The algorithm specifies the operations it needs. Any type supporting those operations can be used.

For example, a function that returns the larger of two values does not need to know whether the values are integers, floating-point numbers, or strings. It only requires that the values can be compared using >.

template <typename T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

The keyword typename introduces a type parameter. class may also be used in this context:

template <class T>
T maximum(T a, T b) {
    return (a > b) ? a : b;
}

These declarations have the same meaning. When the compiler encounters maximum(7, 11), it deduces T as int and generates an appropriate specialization. This process is called template instantiation.

Function-template deduction

Template argument deduction generally works when the arguments have compatible types:

maximum(3, 8);          // T is int
maximum(2.5, 7.1);      // T is double
maximum(std::string("A"), std::string("B"));

The following call may fail because the arguments imply different types:

// maximum(3, 4.5);      // int and double conflict

A caller may explicitly specify the type:

maximum<double>(3, 4.5);

Generic code should be designed around valid operations rather than assumptions about implementation details. Modern C++20 concepts can make these requirements explicit:

#include <concepts>

template <std::totally_ordered T>
T maximum(T a, T b) {
    return a > b ? a : b;
}

The concept constrains T to types supporting the required ordering operations. Constraints improve diagnostics and document intent.

2. Class Templates

A class template defines a family of related classes. A simple fixed-size box illustrates the idea:

template <typename T>
class Box {
private:
    T value;

public:
    explicit Box(T v) : value(v) {}

    const T& get() const {
        return value;
    }
};

Instances can hold different types:

Box<int> count(42);
Box<std::string> name("Ada");

Class templates are useful when data representation and operations should vary consistently with a type. The Standard Library uses this technique extensively: std::vector<int> and std::vector<std::string> are specializations of the same container template.

Non-type template parameters

Templates may also receive compile-time values:

template <typename T, std::size_t N>
class Array {
    T values[N];
public:
    constexpr std::size_t size() const { return N; }
};

Array<int, 10> and Array<int, 20> are different types. The size is known at compile time, which can support optimization and prevent some runtime errors.

Template specialization

A specialization supplies a different implementation for a particular type or condition. Specialization is powerful but should be used sparingly because excessive specialization increases complexity. Prefer a general template unless the special case provides a clear correctness or performance benefit.

3. Standard Containers

A container manages a collection of objects. The major container families differ in memory organization, access patterns, ordering, and complexity.

Here, n denotes the number of stored elements. Big-O notation describes an asymptotic upper-growth category; actual performance also depends on memory locality, allocation cost, object size, and workload.

Sequence containers

std::vector is usually the default sequence container. Its elements occupy contiguous memory, making indexing and traversal efficient:

std::vector<int> scores{72, 81, 90};
scores.push_back(95);
std::cout << scores[1];

When a vector exceeds its capacity, it allocates a larger region and moves or copies its elements. Therefore, appending is amortized constant time, but an individual append can be linear in the number of elements.

std::array<T, N> has a fixed size known at compile time. It is appropriate when the number of elements is fixed. A built-in array does not provide the same standard interface and safety conveniences.

std::deque is useful when efficient insertion at both the front and back is required. It does not guarantee contiguous storage, so it is not a substitute for vector in every application.

Linked lists are specialized structures. Although insertion and removal can be constant time when an iterator is already available, locating the position is generally linear, and node allocation can harm cache performance. A list should therefore not be selected merely because it has constant-time insertion in theory.

Associative containers

Ordered associative containers maintain keys in sorted order. A map stores unique keys and associated values:

std::map<std::string, int> inventory;
inventory["pens"] = 120;
inventory["books"] = 45;

A multimap permits duplicate keys. A set stores keys without separate mapped values.

Unordered containers use hashing. They are suitable when ordering is unnecessary and fast average lookup is important:

std::unordered_map<int, std::string> students;
students.emplace(101, "Mira");

Hash-table performance depends on a good hash function, an appropriate load factor, and valid equality comparisons. Worst-case lookup is linear, even though average lookup is commonly constant time.

4. Iterators: A Common Access Interface

An iterator represents a position in a range. It allows algorithms to operate on different containers without knowing their internal organization.

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

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

begin() refers to the first element, while end() refers to the position immediately after the last element. The end iterator must not be dereferenced.

The common iterator categories are:

• input iterator: reads elements while moving forward;
• output iterator: writes elements while moving forward;
• forward iterator: supports repeated forward traversal;
• bidirectional iterator: supports forward and backward movement;
• random-access iterator: supports jumps and ordering comparisons;
• contiguous iterator: represents elements stored contiguously.

An algorithm’s requirements matter. std::sort requires random-access iterators, so it works with vector and deque but not with list. A list provides its own sort member function.

5. Algorithms and Function Objects

The <algorithm> header provides non-member algorithms that operate on iterator ranges. A range is conventionally written as [first, last), meaning that first is included and last is excluded.

std::vector<int> values{4, 1, 9, 2};
std::sort(values.begin(), values.end());

auto position = std::find(values.begin(), values.end(), 4);
if (position != values.end()) {
    std::cout << "Found";
}

The half-open convention makes empty ranges natural: if first == last, the range contains no elements. It also allows adjacent ranges to connect without overlap.

Important algorithm families include:

• searching: find, find_if, binary_search;
• modification: copy, fill, replace, transform;
• ordering: sort, stable_sort, reverse;
• counting and testing: count, all_of, any_of, none_of;
• reduction: accumulate, reduce;
• set operations: set_union, set_intersection.

A function object, or functor, is an object that behaves like a function because it defines operator():

struct IsLong {
    bool operator()(const std::string& text) const {
        return text.size() > 5;
    }
};

std::count_if(words.begin(), words.end(), IsLong{});

Functors can store state and have a type known at compile time. They are especially useful when a reusable policy requires configuration.

6. Lambdas

A lambda is an unnamed function object. Its general form is:

[capture](parameters) -> return_type {
    statements
}

The return type is often inferred.

std::sort(values.begin(), values.end(),
          [](int a, int b) { return a > b; });

This sorts in descending order. Captures allow a lambda to use surrounding variables:

int limit = 50;
auto large = [limit](int value) {
    return value > limit;
};

[limit] captures by value. [&limit] captures by reference. [&] captures all used local variables by reference, while [=] captures them by value. Broad captures should be used carefully because they can obscure dependencies and create lifetime errors.

A lambda that captures a reference must not outlive the referenced object. Capturing by value avoids that particular reference-lifetime problem, although the captured value may become stale.

7. Ranges and Views in Modern C++

C++20 ranges provide a more compositional interface for algorithms. Instead of passing separate iterator pairs, a range represents the sequence itself.

#include <ranges>
#include <algorithm>

std::ranges::sort(values);

Views are lazy transformations. They do not normally create a new container immediately:

auto result = values
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * x; });

for (int x : result) {
    std::cout << x << ' ';
}

The filtering and transformation occur as the view is traversed. This can reduce unnecessary temporary storage and make a processing pipeline clear. However, view lifetime must be considered: a view generally refers to an underlying range and should not outlive it.

Ranges improve readability, but not every legacy algorithm or third-party library is range-enabled. Interoperability and compiler support should be checked in production projects.

8. Utility Types

The Standard Library provides types for expressing common relationships and states.

pair and tuple

std::pair<std::string, int> record{"Mira", 88};
std::cout << record.first;

A tuple stores a fixed number of possibly different types:

auto data = std::make_tuple(101, std::string("Mira"), 88.5);
auto [id, name, grade] = data;

Structured bindings improve readability when decomposing aggregates, pairs, tuples, and certain user-defined types.

optional

std::optional<T> represents either a value of type T or no value. It is preferable to using a special sentinel such as -1 when every integer may be valid.

std::optional<int> find_score(int id) {
    if (id == 101) return 88;
    return std::nullopt;
}

The caller should test the state before accessing the value.

variant

std::variant<A, B, C> stores one value from a specified set of alternatives. It is a type-safe alternative to a union:

std::variant<int, std::string> item = "ready";
std::visit([](const auto& value) {
    std::cout << value;
}, item);

any

std::any can hold a value of almost any copyable type. Its flexibility reduces compile-time guarantees and requires type-aware extraction. It should be used when the set of possible types genuinely cannot be expressed more precisely.

9. Choosing a Data Structure

Selection should begin with requirements rather than habit. Important questions include:

1. Is the number of elements fixed or dynamic?
2. Is random indexing required?
3. Are elements accessed by position or by key?
4. Is sorted order required?
5. Are insertions concentrated at one or both ends?
6. Are references or iterators required to remain stable?
7. Is memory locality important?
8. What are the expected input size and operation frequencies?

For example, a student-grade table indexed by student number may use unordered_map for average fast lookup. A report requiring alphabetical output may use map, or may collect and sort keys separately. A time-series sequence commonly benefits from vector because traversal and indexing dominate.

Complexity is a model, not a performance guarantee. Two O(1) operations can differ greatly in constant cost. A contiguous vector traversal is often faster than linked-list traversal because of cache locality, even when both are O(n).

10. Worked Example: Generic Statistics

The following function computes the arithmetic mean of a numeric range:

#include <numeric>
#include <ranges>

template <std::ranges::input_range R>
requires std::is_arithmetic_v<std::ranges::range_value_t<R>>
double mean(const R& values) {
    if (values.empty()) {
        throw std::invalid_argument("mean of empty range");
    }

    double total = 0.0;
    std::size_t count = 0;
    for (auto value : values) {
        total += value;
        ++count;
    }
    return total / count;
}

For the values 70, 80, and 90, the total is 240 and the count is 3, so the mean is 80. The function explicitly rejects an empty range because division by zero would not represent a meaningful average. The conversion to double also avoids integer division in the returned result.

In production code, numerical concerns may require a wider accumulator, compensated summation, or a domain-specific numeric type. Genericity does not eliminate the need to understand the properties of the underlying data.

11. Case Application: University Course Registration

Background

Consider an illustrative university registration system. Each student has an identifier, and each student may register for several courses. The system must support registration, withdrawal, lookup, and generation of an ordered report.

Problem

The design team initially stores students in a vector and searches linearly for every registration request. This is simple, but repeated lookup becomes slow as the number of students grows. The report also requires students ordered by identifier.

Analysis

The primary operation is lookup by key. Ordering is also required for reporting. A map<int, Student> directly represents these requirements. It provides logarithmic lookup and maintains keys in sorted order. If ordering were unnecessary and average lookup speed were the only priority, unordered_map<int, Student> could be considered.

Each student’s courses can be stored in a vector<string> when the number of courses is small and sequential traversal is common. If duplicate course registration must be prevented and fast membership testing is important, unordered_set<string> is more appropriate.

Approach

struct Student {
    std::string name;
    std::unordered_set<std::string> courses;
};

std::map<int, Student> students;

void register_course(int id, const std::string& course) {
    auto it = students.find(id);
    if (it == students.end()) {
        throw std::invalid_argument("unknown student");
    }
    it->second.courses.insert(course);
}

The set’s insertion operation naturally avoids duplicate course codes. The map keeps student identifiers ordered for reports.

Outcome

The revised design expresses the domain rules directly. It avoids repeated linear scans, prevents duplicate registrations, and supports ordered traversal. It also remains maintainable because each container communicates its intended role.

Learning Points

• Data structures should reflect dominant operations.
• Average-case complexity must be distinguished from worst-case complexity.
• Container choice affects clarity as well as speed.
• A simple structure may be best when data sizes are small; optimization should be evidence-based.

12. Limitations, Safety, and Professional Practice

Templates can produce long compiler diagnostics, increase compilation time, and expose implementation details through headers. Clear constraints, small interfaces, and meaningful names reduce these costs.

Iterator invalidation is a major source of errors. Inserting into a vector may invalidate iterators, pointers, and references if reallocation occurs. Erasing an element invalidates iterators according to the container’s rules. Programmers should consult the container contract rather than assume that an iterator remains valid.

Generic code should preserve useful invariants. For example, a sorting comparator must define a consistent strict weak ordering. A comparator that says both a < b and b < a for the same pair can make sorting behavior invalid.

Exception safety also matters. Standard containers generally provide strong guarantees for many operations, but guarantees depend on element move and copy behavior. Resource ownership should normally use RAII and standard smart pointers rather than manual new and delete.

Security concerns include uncontrolled memory growth, denial-of-service inputs that produce poor hash behavior, unsafe parsing, and accidental exposure of sensitive data. Choosing a generic container does not automatically make a program secure.

13. Contemporary C++ and AI-Assisted Development

Modern C++ development increasingly uses concepts, ranges, modules, parallel algorithms, and improved compile-time programming. These facilities can make interfaces more expressive, but they require compatible toolchains and careful team standards.

AI-assisted programming tools can suggest templates, algorithms, or container choices. Their output must be reviewed for iterator invalidation, lifetime errors, incorrect complexity assumptions, exception behavior, and licensing or privacy concerns. Generated code should be tested and understood by a responsible developer; generic-looking code is not necessarily correct or maintainable.

Best Practices

• Prefer the simplest standard container satisfying the requirements.
• Use vector as the default sequence container unless evidence suggests otherwise.
• Prefer standard algorithms to handwritten loops when the algorithm expresses intent clearly.
• Use lambdas for local policies and named functors for reusable or stateful policies.
• Constrain templates with concepts or other clear requirements.
• Treat iterator, pointer, and reference invalidation as part of the design.
• Measure performance with representative data rather than relying only on theoretical complexity.
• Use optional for an absent value and variant for a closed set of alternatives.
• Avoid any when a more precise type is available.
• Keep ownership explicit through RAII and standard smart pointers.

Chapter Summary

Generic programming enables algorithms and data structures to operate across many types while preserving type safety. Function templates and class templates provide the foundation, while concepts can state requirements explicitly. The Standard Library supplies sequence, associative, and unordered containers with different complexity and storage characteristics.

Iterators create a common access model, and standard algorithms reuse operations across containers. Lambdas and functors express customizable behavior. C++20 ranges and views support readable, lazy processing pipelines. Utility types such as optional, variant, pair, and tuple represent common data relationships and states.

Effective container selection depends on access patterns, ordering requirements, iterator stability, memory behavior, and maintainability. Complexity analysis is essential, but actual performance also depends on locality, allocation, constants, and workload. Professional generic programming combines abstraction with constraints, testing, safety, and evidence-based design.

Key Terms

Generic programming: Writing algorithms and data structures in terms of supported operations rather than fixed types.

Function template: A parameterized function from which type-specific functions can be generated.

Class template: A parameterized class definition used to create related types.

Template instantiation: Compiler generation of a concrete template specialization.

Concept: A named compile-time requirement on template arguments.

Container: A library type that stores and manages a collection of objects.

Iterator: An object representing a position in a range.

Range: A sequence represented traditionally by a beginning and an end position.

Algorithm: A reusable operation such as searching, sorting, or transforming.

Functor: An object that can be called like a function.

Lambda: An unnamed function object defined at the point of use.

View: A usually lazy range adaptor that refers to or transforms another range.

Sequence container: A container organized as a linear sequence.

Associative container: A container that organizes elements according to keys.

Hash table: A structure using a hash function to locate entries.

Iterator invalidation: Loss of validity of an iterator after a container operation.

optional: A type representing either one value or no value.

variant: A type-safe object containing one value from a fixed set of alternatives.

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

RAII: Resource Acquisition Is Initialization, an ownership and cleanup technique based on object lifetime.

Review Questions

Short Answer Questions

1. What problem does generic programming solve?
2. Distinguish a function template from a class template.
3. Why is vector often a good default sequence container?
4. What is the meaning of the half-open range [first, last)?
5. What is the purpose of std::optional?

Long Answer Questions

1. Compare vector, list, and deque in terms of organization, access, insertion, and practical use.
2. Explain how iterators allow standard algorithms to work with multiple container types.
3. Describe lambdas, captures, and function objects, including appropriate use cases.
4. Explain ordered and unordered associative containers and their performance trade-offs.
5. Discuss how concepts and ranges improve the design of modern generic C++ programs.

Analytical / Application Questions

1. Design a container strategy for a library system requiring lookup by ISBN, alphabetical reports, and prevention of duplicate loans. Justify each choice.
2. A program repeatedly inserts at the front of a sequence and occasionally accesses elements by index. Analyze at least two container choices and explain the trade-offs.
3. Review a design that uses std::any for every field in a data record. Identify maintainability and safety problems and propose more suitable standard-library types.

Multiple Choice Questions with Answers

Question 1

Which container provides contiguous storage and constant-time indexed access?

A. std::vector

B. std::list

C. std::map

D. std::unordered_set

Correct Answer: A. std::vector

Question 2

What does the end iterator of a range represent?

A. The last element

B. The position immediately after the last element

C. The first invalid memory address

D. The container capacity

Correct Answer: B. The position immediately after the last element

Question 3

Which feature expresses compile-time requirements on template arguments in modern C++?

A. Namespaces

B. Concepts

C. Exceptions

D. Streams

Correct Answer: B. Concepts

Question 4

What is the average lookup complexity commonly associated with std::unordered_map?

A. O(1)

B. O(log n)

C. O(n log n)

D. O(n²)

Correct Answer: A. O(1)

Question 5

Which type represents either a value or no value?

A. std::variant

B. std::tuple

C. std::optional

D. std::array

Correct Answer: C. std::optional

Question 6

What is a lambda in C++?

A. A dynamically allocated array

B. An unnamed function object

C. A special kind of iterator

D. A namespace alias

Correct Answer: B. An unnamed function object

Question 7

Why can insertion into a vector invalidate iterators?

A. The vector automatically sorts itself

B. The vector may reallocate its storage

C. Iterators work only with maps

D. Insertion always deletes the first element

Correct Answer: B. The vector may reallocate its storage

Question 8

Which container maintains unique keys in sorted order?

A. std::set

B. std::unordered_set

C. std::vector

D. std::queue

Correct Answer: A. std::set

Question 9

What is the main benefit of a lazy range view?

A. It always duplicates the source container

B. It can process elements without immediately creating a new container

C. It guarantees constant-time sorting

D. It disables iterator operations

Correct Answer: B. It can process elements without immediately creating a new container

Question 10

Which operation is required by std::sort?

A. Forward iterators only

B. Input iterators only

C. Random-access iterators

D. Output iterators only

Correct Answer: C. Random-access iterators