Module 14 — Misconceptions and Mistakes¶

Two different problems, fixed two different ways.

A misconception is a wrong mental model, and only evidence removes it — so each one below is paired with the program or measurement that contradicts it. A mistake is a concrete error, and information fixes it — so each one below comes with the message this toolchain actually printed and the corrected code.

Every diagnostic quoted here was produced by compiling the snippets shown, with the course's flags.

Part 1 — Misconceptions¶

1. "`std::remove` removes elements."¶

It is named remove, and it does not remove anything — it cannot. It takes iterators, and iterators cannot change a container's size. What it does is move the elements to keep to the front and return the position that is now the logical end. Until erase runs on that position, the size is unchanged and the "removed" elements are still in the container:

before:                        . . . . .   [size 5]
after remove_if, before erase: keepers, removed, removed   [size 5]
after erase:                   keepers   [size 3]

The corrected form is one expression, and reading it as a sentence is what makes it memorable:

loans.erase(std::remove_if(loans.begin(), loans.end(), isReturned), loans.end());
// collapse the keepers to the front, then destroy from there to the end

2. "Modifying a container while iterating is fine if the program works."¶

It works on small inputs, because invalidation needs a reallocation, and a reallocation needs a growth past the current capacity:

capacity after each push_back: 1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32
buffer replaced 5 time(s) over 17 insertions

Five replacements in seventeen insertions — so a ten-element test has a good chance of never reallocating and never failing. The rule is not "it works"; it is did anything modify the container between obtaining the iterator and using it? — and if the answer is yes, the pointer, reference or iterator you hold is not something you may use.

3. "`unordered_map` is always faster than `map`."¶

Average-constant beats logarithmic on average, and the qualifier is doing real work:

std::map::find:               18 comparison(s)
std::unordered_map::find:      1 comparison(s), 1 hash(es)
...
with a hash that returns 0 for every key:
  comparisons for one lookup of the FIRST key: 632

A map guarantees O(log n) whatever the data. A hash map guarantees average O(1) and degrades to O(n) when the hash does not distribute — and the degradation depends on the values, on insertion order and on the growth history. It is also the wrong container the moment you need order: unordered_map cannot answer "the next ten loans due", because there is no next.

4. "I can hash any type by hashing one field."¶

It produces a number, and the number must satisfy three properties, in order: deterministic, consistent with ==, well distributed. Only the second is a correctness requirement, and it is the one that is easy to break — by simplifying the equality and forgetting the hash:

equality compares the id only; the hash uses id + title + edition.
size after inserting four books: 4
lookup of #1 Compilers (ed. 9), which is EQUAL to both compilers:
  NOT FOUND

Four keys where the equality says three, and a lookup that misses for a record the container holds. Nothing reports it. Fix the hash to use exactly the fields the equality uses — or decide the extra fields are not part of the identity, and change the equality to match.

5. "Lambdas capture everything they mention."¶

They capture exactly what the capture list says, and nothing else. [limit] gives the closure a copy of limit; if the body then mentions title, it does not compile, and the error is about title. This is a feature: the capture list is the closure's member list, and reading it tells you what the lambda owns, what it borrows, and therefore what has to stay alive.

6. "Capturing by reference is more efficient, so prefer it."¶

It avoids a copy, and it creates a dependency on a lifetime that the lambda does not control. A by-value capture is always safe to store; a by-reference capture is safe only while the captured variable lives, which in practice means until the end of the statement that uses the lambda.

std::function<int()> makeCounter() {
    int count = 0;
    return [&count] { return ++count; };   // compiles; the reference outlives the int
}

The compiler tracks the lambda's lifetime, not the captured variable's, so this is silent. Prefer by value whenever the lambda is stored, returned, or called later — and when you do want shared ownership, capture a shared_ptr by value, which the example program shows keeping an object alive past its block.

7. "`string_view` is a faster `string`."¶

It is not a string at all. It is a pointer and a length — a view — and it owns nothing:

void printTitle(std::string_view title);       // no copy: works with string, char*, literal

That is what makes it cheap to pass and dangerous to return. std::string_view dangerous = firstTitle(); where firstTitle built a local std::string compiles, looks harmless, and points at storage that no longer exists. The rule: a function may return a string_view only when it can point at the owner in the same sentence — a member, a parameter, a global, a literal.

8. "`std::optional` is just an exception you can ignore."¶

It is the right return type for an expected outcome, and the wrong one for a failure. find answers "is this here?" and a no is a perfectly good answer; require answers "give me this", and that cannot be satisfied — which is what an exception is for. Both are in the same class:

std::optional<Loan> find(const std::string& title) const;      // expected absence
const Loan& require(const std::string& title) const;           // failure: throws

Using optional for a failure means every caller must decide what "it failed" means, with no type and no message to work from. Using an exception for an expected outcome means a try around a search that usually finds nothing.

9. "The standard library is always faster than my code."¶

The library gives you a correct, documented implementation of an operation. It cannot fix the complexity of the operation you chose. A scan inside a loop is quadratic whether it is written with std::find_if or by hand, and an unordered_map with a constant hash is slower than a scan of ten elements:

hand-written scan for 1000: 501 comparison(s)   <- linear, and fine at this size

Measure at two data sizes, and check the shape of the growth rather than the numbers.

10. "Complexity does not matter at this size."¶

It matters at the next size, and the next size is not hypothetical: a campus file has ten items in testing and forty thousand in production. The doubling test is the cheapest insurance there is — run the same query on n and on 10n, and look at the ratio. A linear operation grows tenfold; a quadratic one grows a hundredfold; and the difference between them at the second size is the difference between a program and a hang.

