Notebook slides (original) (raw)

Algorithms

Rubric: No raw loops

{ int r = a < b ? a : b; }

{ // r is the minimum of a and b int r = a < b ? a : b; }

/// Returns the minimum of two integers int min(int a, int b) { return a < b ? a : b; }

/// Returns the minimum of two integers int min(int a, int b);

Naming a Function (Guidelines)

Specifying a Function

/// Returns the truncated square root of `x`. `x` must be >= 0.
int sqrti(int x);

Argument Types

spans, views, iterator pairs, and so on are a way to pass a range of objects as if they were a simple argument. The value_type of the range determines if it is in (const), or inout (not const) with input ranges (input iterators) used for sink.

Implicit Preconditions

Object Lifetimes

Validity

Law of Exclusivity

{ vector a{0, 0, 1, 0, 1 }; erase(a, a[0]); }

{ vector a{0, 0, 1, 0, 1 }; erase(a, a[0]); display(a); }

This fails because a[0] is passed by a reference aliasing the vector, a. The standard is inconsistent in how it deals with aliasing with mutations. Unless aliasing is explicitly allowed, avoid it.

{ vector a{0, 0, 1, 0, 1 }; erase(a, copy(a[0])); display(a); }

The Law of Exclusivity is borrowed from Swift, and the term was coined by John McCall. To modify a variable, exclusive access to that variable is required. C++ does not enforce this rule; it must be manually enforced.

The Law of Exclusivity has far greater implications outside the scope of this talk. You might be interested in learning about the Val language.

Ranges

/// Transmogrify the elements in the range [f, l). template void transmogrify(ForwardIterator f, ForwardIterator l);

Implicit Postconditions

Validity of References

Any reference (pointer, iterator, etc.) to an object is assumed to be invalidated if the object is mutated.

A returned reference must be to one of the arguments to the function (or a part of one of the arguments) and is valid until the argument is modified or its lifetime ends.

Loops and Recursion

{ /// removes values equal to a in the range [f, l) /// returns the position, b, such that [f, b) contains all the values in [f, l) not equal to a /// values in the range [b, l) are unspecified auto remove = [](auto f, auto l, const auto& a) { auto b = find(f, l, a); if (b == l) return b; auto p = next(b); // invariant: all values in the range [f, b) do not equal x // decreasing: distance(p, l) while (p != l) { if (*p != a) { *b = std::move(*p); ++b; } ++p; } return b; };

vector a{ 0, 0, 1, 0, 1 };
a.erase(remove(begin(a), end(a), 0), end(a));

display(a);

}

Sequences

Sequence 1
Sequence With Pointers To Objects

Sequence 2
Sequence With Pointers Between Objects

Common algorithms and their uses

Generic Algorithms

{ int a[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; display(*find(begin(a), end(a), 5)); }

Question: How do we know find() will find a value?

Requirements and Guarantees

Concept

The term concept first appeared in the paper Fundamentals of Generic Programming:

We call the set of axioms satisfied by a data type and a set of operations on it a concept.

— Fundamentals of Generic Programming, Dehnert & Stepanov

In C++20, a language concept is a set of syntactic requirements with a set of specified, in documentation, semantic and complexity requirements.

Names should not be associated with semantics because everybody has their own hidden assumptions about what semantics are, and they clash, causing comprehension problems without knowing why. This is why it's valuable to write code to reflect what code is actually doing, rather than what code "means": it's hard to have conceptual clashes about what code actually does.

— Craig Silverstein, personal correspondence

Model

We say that a concept is modeled by specific types, or that the type models the concept, if the requirements are satisfied for these types.

Contracts

Contracts, or Design by Contract, is a systematic approach to ensuring the values passed to, and returned by an operation satisfy specific assertions.

If the execution of a certain task relies on a routine call to handle one of its subtasks, it is necessary to specify the relationship between the client (the call- er) and the supplier (the called routine) as precisely as possible. The mechanisms for expressing such conditions are called assertions. Some assertions, called preconditions and postconditions, apply to individual routines. Others, the class invariants, constrain all the routines of a given class...

— Applying "Design by Contract", Bertrand Meyer

Precondition

Postcondition

The result of find(f, l, v) is an iterator within the range [f, l).

Is a postcondition of find().

Class Invariant

Concepts, Partial Functions, and Domain

Compare the description for the old SGI STL LessThanComparable concept:

Expression semantics

Name Expression Precondition Semantics Postcondition
Less x < y x and y are in the domain of <

versus the C++17 concept.

Table 28: CppLessThanComparable requirements

Expression Return type Requirement
a < b convertible to bool < is a strict weak ordering relation

In the SGI STL the requirement of strict-weak-ordering was a separate concept.

Domain is defined in the C++ standard, but in the context of iterators. This passage used to refer to the domain of operations, but that has been narrowed to the domain of ==:

The term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined. This set can change over time. Each algorithm places additional requirements on the domain of == for the iterator values it uses. These requirements can be inferred from the uses that algorithm makes of == and !=.

Expression Return type Operational Semantics Assertion/notepre-/post-condition
a != b contextually convertible to bool !(a == b) Preconditions: (a, b) is in the domain of ==

What was part of the definition of concepts in general has been weakened to a requirement for a single operation on iterators.

The term domain of the operation is used in the ordinary mathematical sense to denote the set of values over which an operation is (required to be) defined. This set can change over time. Each component may place additional requirements on the domain of an operation. These requirements can be inferred from the uses that a component makes of the operation and is generally constrained to those values accessible through the operation’s arguments.

A partial function is a function whose domain is a subset of the values for the type of the operands

Axes of Freedom

OutputIterators and sink functions

namespace bcc {

template <class T, class F> constexpr void iota(T first, T last, F out) { for (; first != last; ++first) { out(first); } }

} // namespace bcc

{ vector v; bcc::iota(0, 10, [&](int n) { v.push_back(n); }); display(v); }

Algorithm Semantics

{ vector a{0, 1, 2, 3, 4, 5};

erase_if(a, [n = 0](int x) mutable {
    return (x & 1) && !n++;
});
display(a);

}

Question: What went wrong?

template <class F, class P> auto remove_if(F f, F l, P pred) { f = find_if(f, l, pred); // <-- pred is passed by value

if (f == l) return f;

for (auto p = next(f); p != l; ++p) {
    if (!pred(*p)) *f++ = move(*p);
}
return f;

}

{ vector a{0, 1, 2, 3, 4, 5};

int n = 0;
auto first_is_odd = [&n](int x) {
    return (x & 1) && !n++;
};

erase_if(a, first_is_odd);
display(a);

}

Question: Does the above code fix the issue?

Given a glvalue u of type (possibly const) T that designates the same object as *first, pred(u) shall be a valid expression that is equal to pred(*first).

Positional Permutations

Reverse Cycles
Reverse Cycles

Exercise: Write an algorithm, swirl(), that implements the following single cycle permutation.

Swirl Cycles
Swirl

Swirl (Even)
Swirl (Even)

namespace v0 {

template void swirl(I f, I l) { auto m = next(f, distance(f, l) / 2); if (f == m) return; m = rotate(f, m, l); reverse(m, l); ++f; reverse(f, m); }

} // namespace v0

{ using namespace v0;

int a[]{0, 1, 2, 3, 4, 5, 6, 7, 8};
swirl(begin(a), end(a));

display(a);

}

Question: What are the requirements for I, f, and l?

namespace v1 {

template void swirl(I f, I l) { reverse(f, l); auto m = next(f, distance(f, l) / 2); if (m == l) return; rotate(f, m, next(m)); }

} // namespace v1

{ using namespace v1;

int a[]{0, 1, 2, 3, 4, 5, 6, 7, 8};
swirl(begin(a), end(a));

display(a);

}

namespace v2 {

template I swirl(I f, I l) { reverse(f, l); auto m = next(f, distance(f, l) / 2); if (m == l) return m; rotate(f, m, next(m)); return m; }

} // namespace v1

Homework: Implement swirl with the minimum number of moves

Predicate Permutations

Predicate permutations use a predicate function to determine ordering. These algorithms partition the set into two sets. A stable partition algorithm preserves the relative order of the elements in each set.

Comparison Permutations

Comparison permutations use a comparison function to map an ordering of the values to an ordering of their position

An ordering relation, prec\precprec, is a strict-weak ordering iff

\begin{align} (a & \nprec a). && \text{(Irreflexivity)} \\ (a & \prec b) \wedge (b \prec c) \implies a \prec c. && \text {(Transitivity)} \\ (a & \equiv b) \wedge (b \equiv c) \implies a \equiv c. && \text {(Equivalence Transitivity)}\\ \end{align}

Where aaa and bbb, are equivalent, equiv\equivequiv, iff (anprecb)wedge(bnpreca)(a \nprec b) \wedge (b \nprec a)(anprecb)wedge(bnpreca).

A total ordering is a strict-weak ordering where the defined equivalence is equality

C++20 defines the ordering on floating-point types as a std::partial_ordering because of nan values. I find this complicates matters unnecessarily, and means the requirements of the comparison operator cannot be defined with a concept but require a precondition. See prior discussion of domain of an operation.

template // I models RandomAccessIterator void sort_subrange_0(I f, I l, I sf, I sl) { std::sort(f, l); }

template // I models RandomAccessIterator void sort_subrange(I f, I l, I sf, I sl) { if (f != sf && sf != l) { std::nth_element(f, sf, l); // partition [f, l) at sf ++sf; } std::partial_sort(sf, sl, l); }

Operations on sorted sequences

{ int a[]{ 0, 1, 2, 3, 3, 3, 4, 4, 5, 6 }; auto p = lower_bound(begin(a), end(a), 3); display(a); cout << string(distance(begin(a), p) * 3 + 1, ' ') << "^\n"; }

Projections

{ struct employee { string _first; string _last; };

employee a[]{{"Joe", "Zimmer"}, {"Frank", "Berse"}};

sort(begin(a), end(a), [](const employee& a, const employee& b) {
    return a._last < b._last;
});
auto p = lower_bound(begin(a), end(a), "Zimmer"s, [](const employee& a, const string& b) {
    return a._last < b;
});

display(p->_first);

}

{ struct employee { string _first; string _last; };

employee a[]{{"Joe", "Zimmer"}, {"Frank", "Berse"}};

ranges::sort(a, less<>(), &employee::_last);
auto p = ranges::lower_bound(a, "Zimmer"s, less<>(), &employee::_last);

display(p->_first);

}

"Joe"

Iterator hierarchy (and why you probably shouldn't care)

Composition vs. multi-pass

Generators vs input iterator

Heap operations

Exercise: Create a priority_queue of my_type.

Exercise: Create a new priority_queue adapter that supports move using the heap operations.