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

    Standard Library Sorted Sequence Operations Sorted Sequence Operations Sorted Seq. Ops

    This is not checked by any of the sorted sequence algorithms.

    Binary Searches

    Searching one element in a sorted sequence of N elements can be done in O(log N) steps.

    Finding an element in an unsorted sequence would take N steps in the worst case.

    Binary Search Algorithm

    binary_search binary_search

    std::vector<int> v {1,2,3,4,5,6,7,8};
    // search in subrange (as in image):
    cout << binary_search(begin(v)+2, begin(v)+7, 4);  // true
    // search in entire vector:
    cout << binary_search(begin(v), end(v), 8);  // true
    cout << binary_search(begin(v), end(v), 9);  // false
    
    std::vector<int> v {3,4,5,6,7};
    cout << std::ranges::binary_search(v, 4);  // true
    cout << std::ranges::binary_search(v, 9);  // false
    

    lower_bound lower_bound

    std::vector<int> v {0,1,2,3,4,5,6,7,8};
    // find in subrange (as shown in image):
    auto i = lower_bound(begin(v)+3, begin(v)+7, 5);
    if (i != end(v)) {  // true ⇒ found
      cout << *i;  // 5
    }
    // find in entire vector
    auto j = lower_bound(begin(v), end(v), 2);
    if (j != end(v)) {  // true ⇒ found
      cout << *j;  // 2
    }
    
    std::vector<int> v {3,4,5,6,7};
    auto i = std::ranges::lower_bound(v, 5);
    if (i != end(v)) {  // true ⇒ found
      cout << *i;  // 5
    }
    

    upper_bound upper_bound

    std::vector<int> v {0,1,2,3,4,5,6,7,8};
    // find in subrange (as shown in image):
    auto i = upper_bound(begin(v)+3, begin(v)+7, 5);
    if (i != end(v)) {  // true ⇒ found
      cout << *i;  // 6
    }
    // find in entire vector
    auto j = upper_bound(begin(v), end(v), 2);
    if (j != end(v)) {  // true ⇒ found
      cout << *j;  // 3
    }
    
    std::vector<int> v {3,4,5,6,7};
    auto i = std::ranges::upper_bound(v, 5);
    if (i != end(v)) {  // true ⇒ found
      cout << *i;  // 6
    }
    

    equal_range equal_range

    std::vector<int> v {1,1,2,3,4,5,5,5,6,6,7,7,8};
    // find in subrange (as shown in image):
    auto r5 = equal_range(begin(v)+3, begin(v)+11, 5);
    // erase range of '5'
    v.erase(r5.first, r5.second);
    for (int x : v) { cout << x << ' '; }  // 1 1 2 3 4 6 6 7 7 8
    // find in entire vector
    auto r6 = equal_range(begin(v), end(v), 6);
    // erase range of '6'
    v.erase(r6.first, r6.second);
    for (int x : v) { cout << x << ' '; }  // 1 1 2 3 4 7 7 8
    
    std::vector<int> v {3,4,5,5,5,6,6,7};
    auto [r5b,r5e] = std::ranges::equal_range(v, 5);
    // erase range
    v.erase(r5b, r5e);
    for (int x : v) { cout << x << ' '; }  // 3 4 6 6 7
    

    includes includes

    std::vector<int> r1 {0,1,2,3,4,5,6,7};
    std::vector<int> r2 {0,1,3,5,6,8,9};
    // as shown in image
    cout << includes(begin(r1)end(r1), begin(r2)+1begin(r2)+5);  // true
    // entire r2 in r1?
    cout << includes(begin(r1)end(r1), begin(r2)end(r2));  // true
    
    std::vector<int> range1 {0,1,2,3,4,5,6,7};
    std::vector<int> range2 {1,3,5,6};
    cout << std::ranges::includes(range1, range2);  // true
    

    Merging Merge

    Two sorted sequences can be merged into one sorted sequence in linear time.

    Merge Algorithm

    merge merge

    std::vector<int> in1 {0,2,4,6,7};
    std::vector<int> in2 {1,3,5,8};
    // make sure output can fit all elements
    std::vector<int> out;
    out.resize(in1.size() + in2.size());
    merge(begin(in1)end(in1), begin(in2)end(in2), begin(out));
    for (int x : out) { cout << x << ' '; }  // 0 1 2 3 4 5 6 7 8
    
    std::vector<int> in1 {0,2,4,6,7};
    std::vector<int> in2 {1,3,5,8};
    // make sure output can fit all elements
    std::vector<int> out;
    out.resize(in1.size() + in2.size());
    std::ranges::merge(in1, in2, begin(out));
    for (int x : out) { cout << x << ' '; }  // 0 1 2 3 4 5 6 7 8
    

    inplace_merge inplace_merge

    std::vector<int> v {0,2,3,5,6,1,3,4,8};
    inplace_merge(begin(v), begin(v)+5, end(v));
    for (int x : v) { cout << x << ' '; }  // 0 1 2 3 3 4 5 6 8
    
    std::vector<int> v {0,2,3,5,6,1,3,4,8};
    std::ranges::inplace_merge(v, begin(v)+5);
    for (int x : v) { cout << x << ' '; }  // 0 1 2 3 3 4 5 6 8
    

    Set Operations

    set_union set_union

    std::vector<int> s1 {0,1,2,2,4,4,5};
    std::vector<int> s2 {1,1,3,4,5};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(s1.size() + s2.size());
    auto e = set_union(begin(s1)end(s1), begin(s2)end(s2), begin(out));
    // shrink output to fit
    out.erase(e, end(out));
    for (int x : out) { cout << x << ' '; }  // 0 1 1 2 2 3 4 4 5
    
    std::vector<int> s1 {0,1,2,2,4,4,5};
    std::vector<int> s2 {1,1,3,4,5};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(s1.size() + s2.size());
    auto res = std::ranges::set_union(s1, s2, begin(out));
    // shrink output to fit
    out.erase(res.out, end(out));
    for (int x : out) { cout << x << ' '; }  // 0 1 1 2 2 3 4 4 5
    

    set_intersection set_intersection

    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto e = set_intersection(begin(s1)end(s1), begin(s2)end(s2), begin(out));
    // shrink output to fit
    out.erase(e, end(out));
    for (int x : out) { cout << x << ' '; }  // 2 4 7
    
    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto res = std::ranges::set_intersection(s1, s2, begin(out));
    // shrink output to fit
    out.erase(res.out, end(out));
    for (int x : out) { cout << x << ' '; }  // 2 4 7
    

    set_difference set_difference

    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto e = set_difference(begin(s1)end(s1), begin(s2)end(s2), begin(out));
    // shrink output to fit
    out.erase(e, end(out));
    for (int x : out) { cout << x << ' '; }  // 1 6
    
    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto res = std::ranges::set_difference(s1, s2, begin(out));
    // shrink output to fit
    out.erase(res.out, end(out));
    for (int x : out) { cout << x << ' '; }  // 1 6
    

    set_symmetric_difference set_symmetric_difference

    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto e = set_symmetric_difference(
      begin(s1), end(s1)begin(s2), end(s2), begin(out));
    // shrink output to fit
    out.erase(e, end(out));
    for (int x : out) { cout << x << ' '; }  // 1 3 6
    
    std::vector<int> s1 {1,2,4,6,7};
    std::vector<int> s2 {2,3,4,7};
    // make sure output could fit all elements
    std::vector<int> out;
    out.resize(std::max(s1.size(),s2.size()));
    auto res = std::ranges::set_symmetric_difference(s1, s2, begin(out));
    // shrink output to fit
    out.erase(res.out, end(out));
    for (int x : out) { cout << x << ' '; }  // 1 3 6