Standard Library, Algorithms, and Functional Features

Introduction

Modern C++ programming is not limited to defining classes and managing memory manually. The Standard Library provides tested, reusable components for representing data, traversing collections, transforming values, performing input/output, handling time, and expressing operations as functions. Effective use of these facilities is central to professional mechatronics software, where programs may process sensor samples, communicate with devices, log measurements, schedule operations, and analyze experimental data.

The central design principle of this chapter is separation of data structures from operations. A container stores data; an iterator or range provides access to that data; an algorithm performs a general operation; and a callable object specifies application-specific behavior. This separation improves reuse and makes complexity visible.

Learning Objectives

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

• select appropriate standard containers for engineering tasks;
• use strings, iterators, ranges, and standard algorithms safely;
• write and compare lambdas, function objects, and function pointers;
• represent multiple return values and uncertain or alternative results using tuple, optional, and variant;
• use time utilities, streams, and files in reliable programs;
• evaluate time and space complexity and explain container trade-offs;
• design a small standard-library-based application for a mechatronics system.

1. The Standard Library as a Design Framework

The C++ Standard Library includes several interacting families:

The library is governed by requirements such as ownership, validity, ordering, and complexity. A function that receives two iterators generally operates on a half-open range [first, last): the first iterator is included and the second marks one position beyond the final element. This convention supports empty ranges because first == last is valid.

Complexity notation

Algorithmic efficiency is commonly described using Big-O notation. If an operation processes n elements, O(n) means its running time grows approximately in proportion to n; O(log n) describes logarithmic growth; and O(n²) describes quadratic growth. Big-O ignores constant factors and lower-order terms, so it is a growth-rate model rather than an exact execution-time prediction.

For example, binary search on a sorted random-access sequence has complexity O(log n), whereas linear search has complexity O(n). Complexity does not replace measurement: cache behavior, allocation, hardware, and input distribution also affect performance.

2. Strings and Text Processing

std::string owns a mutable sequence of characters. It is appropriate when a program must store, modify, or return text. Common operations include size(), empty(), find(), substr(), append(), and comparison.

#include <string>
#include <iostream>

int main() {
    std::string message = "Motor temperature: 42.5 C";
    auto position = message.find("temperature");
    if (position != std::string::npos)
        std::cout << message.substr(position) << '\n';
}

std::string::npos is a special value indicating that a search failed. A frequent error is comparing the result of find with zero rather than checking against npos.

std::string_view provides a non-owning view of character data. It is efficient for function parameters because it normally avoids copying:

#include <string_view>

bool isCommand(std::string_view text) {
    return text == "START" || text == "STOP";
}

A view must not outlive the characters to which it refers. Returning a string_view referring to a local std::string creates a dangling reference. Similarly, storing a view of a temporary or of a string that is later reallocated is unsafe.

Text parsing often requires deliberate treatment of whitespace, delimiters, numeric conversion, and invalid input. Functions such as std::from_chars support low-level, locale-independent numeric conversion and do not throw exceptions. Stream extraction is more convenient but may require checking stream state.

3. Containers and Their Trade-offs

Sequence containers

std::array<T, N> has a fixed size known at compile time and stores elements contiguously. It is useful for fixed sensor channels, coordinate vectors, and calibration coefficients. std::vector<T> is a dynamically sized contiguous sequence and is the default choice for many collections.

A vector provides constant-time average access by index, written O(1). Appending at the end is amortized O(1): occasional reallocations are expensive, but the average cost over many insertions remains constant. Inserting or erasing in the middle is O(n) because subsequent elements may need to move.

std::deque<T> supports efficient insertion at both ends and indexed access, but its storage is not one contiguous block. std::list<T> provides constant-time insertion or erasure at a known position, but each element typically requires a separate node and pointer links. Consequently, lists often have poor cache locality and should not be selected merely because insertion is theoretically O(1).

Associative containers

std::map<Key, T> stores sorted key-value pairs, usually in a balanced tree. Search, insertion, and erasure are O(log n). std::set stores unique sorted keys. These containers support ordered traversal and range queries.

