A C++ inventory's insert adds to a std::vector and a std::map index; how do you make it leave both unchanged if copying the item throws?
answer
- two structures, one invariant
- find the step that can fail
- commit with operations that cannot throw
- undo must be nothrow
basics
~20 sDo every step that can throw before anything is committed, or pair each committed step with an undo that cannot throw: add the index entry, push_back the copy, and erase that entry by iterator if the copy throws.
solid answer
~40 sThe invariant is that the item list and the SKU index agree. Writing `items_.push_back(item); index_.emplace(sku, pos);` breaks it if the second step throws, because the vector has already committed. Each standard step is strong on its own: `std::map::try_emplace` of one element has no effects if it throws, and `push_back` of a copyable element has no effects either. The fix is to sequence them so a failure in the second can be undone by an operation that cannot throw: `try_emplace` into the index, then `push_back` inside `try`, and on any exception `index_.erase(it)` and `throw;`. Erasing by iterator does not throw, so the rollback cannot fail. If no non-throwing undo exists, stage the change in a copy and publish it with a non-throwing operation.
code
cpp · 39 lines#include <cstddef>
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
inline bool fail_next_copy = false; // fault injection for the demo
struct Item {
std::string sku; int qty = 0;
Item(std::string s, int q) : sku(std::move(s)), qty(q) {}
Item(const Item& o) : sku(o.sku), qty(o.qty) {
if (std::exchange(fail_next_copy, false)) throw std::runtime_error("copy failed");
}
};
class Inventory {
std::vector<Item> items_;
std::map<std::string, std::size_t> index_; // sku -> position in items_
public:
void insert(const Item& item) { // strong guarantee
auto [it, added] = index_.try_emplace(item.sku, items_.size());
if (!added) throw std::invalid_argument("duplicate sku");
try { items_.push_back(item); } // copies the Item: may throw
catch (...) { index_.erase(it); throw; } // undo cannot throw
}
std::size_t size() const noexcept { return items_.size(); }
std::size_t indexed() const noexcept { return index_.size(); }
};
int main() {
Inventory inv;
inv.insert(Item{"A-1", 3});
fail_next_copy = true;
try { inv.insert(Item{"B-2", 5}); } catch (const std::exception& e) { std::cout << e.what() << '\n'; }
std::cout << "items " << inv.size() << ", index " << inv.indexed() << '\n';
}go deeper
Understand that the inventory must never end up with an item missing from its index, even when an insert fails.
Explain why push_back followed by emplace breaks the invariant when the second step throws, using each container's own guarantee.
Restructure the function so all fallible work precedes commits or has a non-throwing undo, and prove it with fault-injection tests.
Weigh rollback against staging and publishing by their cost on the success path, and decide which public operations the inventory documents as strong.
## The failure to fix An inventory class keeps two structures that must agree: - `std::vector<Item> items_` stores the items in insertion order; - `std::map<std::string, std::size_t> index_` maps each SKU to its position. The **invariant** is that every item has exactly one index entry pointing at it. A first draft of `insert`: ```cpp void insert(const Item& item) { items_.push_back(item); // commits the item index_.emplace(item.sku, items_.size() - 1); // may throw std::bad_alloc } ``` If the map allocation throws, the item is in the vector with no index entry. The function gives **no guarantee**: the object is left with a broken invariant. ## Step 1: know each step's own guarantee | Step | Can throw because | Guarantee when it throws | |---|---|---| | `index_.try_emplace(sku, pos)` | allocating the node, copying the key | no effects (single-element associative insert) | | `items_.push_back(item)` | reallocating, copying the `Item` | no effects for a copy-insertable element | | `index_.erase(it)` | nothing | does not throw | | `items_.pop_back()` | nothing | does not throw | Two strong steps in sequence are not strong: once the first has committed, a failure in the second leaves the object in between. ## Step 2: sequence so the undo is non-throwing The rule is **do the fallible work first, and make every step after the first commit reversible by an operation that cannot throw**: 1. `try_emplace` the index entry. If it throws, nothing has changed. If the SKU already exists, report a duplicate and stop. 2. `push_back` the item inside a `try` block. If copying the item throws, the vector is unchanged. 3. In the `catch (...)`, `index_.erase(it)` and rethrow with `throw;`. Erasing by iterator does not throw, so the rollback always succeeds. The snippet below injects a failing copy on the second insert and shows that afterwards the inventory has one item and one index entry. The alternative order also works: `push_back` first, then `try_emplace` inside `try`, and `items_.pop_back()` on failure, since `pop_back` does not throw either. What matters is that the compensating action is non-throwing. ## Step 3: when no non-throwing undo exists Some changes cannot be reversed without another fallible operation, such as reordering many elements. Then the remaining tool is **stage and publish**: build the new state in a separate object, where failure touches nothing visible, and replace the live state with an operation that cannot throw. The standard containers' `swap` member functions do not throw, which is why they are the usual publishing step; the copy-and-swap idiom for assignment operators is the best-known instance of this, covered with the special member functions. ## Where the hidden copies are Fallible steps are not always visible as calls: - `try_emplace(item.sku, ...)` copies the SKU string into the new map node, which can throw `std::bad_alloc`. - `push_back(item)` may reallocate the vector, copying or moving every existing element, before it copies the new one. - Taking the item by value instead of by `const Item&` would copy it at the call site, before `insert` even starts; that copy is outside the function's guarantee, but it is still a place the caller sees an exception. - Logging inside the function, for example formatting a message with the SKU, allocates too and must come before the commit or inside a `try`. ## Costs to weigh - Staging a copy of a large inventory for every insert is expensive; the undo-based version above costs nothing extra on the success path. - The rollback version relies on the specific guarantees of the containers involved; a hand-written container needs the same properties documented. - Testing needs **fault injection**: a type whose copy throws on demand, or an allocator that fails after N allocations, otherwise the rollback path never runs in tests. ## Review checklist for a strong-guarantee function - List every operation that can throw, including copies hidden in arguments. - Confirm nothing visible changes before the last fallible step, or that each earlier commit has a non-throwing undo. - Make the undo path rethrow with `throw;` so the caller still sees the original exception. - Add a fault-injection test that forces each fallible step to fail.
- Why does try_emplace come before push_back here and not after?Either order works as long as the second step's failure can be undone without throwing: `erase` by iterator on the map and `pop_back` on the vector both do not throw. Putting `try_emplace` first also checks for a duplicate SKU before any copy of the item is made, so the common rejection path never touches the vector.
- How do you test that the rollback really works?Force each fallible step to fail. A test item type whose copy constructor throws when a flag is set exercises the `push_back` failure; an allocator that fails after a set number of allocations exercises the map's node allocation. After each injected failure, assert that the sizes and contents of both structures match the state before the call.
- Using only strong standard operations makes the function strong automatically.
- A rollback step that can itself throw is fine if it rarely fails.
- Catching the exception and not rethrowing gives the strong guarantee.
- The strong guarantee always requires copying the whole container first.