Collapse All Levels Collapse Top Level Expand Top Level Expand All Levels
News Articles Recipes Beginner's Guide to C++ Lists
@hackingcpp RSS Feed About Privacy Home
    Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Diagnostics
    Standard Library – Part 1
    Function Objects
    Standard Library – Part 2
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    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

    Forward Traversal Forward

    Range-Based Loop Range for

    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; }

    for_each / for_each_n for_each/for_each_n for_each

    • 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
    standard library algorithm 'ranges-for_each' visual example
    • no out-of-bounds access possible
    #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; });
    standard library algorithm 'for_each' visual example
    • can be used on subranges
    • out-of-bounds access bugs possible
    #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; });
    standard library algorithm 'for_each_n' visual example
    • can be used on subranges
    • out-of-bounds access bugs possible
    #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; });

    Explicit Use of Iterators Iterators

    • 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; }

    Index-Based Loop Index Loop

    • 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]; }

    Reverse Traversal Reverse

    Reverse Range-Based Loop Range-Based C++20

    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; }

    Reverse for_each / for_each_n Reverse for_each for_each

    • 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
    standard library algorithm 'ranges-for_each' visual example
    • no out-of-bounds access possible
    #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; });
    standard library algorithm 'for_each' visual example
    • can be used on subranges
    • out-of-bounds access bugs possible
    #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; });
    standard library algorithm 'for_each_n' visual example
    • can be used on subranges
    • out-of-bounds access bugs possible
    #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; });

    Explicit Use of Reverse Iterators Iterators

    • 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; }

    Reverse Index-Based Loop Index Loop

    • 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

    Get Next / Previous Iterator Next/Prev

    #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.

    standard library algorithm 'next1' visual example
    std::vector<int> v {1,2,3,4,5,6};
auto i = next(v.begin());
auto j = next(i, 3);
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    •  
    

    •  
    • i
    •  
    •  
    •  
    •  
    

    •  
    • i
    •  
    • j
    •
    standard library algorithm 'prev1' visual example
    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
    •
    Std.Algorithms
    Beginner's Guide / Std.Library 1
    min/max

    Related …

    Last updated: 2021-04-10

    Comments…