Question bank — Iterators — input, output, forward, bidirectional, random access, contiguous

True. The categories form a refinement chain, so random access is a strict superset — it keeps --it and adds it+n, it[n], etc. on top.

False. Refinement only goes one way. A std::list iterator can step --it but cannot jump it+n in $O(1)$, so it stops at bidirectional.

True. deque is random-access, so subscripting is constant-time — it just isn't contiguous, which is a separate promise about memory layout.

False. Random access guarantees fast indexing, not that element 5 and element 6 share one memory block. Only contiguous iterators promise &*(it+n) == &*it + n.

False. Pure output iterators have no equality and no end sentinel; you must drive them from a known-length source range instead.

False. Input iterators are single-pass — advancing any copy consumes the underlying stream, so the other copy is invalidated. Multi-pass safety begins at forward.

True. Forward iterators are multi-pass and mutable (unless the container is const), so x = *it and *it = x are both allowed — that's what separates them from input/output.

False. std::sort needs random-access iterators to partition by jumping around; list only has bidirectional iterators, which is exactly why list ships its own L.sort() member.

True. Contiguous adds a memory guarantee (&*(it+n) == &*it + n), not a new callable operation. The operations are identical to random access.

True. A string stores its characters in one contiguous block (like vector and array), so &*(s.begin()+n) == &*s.begin() + n holds.

list iterators are bidirectional, so operator + does not exist — this fails to compile. Use std::advance(m, 2) (an $O(n)$ loop of ++).

Storing and revisiting the first read position is illegal for input iterators — they are single-pass, so the old position is invalid the moment you advance.

You cannot compare a pure output iterator with ==; output iterators have no equality. Track how many elements you wrote instead.

back_inserter is output-only. Reading through it (x = *it) is not supported; it only supports *it = value and ++it.

deque is not contiguous, so p+1 may not point at element 1 — the memory is split into chunks. Only vector/array/string may be handed to such a C API.

Input iterators move forward only; negative advance would require --it, which they lack. Negative distances are legal only from bidirectional upward.

Because not every container can perform every operation cheaply — a list cannot jump in $O(1)$. Categories encode which operations are affordable so the compiler picks the fastest valid algorithm.

Tag dispatch selects it += n for random-access iterators (one jump) and a ++it loop for bidirectional ones, because only random-access memory supports a constant-time jump.

Its type selects the overload at compile time, so the dispatch has zero runtime cost — the branch is resolved before the program runs. See Templates and Tag Dispatch.

copy writes its destination with *it = value and advances with ++it — exactly the output-iterator contract. It never reads the destination, so nothing stronger is needed.

Random access is necessary for contiguous (you need it+n first) but not sufficient — you also need the addresses to be linear, which random access alone doesn't promise.

C APIs expect a raw pointer into one flat array where p+n is the n-th element. Only the contiguous guarantee &*(it+n) == &*it + n makes &*container.begin() behave that way. Compare with plain Pointers and pointer arithmetic.

Contiguous — the strongest. A pointer supports read/write, ++, --, +n, subtraction, ordering, and its addresses are by definition linear in memory.

Nothing moves — zero steps is valid for every category, including input, since no direction or jump is actually performed.

Yes. find reads with *it, advances with ++it, and compares positions with != — all supported from input/forward upward, so it works on the widest range of containers.

Any category with equality — input, forward, bidirectional, random access, contiguous. Pure output iterators cannot, since they have no == and no end sentinel.

No. Key lookup is a container operation on the tree; the iterator only walks the sorted sequence with ++/--, so it is bidirectional, not random access.

No. A const_iterator allows *it reads but forbids *it = x; the category (contiguous) describes traversal power, while const-ness independently governs mutability.