C++ / ITERATORS, ALGORITHMS, AND RANGES
Writing code that works with any container
Turn container-specific helpers into templates that accept any container, subrange, or raw array by relying only on iterators and iterator_traits.
What you will learn
- Parameterize on an iterator pair or range instead of a concrete container type
- Use `using std::begin;` plus unqualified begin(r) so raw arrays and ADL types work
- Name element and count types via std::iterator_traits, never a hard-coded int
- Trade size(), [i], and push_back for distance, next, and insert(end(), x)
Understanding Writing code that works with any container
There is no Container base class in the standard library. std::vector<int> and std::forward_list<int> share no inheritance and no common member interface; what they share is that each will hand you two iterators plus a promise that walking from the first reaches the second. A function that spells a container type in its signature is therefore not general code with a narrow parameter, it is code welded to one data structure. The unit of genericity is the iterator pair, and your function's real interface is the set of iterator operations its body performs.
Two small mechanics keep such templates honest. Write `using std::begin;` and then call begin(r) unqualified: that picks up std::begin for arrays and for anything with a member begin(), while still letting argument-dependent lookup find a free begin that a third-party type defines in its own namespace. When you need to name the element type, ask std::iterator_traits<It>::value_type instead of hard-coding int, and use difference_type for counts; traits work even for int*, which is what an array decays to and which has no member typedefs at all.
Beyond that, genericity is restraint: every operation you use is a requirement, and every requirement excludes containers. c.size() excludes forward_list, c[i] and last - first exclude list and set, c.push_back(x) excludes associative containers. std::distance, std::next, out.insert(out.end(), x), and output iterators cover the same ground with weaker demands. Because a template body is only type-checked when instantiated, a requirement that is too strong stays invisible until someone trips over it, so instantiate deliberately with a std::vector and a std::forward_list as your compile-time canary.
<array>
<forward_list>
<iostream>
<iterator>
<vector>
// No container is named: r only has to hand out a pair of positions.
template <typename Range>
void report(const char* name, const Range& r) {
using std::begin; // unqualified begin/end can now find std::begin,
using std::end; // a member begin(), or an ADL free begin()
auto first = begin(r);
auto last = end(r);
using Value = typename std::iterator_traits<decltype(first)>::value_type;
Value total{};
for (auto it = first; it != last; ++it)
total += *it;
std::cout << name << ": " << std::distance(first, last)
<< " elements, total " << total << '\n';
}
int main() {
std::vector<int> v{1, 2, 3, 4};
std::forward_list<int> fl{5, 6, 7}; // no size(), no operator[]
std::array<int, 2> a{8, 9};
int raw[]{10, 20, 30}; // not a class at all
report("vector", v);
report("forward_list", fl);
report("array", a);
report("raw array", raw);
}
Generic container code is generic because it depends only on the operations an iterator pair supports, never on the container's name.
Worked examples
Iterator pair in, output iterator out
One loop body feeds a deque, a set, and stdout, and accepts only part of a vector as input.
<deque>
<iostream>
<iterator>
<set>
<vector>
template <typename InIt, typename OutIt>
OutIt copy_evens(InIt first, InIt last, OutIt out) {
for (; first != last; ++first)
if (*first % 2 == 0)
*out++ = *first;
return out;
}
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
std::deque<int> d;
copy_evens(v.begin() + 1, v.end() - 1, std::back_inserter(d));
std::set<int> s;
copy_evens(v.begin(), v.end(), std::inserter(s, s.end()));
std::cout << "deque:";
for (int x : d) std::cout << ' ' << x;
std::cout << '\n';
std::cout << "set size: " << s.size() << '\n';
copy_evens(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
std::cout << '\n';
}
Example explained
Line 1InIt only has to support !=, ++ and *, so the function has no idea which container the elements live in.
Line 2Passing v.begin() + 1 and v.end() - 1 covers just 2,3,4,5, which a parameter of type const std::vector<int>& could never express.
Line 3std::back_inserter(d) and std::inserter(s, s.end()) both turn the write *out++ = value into an insertion, so the same body fills a deque or a set.
Line 4std::ostream_iterator<int>(std::cout, ",") shows the destination need not be a container at all, which is why the output ends with a trailing comma.
Take a container, return the same kind
insert(out.end(), x) is the single insertion call that sequence and associative containers both accept.
<iostream>
<list>
<set>
<vector>
template <typename Container, typename F>
Container mapped(const Container& c, F f) {
Container out;
for (const auto& x : c)
out.insert(out.end(), f(x));
return out;
}
int main() {
std::vector<int> v{3, -1, 2};
std::list<int> l{3, -1, 2};
std::set<int> s{-2, 2, 3};
auto square = [](int x) { return x * x; };
std::cout << "vector:";
for (int x : mapped(v, square)) std::cout << ' ' << x;
std::cout << '\n';
std::cout << "list:";
for (int x : mapped(l, square)) std::cout << ' ' << x;
std::cout << '\n';
auto ss = mapped(s, square);
std::cout << "set:";
for (int x : ss) std::cout << ' ' << x;
std::cout << " (3 inputs -> " << ss.size() << " elements)\n";
}
Example explained
Line 1Container out; reuses whatever type the caller passed, so no std::vector is baked into the helper.
Line 2out.insert(out.end(), f(x)) is accepted by vector, list and set alike; push_back would compile for the first two and reject the set.
Line 3Re-reading out.end() every iteration matters for vector, where a reallocation invalidates the end iterator from the previous pass.
Line 4The set result has two elements from three inputs because -2 and 2 both square to 4: generic code inherits each container's semantics instead of overriding them.
Important notes
std::distance and std::next are O(n) for anything weaker than a random-access iterator, so compute them once instead of inside a loop or a linear algorithm quietly becomes quadratic.
In C++20, std::ranges::begin(r) already handles arrays and ADL for you, and constraining the parameter (template <std::ranges::input_range R>) reports a mismatch at the call site instead of deep inside the template body.
Common mistakes
Declaring the helper as const std::vector<int>& and later needing to pass a std::list<int> or half a vector: no conversion exists so the call will not compile, and copying into a temporary vector to satisfy it adds an allocation and an O(n) copy on every call.
Writing r.begin() or std::begin(r) inside the template: the member form fails outright for int[5] because arrays have no members, and the fully qualified form suppresses ADL, so a type whose only begin is a free function in its own namespace stops compiling.
Assuming pointer arithmetic: begin(r) + 1, last - first and r[i] compile happily for vector and deque, then break the first time someone passes a std::list or std::set, because those iterators offer no addition or subscript.
Try it yourself
Change, predict, then run
Write template <typename Range, typename T> auto index_of(const Range& r, const T& value) that returns the zero-based position of the first element equal to value, or -1 if there is none, using only begin/end, ++, * and != — no size(), no [i], no iterator arithmetic. Call it with a std::vector<std::string>, a std::forward_list<int> and a raw int[5], and print all three results.
Open the C++ workspaceCheck your understanding
A helper is written as `template <typename Range> auto second(const Range& r) { using std::begin; return *(begin(r) + 1); }`. It compiles and runs for std::vector<int> but fails to compile for std::list<int>. What is the actual reason?
- std::list has no free begin() overload, so the unqualified call finds nothing to call.
- auto cannot deduce a return type from the result of a list iterator's operator*.
- Iterator addition is only defined for random-access iterators, and a list's iterators are bidirectional, so std::next(begin(r)) is needed.
- std::list stores elements in nodes, so *it yields a node handle rather than an int.
Show answer
The + 1 is the problem: only random-access iterators provide iterator arithmetic, and list nodes are scattered, so moving forward means following links, which is exactly what std::next (or std::advance) does. The lookup option is tempting because free begin/end genuinely matter for raw arrays, but std::begin on a std::list simply calls its member begin() and succeeds; the name resolves fine and the arithmetic is what fails.