std::unordered_map and std::unordered_set use hashing. Their average search, insertion, and erasure complexity is O(1), while the worst case is O(n). Performance depends on a suitable hash function, load factor, and allocation behavior. They do not provide sorted iteration.

Container selection

The correct choice depends on access patterns, stability of references, memory limits, real-time requirements, and whether deterministic worst-case behavior is needed. A hash table’s average complexity is not a guarantee of bounded latency, which may matter in control systems.

4. Iterators, Ranges, and Algorithms

An iterator behaves conceptually like a generalized pointer. It allows an algorithm to operate on many containers without knowing their internal representation. Examples include begin, end, cbegin, and cend.

#include <algorithm>
#include <vector>

std::vector<int> values{8, 3, 10, 4};
std::sort(values.begin(), values.end());

Algorithms include:

• non-modifying operations: find, count, all_of, any_of, none_of;
• modifying operations: copy, fill, replace, transform;
• ordering operations: sort, stable_sort, partial_sort;
• partitioning operations: partition, stable_partition;
• numerical operations: accumulate, reduce, and inner_product.

std::sort requires random-access iterators, such as those from vector and array. It cannot directly sort a list; list::sort() must be used instead. std::find works with weaker iterator categories and is therefore more general.

The C++20 ranges library expresses algorithm inputs more directly:

#include <algorithm>
#include <ranges>
#include <vector>

std::vector<int> readings{4, 9, 2, 11};
auto result = std::ranges::find(readings, 9);
std::ranges::sort(readings);

Ranges reduce errors involving mismatched iterator pairs and support composable views. A view is generally lazy: it describes a computation without immediately creating a new container.

#include <ranges>
#include <vector>

std::vector<int> readings{10, 21, 30, 41};
for (int x : readings | std::views::filter([](int v) { return v > 20; }))
    std::cout << x << ' ';

A view may refer to its source, so the source must remain alive while the view is used. Lazy pipelines are expressive, but repeated traversal or complex pipelines should be measured in performance-sensitive code.

Algorithm preconditions and invalidation

Algorithms often have preconditions. binary_search requires a sorted range under the same ordering used for the search. unique only removes consecutive equivalent elements, so sorting may be necessary before using it to remove all duplicates.

Container modifications can invalidate iterators and references. Reallocation of a vector invalidates all iterators, pointers, and references to its elements. Erasing an element invalidates the erased position and, for a vector, later positions. Good practice is to perform modifications through the iterator returned by the operation when an algorithm provides one.

5. Lambdas and Callable Objects

A callable is anything that can be invoked using function-call syntax. It may be a free function, function pointer, lambda expression, function object, or an object implementing operator().

A lambda has the general form:

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

The return type is often inferred. Captures may be by value ([x]), by reference ([&x]), all by value ([=]), or all by reference ([&]). Explicit captures are usually safer and clearer.

std::vector<double> temperatures{18.0, 25.5, 31.2, 27.4};
const double limit = 30.0;
auto hot = std::count_if(temperatures.begin(), temperatures.end(),
                         [limit](double t) { return t > limit; });

The lambda captures limit by value, so its behavior does not depend on later changes to the original variable. Capturing by reference is appropriate when the callable is used immediately and the referenced object remains alive. It is dangerous when a lambda is returned or stored for later execution.

A function object can hold state explicitly:

struct Scaler {
    double factor;
    double operator()(double value) const { return factor * value; }
};

Function objects can be more descriptive than complex lambdas and may be optimized effectively. std::function<R(Args...)> stores an arbitrary compatible callable, but it can involve type-erasure overhead and possible allocation. Use templates or auto when maximum performance and compile-time type information are important.

6. Tuples, Optional Values, and Alternatives

std::pair and std::tuple group values of possibly different types. Structured bindings improve readability:

std::tuple<int, double, std::string> sample{7, 2.5, "OK"};
auto [channel, value, status] = sample;

Tuples are useful for compact internal results, but a named structure is often clearer for a public interface because each field has a meaningful name.

