Container Traversal Container Traversal Traversal
Try to only write loops if there is no well-tested (standard) library function/algorithm for what you want to do!
prefer non-random linear forward traversal for sequence containers like std::vector ⇒ best performance due to cache & prefetching friendliness
reverse traversal is only supported by some standard containers
for (type variable : container)- works for all standard sequence and associative containers
- container agnostic ⇒ easy to change container type
- no out-of-bounds access bugs possible
- no signed/unsigned index type hassle
- best performance when using sequence containers due to linear access pattern (cache & prefetching friendly)
- early exit possible with
break; - not suited for algorithms that require random access patterns
std::vector<Type> v { … }; // read-only, type cheap to copy/or copy needed: for (Type x : v) { cout << x; } for (auto x : v) { cout << x; } // read-only, type expensive to copy: for (Type const& x : v) { cout << x; } for (auto const& x : v) { cout << x; } // modify values: for (Type& x : v) { cin >> x; } for (auto& x : v) { cin >> x; }- convenient if you already have a function(object) to be applied to each element
- works for all standard sequence and associative containers
- container agnostic ⇒ easy to change container type
- no signed/unsigned index type hassle
- self-documenting name
- out-of-bounds access bugs possible with iterator ranges
#include <algorithm> // std::ranges::for_each namespace ranges = std::ranges; // alias Container<Type> v; … // read-only, type cheap to copy or copy needed: ranges::for_each(v, [](Type x){ cout << x; }); ranges::for_each(v, [](auto x){ cout << x; }); // read-only, type expensive to copy: ranges::for_each(v, [](Type const& x){ cout << x; }); ranges::for_each(v, [](auto const& x){ cout << x; }); // modify values: ranges::for_each(v, [](Type& x){ cin >> x; }); ranges::for_each(v, [](auto& x){ cin >> x; });
#include <algorithm> // std::for_each Container<Type> v; … // read-only, type cheap to copy or copy needed: for_each(begin(v), end(v), [](Type x){ cout << x; }); for_each(begin(v)+2, begin(v)+5, [](auto x){ cout << x; }); // read-only, type expensive to copy: for_each(begin(v), end(v), [](Type const& x){ cout << x; }); for_each(begin(v), end(v), [](auto const& x){ cout << x; }); // modify values: for_each(begin(v), end(v), [](Type& x){ cin >> x; }); for_each(begin(v), end(v), [](auto& x){ cin >> x; });
#include <algorithm> // std::for_each_n Container<Type> v; … auto const n = v.size() / 2; // read-only, type cheap to copy or copy needed: for_each_n(begin(v), n, [](Type x){ cout << x; }); // read-only, type expensive to copy: for_each_n(begin(v), n, [](Type const& x){ cout << x; }); // modify values: for_each_n(begin(v), n, [](Type& x){ cin >> x; });- container agnostic ⇒ easy to change container type
- works for all standard sequence containers
- no signed/unsigned index type hassle
- possible to skip multiple elements
- out-of-bounds access bugs possible
- verbose
std::vector<int> v {1, 2, 3, 4, 5, 6}; for (auto i = begin(v); i != end(v); ++i) { cout << *i; } for (auto i = begin(v); i != end(v); ++i) { cin >> *i; } // read-only - using const iterators for (auto i = cbegin(v); i != cend(v); ++i { cout << *i; }- possible to skip multiple elements
- prone to out-of-bounds access bugs
- easy to write subtle bugs due to signed/unsigned index type conversions
- does not work for all sequence containers ⇒ not easy to change container type
- making sure that loop doesn't modify elements requires more discipline
- verbose
std::vector<int> v {1, 2, 3, 4, 5, 6}; for (std::size_t i = 0; i < v.size(); ++i) { cout << v[i]; } // explicitly read-only const auto& cv = v; for (std::size_t i = 0; i < cv.size(); ++i) { cout << cv[i]; }for (type variable : container | std::views::reverse)- works for all bidirectional containers
- no out-of-bounds access bugs possible
- no signed/unsigned index type hassle
- early exit possible with
break;
#include <ranges> C++20 std::vector<int> v {1, 2, 3, 4, 5, 6}; for (int x : v | std::views::reverse) { cout << x << '\n'; } // read-only, if type cheap to copy/or copy needed for (auto x : v | std::views::reverse) { cout << x; } // read-only, if type expensive to copy for (auto const& x : v | std::views::reverse) { cout << x; } // modify values for (auto& x : v | std::views::reverse) { cin >> x; }- convenient if you already have a function(object) to be applied to each element
- works for all bidirectional containers
- easy to change container type
- no signed/unsigned index type hassle
- self-documenting name
- out-of-bounds access bugs possible with iterator ranges
#include <algorithm> // std::ranges::for_each #include <ranges> // range views namespace ranges = std::ranges; // alias namespace views = std::ranges::views; // alias Container<Type> v; … // read-only, type cheap to copy or copy needed: ranges::for_each(views::reverse(v), [](Type x){ cout << x; }); ranges::for_each(views::reverse(v), [](auto x){ cout << x; }); // read-only, type expensive to copy: ranges::for_each(views::reverse(v), [](Type const& x){ cout << x; }); ranges::for_each(views::reverse(v), [](auto const& x){ cout << x; }); // modify values: ranges::for_each(views::reverse(v), [](Type& x){ cin >> x; }); ranges::for_each(views::reverse(v), [](auto& x){ cin >> x; });#include <algorithm> // std::for_each Container<Type> v; … // read-only, type cheap to copy or copy needed: for_each(rbegin(v), rend(v), [](Type x){ cout << x; }); for_each(rbegin(v)+2, rbegin(v)+5, [](auto x){ cout << x; }); // read-only, type expensive to copy: for_each(rbegin(v), rend(v), [](Type const& x){ cout << x; }); for_each(rbegin(v), rend(v), [](auto const& x){ cout << x; }); // modify values: for_each(rbegin(v), rend(v), [](Type& x){ cin >> x; }); for_each(rbegin(v), rend(v), [](auto& x){ cin >> x; });#include <algorithm> // std::for_each_n Container<Type> v; … auto const n = v.size() / 2; // read-only, type cheap to copy or copy needed: for_each_n(rbegin(v), n, [](Type x){ cout << x; }); // read-only, type expensive to copy: for_each_n(rbegin(v), n, [](Type const& x){ cout << x; }); // modify values: for_each_n(rbegin(v), n, [](Type& x){ cin >> x; });- works for all bidirectional containers
- no signed/unsigned index type hassle
- possible to skip multiple elements
- out-of-bounds access bugs possible
- verbose
std::vector<int> v {1, 2, 3, 4, 5, 6}; for (auto i = rbegin(v); i != rend(v); ++i) { cout << *i; } for (auto i = rbegin(v); i != rend(v); ++i) { cin >> *i; } // read-only - using const iterators for (auto i = crbegin(v); i != crend(v); ++i { cout << *i; }- prone to out-of-bounds access bugs
- easy to write subtle bugs due to unsigned size type: implicit conversions to signed int, overflow/wrap-around, …
- making sure that loop doesn't modify elements requires more discipline
- verbose
std::vector<int> v {1, 2, 3, 4, 5, 6}; // std containers use unsigned size types // ⇒ be careful not to decrement unsigned "0" for (auto i = v.size(); i > 0; --i) { cout << v[i-1]; } // explicitly read-only const auto& cv = v; for (auto i = cv.size(); i > 0; --i) { cout << cv[i-1]; }Utilities
#include <iterator>
Functions std::prev and std::next provide a universal way of incrementing/decrementing iterators even if the iterator type does not support random access (e.g., it += 5).
However, be aware that advancing non-random access iterators (e.g., those from std::list) by N steps might be costly, i.e., involve on the order of N memory operations.
std::vector<int> v {1,2,3,4,5,6}; auto i = next(v.begin()); auto j = next(i, 3);
std::vector<int> v {1,2,3,4,5,6}; auto i = prev(v.end()); i = prev(i); auto j = prev(i, 3);- 1
- 2
- 3
- 4
- 5
- 6
-
-
-
-
-
-
- i
-
-
-
-
- i
-
-
- j
-
- i
-