Part 2 — Common programming mistakes¶

Symptoms, and what actually causes them¶

Symptom	Cause
Crash, garbage, or a silently wrong result after modifying a `vector` during iteration	Iterator invalidation on reallocation
The element is still in the container after "removing" it	`std::remove`/`remove_if` without `erase`
`error: no match for 'operator<' (operand types are 'const Book' and 'const Book')`	A type used as a key in `map`/`set` has no ordering
`error: use of deleted function 'std::unordered_map<...>::unordered_map() [with ... _Hash = std::hash<Book>]'`	A type used as a key in an unordered container has no hash
`error: no match for 'operator==' (operand types are 'Book' and 'const Book')`	An algorithm (`std::find`, `std::count`) needs equality the type does not have
`error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' ...)` from inside `std::sort`	`std::sort` needs random-access iterators; a `list` has none
Two equal keys behave as different keys; duplicates accumulate	The hash and `==` disagree: equal values must hash equally
`unordered_map` is unexpectedly slow	A poor hash, or many collisions; look at `bucket_count()` and `load_factor()`
A crash in a lambda invoked later	A capture by reference outlived the captured variable
Garbage printed from a `string_view`	The view points at destroyed storage
The program is far slower than expected on large data	A linear scan inside a loop — quadratic overall
Elements are copied rather than moved when a `vector` grows	The element's move constructor is not `noexcept` (Module 10)
`std::sort` crashes or leaves the range unsorted	The comparator is not a strict weak ordering — `<=` instead of `<`
An element vanishes from a `map` with a custom key	The comparator reports two distinct keys as equivalent

Worked mistakes¶

M1. A custom type as a key in an ordered container¶

struct Book { int id = 0; std::string title; };

std::map<Book, int> stock;
stock[Book{1, "Compilers"}] = 2;

…/include/c++/14.2.0/bits/stl_function.h:405:20: error: no match for 'operator<'
       (operand types are 'const Book' and 'const Book')
m14-diag-b.cpp:11:31:   required from here

The snippet above was saved as m14-diag-b.cpp, and library paths are abbreviated to …/include/c++/… — the frames that matter are the ones naming a file of yours.

Read the trail, not just the error. The error is inside the standard library's own std::less<Book>, and the required from here line names your line — which is the one frame you can change. The fix is operator< for Book, and it must be a strict weak ordering:

bool operator<(const Book& left, const Book& right) {
    if (left.id != right.id)       { return left.id < right.id; }
    if (left.title != right.title) { return left.title < right.title; }
    return left.edition < right.edition;      // equivalent only if all three match
}

M2. The same type in an unordered container, with no hash¶

struct Book {
    int id = 0;
    std::string title;
    bool operator==(const Book& other) const { return id == other.id; }
};

std::unordered_map<Book, int> stock;

error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
       ::unordered_map() [with _Key = Book; _Tp = int; _Hash = std::hash<Book>;
       _Pred = std::equal_to<Book>; _Alloc = std::allocator<std::pair<const Book, int> >]'

The template arguments in the message are the answer: the container defaulted to std::hash<Book>, which does not exist, so the default constructor was deleted. Two fixes:

// 1. supply a hash as a template argument
std::unordered_map<Book, int, BookHash> stock;

// 2. or make the key type the identity
std::unordered_map<int, Book> stock;      // often the honest representation

Do not reach for a hash before checking whether the second option is right. Expressing "the id is the identity" in the key type is simpler, faster and impossible to get subtly wrong.

M3. An algorithm that needs equality¶

std::vector<Book> books{{1, "Compilers"}};
const auto found = std::find(books.begin(), books.end(), Book{1, "Compilers"});

…/include/c++/14.2.0/bits/predefined_ops.h:270:24: error: no match for 'operator=='
       (operand types are 'Book' and 'const Book')

Same shape of mistake as M1, and the same fix: the type has to provide the operation the algorithm names. Note which operations your type is missing for the queries you actually run — find needs ==, sort and map need <, unordered_map needs both == and a hash.

M4. `std::sort` on a container that cannot support it¶

std::list<int> values{3, 1, 2};
std::sort(values.begin(), values.end());

error: no match for 'operator-' (operand types are 'std::_List_iterator<int>'
       and 'std::_List_iterator<int>')
required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = _List_iterator<int>]'

sort computes distances, and a list iterator cannot jump. The error is about iterator arithmetic, not about sorting. The fix is values.sort(), which re-links nodes — the container's own member, written for exactly this case. The diagnostic names the missing operation; the fix names the container.

M5. A stored lambda with a reference capture¶

std::function<int()> makeCounter() {
    int count = 0;
    return [&count] { return ++count; };   // reference to a local
}
auto counter = makeCounter();
std::cout << counter() << '\n';            // reading freed storage

Compiles with no warning at all: the compiler checks that the lambda's own lifetime is respected, and std::function owning the closure is perfectly valid. What is invalid is the reference inside it. There is no captured output to show, because the behaviour is undefined — it may print a plausible number, print garbage, or crash, and it may do something different tomorrow. The evidence for this mistake is the audit, not a transcript: read every capture list in your program and ask whether the captured variable still exists when the lambda is called. Part E of examples/module-14/06-lambdas-captures-and-views/ walks through the two shapes to check for.

The four rules worth memorising¶

Choose the container from the operations you perform, and write the sentence that says so.
Ask, before every use of an iterator: did anything modify this container since I obtained it?
remove_if needs erase; a stored lambda needs value captures; a returned string_view needs a named owner.
Measure at two data sizes before claiming an improvement — and check the shape of the growth, not the numbers.

Continue¶

Previous: Worked examples · Next: Debugging · Module home: Module 14