std::optional<T> represents either a value of type T or no value. It is appropriate when absence is a normal, non-exceptional result:

std::optional<double> readPressure(bool sensorReady) {
    if (!sensorReady) return std::nullopt;
    return 101.3;
}

The caller should test the result before dereferencing it. value_or(defaultValue) provides a fallback. optional does not explain why a value is absent; if failure causes must be represented, an error type or a result-like design may be preferable.

std::variant<Ts...> stores exactly one alternative from a specified set. It is useful for messages that may contain different valid forms:

std::variant<int, double, std::string> message = 24.5;
std::visit([](const auto& item) { std::cout << item << '\n'; }, message);

std::get<T> retrieves a type alternative and can throw std::bad_variant_access if the active alternative is different. std::get_if<T> returns a pointer or nullptr. A visitor can provide type-specific behavior without unsafe casts.

7. Time Utilities and Measurement

The <chrono> library separates clocks, durations, and time points. A duration represents an interval; a time point represents an instant relative to a clock’s epoch. steady_clock is suitable for measuring elapsed time because it is monotonic and is not adjusted by system-clock changes. system_clock represents calendar time and is suitable for timestamps.

#include <chrono>
#include <iostream>

using namespace std::chrono;
auto start = steady_clock::now();
// operation being measured
volatile int result = 0;
for (int i = 0; i < 100000; ++i) result += i;
auto finish = steady_clock::now();
auto elapsed = duration_cast<microseconds>(finish - start);
std::cout << elapsed.count() << " microseconds\n";

The measurement includes the clock calls and may be affected by compiler optimization, operating-system scheduling, cache state, and background activity. Reliable benchmarking requires repeated trials, representative data, and prevention of dead-code elimination. A duration conversion may truncate; use floating-point duration when fractional units are important.

For periodic control tasks, a monotonic clock and an explicit deadline strategy are safer than repeatedly sleeping for a fixed duration, because work time and scheduling delay accumulate. Hard real-time guarantees cannot be inferred solely from use of chrono.

8. Streams and Files

The standard stream objects include std::cin, std::cout, std::cerr, and std::clog. Formatted extraction parses according to type:

int channel;
double voltage;
if (std::cin >> channel >> voltage) {
    // input is valid
} else {
    std::cerr << "Invalid input\n";
}

After a failed extraction, the stream enters a failure state. Recovery generally requires clearing the state and discarding invalid characters, for example with clear() and ignore().

std::ifstream reads files and std::ofstream writes them. Always check that a file opened successfully and specify an appropriate mode. Text files are portable and inspectable; binary files can be smaller and faster but require careful treatment of representation, byte order, padding, and version compatibility.

#include <fstream>
#include <string>

std::ofstream log("measurements.csv");
if (!log) throw std::runtime_error("Cannot open log file");
log << "time_ms,temperature\n";
log << 1250 << ',' << 31.4 << '\n';

A robust logger should define its format, units, timestamp convention, precision, failure behavior, and file-rotation policy. Never construct a filename directly from untrusted user input without validation; path traversal can expose or overwrite protected files.

9. Integrated Application: Sensor Monitoring Pipeline

The following is an illustrative case study rather than a claim about a particular commercial product.

Background and problem

A small mobile robot has temperature sensors identified by channel name. Measurements arrive as records containing a sensor identifier, a timestamp, and a value. The software must reject invalid records, identify overheating sensors, retain readings, calculate a summary, and write a CSV report.

Analysis

A vector is appropriate for chronological readings because measurements are appended and later traversed. An unordered_map is suitable for quick lookup of the latest value by sensor name. optional can represent an unavailable latest reading. A lambda can define the alarm predicate. steady_clock is appropriate for measuring processing duration, while a system timestamp may be written to a log.

#include <algorithm>
#include <fstream>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>

struct Reading {
    std::string sensor;
    long long time_ms;
    double celsius;
};

class Monitor {
    std::vector<Reading> history;
    std::unordered_map<std::string, double> latest;
public:
    void add(Reading r) {
        if (r.sensor.empty()) return;
        if (r.celsius < -40.0 || r.celsius > 150.0) return;
        latest[r.sensor] = r.celsius;
        history.push_back(std::move(r));
    }

