Rubric: No raw loops
{
int r = a < b ? a : b;
}
{
// r is the minimum of a and b
int r = a < b ? a : b;
}
{
int r = min(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);
capacity
empty
(ambiguous but used by convention)is_blue
partition
a = sort(b)
not a = sorted(b)
set_
, i.e. set_capacity
intersection(a, b)
not calculate_intersection(a, b)
name
not get_name
/// Returns the truncated square root of `x`. `x` must be >= 0.
int sqrti(int x);
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.
{
vector a{0, 0, 1, 0, 1 };
erase(a, a[0]);
}
a
after this code?{
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.
/// Transmogrify the elements in the range [f, l).
template <class ForwardIterator>
void transmogrify(ForwardIterator f, ForwardIterator l);
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.
{
/// 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);
}
[f, l]
?(f, l)
?[f, l)
[p, p)
represents an empty range, at position p
[INT_MIN, INT_MAX)
with type intf
in a sequence can be denoted with an index, pointer, or iteratorf
be incrementable to obtain the next element in the sequence[f, l)
[f, f + n) _n
[f, predicate()) _until
[f, is_sentinel())
NTBSconst char*
[f, ...)
unbounded (dependent on something else)a
in C and C++, it is guaranteed that &a + 1
yields a valid, but not dereferenceable, pointer[&a, &a + 1)
is a valid rangefind(f, l, a)
returns the position of the first element in the range [f, l)
that is equal to a
.{
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?
[f, l)
must form a valid rangevalue_type
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
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, 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
[f, l)
must form a valid range is a preconditionf(int* p)
with the precondition that p
is dereferenceableThe result of
find(f, l, v)
is an iterator within the range[f, l)
.
Is a postcondition of find()
.
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/note pre-/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
std::basic_string()
only guarantees the value of a moved-from string is validstd::merge()
currently requires a strict-weak orderingstd::fill()
, std::iota()
and std::generate()
would be better expressed with output iterators and sink function forms: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<int> v;
bcc::iota(0, 10, [&](int n) { v.push_back(n); });
display(v);
}
{
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<int> 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?
pred
is a regular, pure, function although the standard wording is obtuse:Given a glvalue
u
of type (possiblyconst
)T
that designates the same object as*first
,pred(u)
shall be a valid expression that is equal topred(*first)
.
rotate
reverse
swap
, swap_ranges
shuffle
next_permutation
remove_if()
, many algorithms in the standard library are implemented in terms of other algorithms in the libraryswap_ranges()
and reverse()
are the worst case, where every cycle is length 2 and requires 3 movesn
elements requires (n / 2) * 3
movesswap()
Exercise: Write an algorithm, swirl()
, that implements the following single cycle permutation.
namespace v0 {
template <class I>
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 <class I>
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);
}
swirl
computes the mid-point, so it is a good thing to returnstd::reverse()
throws it away!)namespace v2 {
template <class I>
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
partition
& stable_partition
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.
sort
, stable_sort
, & partial_sort
nth_element
make_heap
Comparison permutations use a comparison function to map an ordering of the values to an ordering of their position
\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}An ordering relation, $\prec$, is a strict-weak ordering iff
Where $a$ and $b$, are equivalent, $\equiv$, iff $(a \nprec b) \wedge (b \nprec a)$.
operator<()
operator<()
is a total orderingA total ordering is a strict-weak ordering where the defined equivalence is equality
operator<()
is not defined on std::complex<>
because there is no definition consistent with multiplicationnan
values, both float
and double
are totally-ordered because nan
is explicitly outside the value domain for floating point typesnan
is not a numbernan
is partially formednan
values with operator<()
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.
sort
and nth element
operations establish a direct relationship between the order of elements and their position in the sequence.make_heap
orders the elements as a max heapmake_heap
, and the related heap operation are included in the standard library because they are used by sort
sort
in the standard library is an introsort, which is an introspective quicksort that switches to heap sort when the recursion depths exceeds a level $k \cdot log(n)$nth_element
sorts a sequence enough so that the specified element is in the correct locationnth_element
is that the sequence is partitions such that every element before the nth element is less than or equal to it, and every element after is greater than or equal.nth_element
and partial_sort
you can sort a subrange of a sequence as if the entire range where sortedtemplate <class I> // I models RandomAccessIterator
void sort_subrange_0(I f, I l, I sf, I sl) {
std::sort(f, l);
}
template <class I> // 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);
}
lower_bound
, upper_bound
, equal_range
, binary_search
merge
includes
, set_difference
, set_intersection
, set_symmetric_difference
, set_union
lower_bound
should is the most commonly used way to do a binary search for an element in a sequence{
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";
}
{
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"
make_heap
, push_heap
, pop_heap
, sort_heap
priority_queue
Exercise: Create a priority_queue
of my_type
.
Exercise: Create a new priority_queue
adapter that supports move using the heap operations.