14. Iterator tradeoffs
In a latency-critical order book, the same algorithm may run over contiguous buffers or node-based containers. Choosing operations incompatible with an iterator’s category can either fail to compile or silently inflate complexity, harming tail latency. Design the iteration carefully to keep optimal complexity where possible.
template<class It> int tail_sum(It first, It last, size_t n){
auto len = last - first;
std::advance(first, len > n ? len - n : 0);
int s=0; for(; first!=last; ++first) s += *first;
return s;
}
Part 1.
Explain why this template is ill-formed for non-random-access iterators and how to rewrite it to support forward iterators while preserving O(1) behavior for random-access iterators.
Part 2.
(1) How do iterator categories constrain valid operations and algorithm complexity guarantees?
(2) Why can computing length with std::distance hurt latency on node-based containers?
(3) What iterator invalidation risks exist when advancing in hot paths?
(4) Does if constexpr-based dispatch add runtime overhead here?
(5) How does contiguous versus node-based iteration affect cache behavior?
Answer
Answer (Part 1)
last - first requires a random-access iterator; with forward/bidirectional iterators it is ill-formed, and substituting std::distance changes complexity to O(n). Use category-aware selection so random-access stays O(1) while others use O(n) distance: if constexpr (std::random_access_iterator<It>) { auto len = last - first; } else { auto len = static_cast<size_t>(std::distance(first, last)); } std::advance(first, len > n ? len - n : 0); The compile-time branch avoids runtime cost and preserves optimal complexity by category.
Answer (Part 2)
(1) They define which operations are legal and the minimal complexity. Using stronger-category operations on weaker iterators is invalid or slower.
(2) std::distance on non-random-access is linear and pointer-chasing. It increases tail latency via cache misses and branch mispredictions.
(3) Modifying the underlying container during iteration can invalidate iterators. vector reallocation/erase and list erasure can break traversal.
(4) No; if constexpr is resolved at compile time. The unused branch is discarded, yielding zero runtime overhead.
(5) Contiguous ranges enable prefetching and vectorization, maximizing cache-line utilization. Node-based iteration causes pointer chasing, cache/TLB misses, and pipeline stalls.