    std::optional<double> latestValue(const std::string& sensor) const {
        auto it = latest.find(sensor);
        if (it == latest.end()) return std::nullopt;
        return it->second;
    }

    std::size_t countHot(double limit) const {
        return std::count_if(history.begin(), history.end(),
            [limit](const Reading& r) { return r.celsius > limit; });
    }

    void writeCsv(const std::string& filename) const {
        std::ofstream out(filename);
        if (!out) throw std::runtime_error("Output cannot be opened");
        out << "sensor,time_ms,celsius\n";
        for (const auto& r : history)
            out << r.sensor << ',' << r.time_ms << ',' << r.celsius << '\n';
    }
};

Outcome and evaluation

Appending to history is amortized O(1). Average latest-value lookup in the unordered map is O(1), with O(n) worst-case behavior. Counting hot readings is O(n) for n stored records, and writing the report is also proportional to the amount of output. Memory use is O(n + s), where s is the number of distinct sensor identifiers.

The design is readable and suitable for a non-real-time logger. For a hard real-time controller, dynamic allocation, file I/O, hash-table latency, and exception behavior would require stricter analysis. A bounded ring buffer, preallocated storage, and a separate non-real-time logging task might be preferable.

Learning points

The case demonstrates that standard-library choices encode requirements. The vector expresses chronological storage, the hash map expresses key lookup, the lambda expresses a policy, optional expresses absence, and the stream expresses a text boundary. Good design also documents validation limits and units instead of treating library components as a substitute for system engineering.

10. Limitations, Safety, and Best Practices

The Standard Library is powerful but does not automatically make software safe. Common hazards include dangling views, iterator invalidation, unchecked stream states, accidental signed/unsigned conversions, integer overflow, data races, and excessive dynamic allocation.

Recommended practices include:

1. Prefer the simplest container whose complexity and ownership semantics satisfy the requirement.
2. Use algorithms and ranges instead of handwritten loops when they improve clarity.
3. Make lambda captures explicit, especially for callbacks stored beyond the current scope.
4. Treat input as untrusted: validate syntax, range, units, and file paths.
5. Check optional and variant states before access.
6. Use steady_clock for elapsed-time measurement.
7. Document iterator, pointer, and reference validity assumptions.
8. Benchmark representative workloads rather than relying only on Big-O analysis.
9. Separate deterministic control logic from logging, parsing, and other potentially blocking tasks.
10. Compile with warnings and sanitizers during testing, and use static analysis where available.

In safety-related mechatronics, software libraries must be considered within the applicable organizational and industry assurance process. A standard function's correctness does not by itself establish system safety; requirements, testing, traceability, fault handling, and verification remain necessary.

Contemporary Developments

C++20 ranges and concepts improve algorithm interfaces and express constraints at compile time. C++23 adds further range and utility facilities, although compiler and library support varies. Parallel algorithms can exploit multiple execution resources, but they require attention to data races, determinism, scheduling overhead, and real-time interference. Standard library evolution therefore offers productivity gains while preserving the need for engineering judgment.

Chapter Summary

The C++ Standard Library provides a coherent model in which containers store data, iterators and ranges expose it, algorithms perform general operations, and callables supply customizable behavior. vector is a strong default for contiguous sequences; ordered and unordered associative containers serve different lookup and ordering requirements. Strings require ownership and lifetime awareness, while string_view avoids copying but does not own data.

Algorithms such as search, sort, transform, and counting reduce repetitive code, but their preconditions and iterator invalidation rules must be understood. Lambdas and function objects express policies compactly. tuple, optional, and variant represent grouped, absent, and alternative values. Chrono separates clocks, durations, and time points. Streams and files provide practical I/O but require validation and error handling. Complexity analysis, measurement, determinism, safety, and application requirements should guide all library choices.

Key Terms

Container: An object that stores a collection of values.

Iterator: An abstraction used to traverse elements in a data structure.

Range: A sequence described by a beginning and an endpoint, commonly [first, last).

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

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

Callable: An entity that can be invoked using function-call syntax.

Predicate: A callable that returns a Boolean result.

vector: A dynamically sized contiguous sequence container.

map: An ordered key-value associative container.

unordered_map: A hash-based associative container.

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

string_view: A non-owning view of character data.

tuple: A fixed-size grouping of potentially different types.

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

variant: A type containing exactly one value from a specified set of alternatives.

Duration: A measured interval of time.

Time point: An instant associated with a clock.

Stream: An abstraction for sequential input or output.

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

Big-O notation: A description of asymptotic growth as input size increases.

Review Questions

Short Answer Questions

1. Why is vector often preferred over list even when middle insertion is required occasionally?
2. What lifetime danger is associated with string_view?
3. What is the purpose of the half-open range [first, last)?
4. When should steady_clock be used instead of system_clock?
5. What does optional communicate to a caller?

Long Answer Questions

1. Compare vector, deque, list, map, and unordered_map in terms of storage, access, ordering, and complexity.
2. Explain how lambdas, function objects, and std::function differ and identify a suitable use for each.
3. Discuss iterator invalidation and explain why it matters in an algorithm-based program.
4. Describe reliable file-input and file-output practices for an engineering data logger.
5. Explain how ranges and views improve expressiveness, and discuss their lifetime and performance considerations.

Analytical / Application Questions

1. Design a container and algorithm strategy for a robot that stores 100,000 timestamped readings, frequently appends new readings, and occasionally searches by timestamp. Justify the trade-offs.
2. A control application requires bounded response time while also logging measurements to disk. Analyze why direct file output from the control loop may be unsuitable and propose an architecture.
3. Develop a validation and processing plan for sensor messages that may contain an integer command, a floating-point measurement, or an error string. Explain how variant, visit, optional, and stream or character parsing could be combined.

Multiple Choice Questions with Answers

Question 1

Which container provides contiguous storage and amortized constant-time insertion at the end?

A. std::vector

B. std::list

C. std::map

D. std::set

Correct Answer: A. std::vector

Question 2

What does std::string_view own?

A. A dynamically allocated copy of characters

B. The original string object

C. Nothing; it is a non-owning view

D. A null-terminated array in all cases

Correct Answer: C. Nothing; it is a non-owning view

Question 3

Which clock is most appropriate for measuring elapsed processing time?

A. std::system_clock

B. std::steady_clock

C. std::clock_t only

D. A calendar date type

Correct Answer: B. std::steady_clock

Question 4

What does std::optional<double> represent?

A. Two doubles simultaneously

B. Only an exception

C. A double or no value

D. A double and an integer key

Correct Answer: C. A double or no value

Question 5

What is the average complexity of lookup in an unordered_map?

A. O(1)

B. O(log n)

C. O(n log n)

D. O(n²)

Correct Answer: A. O(1)

Question 6

Which algorithm requires a sorted range as a precondition?

A. std::binary_search

B. std::fill

C. std::count

D. std::for_each

Correct Answer: A. std::binary_search

Question 7

What is the principal risk of capturing a local variable by reference in a stored lambda?

A. The lambda cannot be called

B. The reference may dangle after the variable's lifetime ends

C. The lambda always copies the variable

D. The program becomes automatically thread-safe

Correct Answer: B. The reference may dangle after the variable's lifetime ends

Question 8

Which type stores exactly one active alternative from a specified set of types?

A. std::tuple

B. std::optional

C. std::variant

D. std::array

Correct Answer: C. std::variant

Question 9

What does the second iterator in a conventional half-open range represent?

A. The first element twice

B. The final included element

C. One position beyond the final element

D. A required null pointer

Correct Answer: C. One position beyond the final element

Question 10

Why might a hard real-time task avoid direct file output?

A. Files cannot contain numbers

B. File output may block and have unpredictable latency

C. Streams only work with strings

D. The Standard Library forbids output in embedded systems

Correct Answer: B. File output may block and have unpredictable latency