Modern C++ Basics - Ranges & Algorithms

Ranges#

Introduction#

• Three important components in ranges:
  • Range
  • View: A range that can be moved in $O(1)$, copied in $O(1)$ (or cannot be copied) and destructed in $O(1)$.
  • Range adaptor: A functor that can transform a range/ranges to a view. You can connect a range with a range adaptor with operator|, which consists of a pipeline.
• They’re all defined in <ranges>; all views are defined as std::ranges::xx_view, and all range adaptors are defined as std::views::xx.
• A significant feature of the view generated by range adaptor is that calculation happens lazily.
  • That is, the calculation will happen iff. you want to get the next value of new view.

Writable views#

• Some views are read-only, i.e. you cannot change the element referenced by the view.
• Writable:
  • stdv::filter(Pred)
  • stdv::take(x)
  • stdv::take_while(Pred)
  • stdv::drop(x)
  • stdv::drop_while(Pred)
  • stdv::reverse
  • stdv::keys
  • stdv::values
  • stdv::elements<i>
  • stdv::stride(k)
• There are also some adaptors that combine some ranges and/or return a tuple (writable):
  • stdv::join
  • stdv::join_with(xx)
  • stdv::zip(r1, r2, ...)
  • stdv::cartesian_product(r1, r2, ...)
  • stdv::enumerate
• There are also some range adaptors that produce many views instead of a single view (writable):
  • stdv::slide(width)
  • stdv::adjacent<width>
  • stdv::pairwise
  • stdv::chunk(width)
  • stdv::chunk_by(pred2)
  • stdv::split(xx)
  • stdv::lazy_split(xx)

std::vector<int> nums { 0, 1, 2 };    
std::vector<std::string> strs { "one", "two", "three" };    
for (auto [idx, str] : strs | stdv::enumerate) {
    std::println("{}: {}", idx, str);
    str = "<" + str + ">"; // str is a reference
}
for (const auto [num, str] : stdv::zip(nums, strs)) {
    std::println("{}: {}", num, str);
}

• Caching behavior of views: views only guarantee that you will get the same elements for a non-modified range. It’s usually encouraged to use views ad hoc, i.e. use it once and immediately like in a loop.

Read-only views#

• Read-only:

  • stdv::as_const
  • stdv::transform(Transform)
  • stdv::zip_transform(TransformN, r1, r2, ...)
  • stdv::adjacent_transform(TransformN)
  • stdv::pairwise_transform(Transform2)

• Caveat on transform: The result is uncached, so when its value are needed, it may be called for multiple times.

Misc#

• Convert a range to a container: stdr::to

• Naïve range factories:

  • stdv::single(obj)
  • stdv::empty<T>
  • stdv::repeat(r, k = INF)
  • stdv::iota(lower, upper=INF)
  • stdv::istream<xx>(stream)

• Get a subrange from a range: stdr::subrange(first, last)

• stdr::size/begin() is more powerful.

Sentinel#

• We say that range is an iterator pair; but it’s in fact beyond that. An iterator begin and a sentinel end is enough!

struct NullTerminatedSentinel {};

bool operator==(const char* ptr, NullTerminatedSentinel) {
    return *ptr == '\0';
}

int main() {
    const char* cstr = "Hello";
    auto range = std::ranges::subrange(cstr, NullTerminatedSentinel{});
    for (auto& ch : range) {
        std::print("{}", ch);
    }
    std::println();
}

More Examples#

C++ Standard Library Composable Range Views | hacking C++ ↗

Generator#

• Use case:

std::generator<unsigned int> fib(const unsigned int num) {
    struct Arr {
        unsigned int now { 0 };
        unsigned int next { 1 };
    } arr;
    for (auto _ : stdv::repeat(std::ignore, num)) {
        unsigned int ret = arr.now;
        arr.now = arr.next;
        arr.next += ret;
        co_yield ret;
    }
}

int main() {
    for (const auto e: fib(100)) {
        std::print("{} ", e);
    }
    std::println();
}

• One generator can only be used once.
• Generator is also a view, which is only input_range.

Function#

Pointer to member functions#

• Usage: .*/->*/std::invoke/std::invoke_r<Result>

class Person {
public:
    unsigned int age;
    void addAge(unsigned int n) {
        age += n;
    }
};

int main() {
    using FuncPtr = void (Person::*)(unsigned int); // or use decltype(&Person::addAge)
    Person p { 0 };
    Person* ptr = &p;2
    FuncPtr f = &Person::addAge; // or use auto
    (p.*f)(5);
    (ptr->*f)(5);
    std::invoke(f, p, 5);
    std::invoke(f, ptr, 5);
}

Callable parameter (std::function)#

Usage#

• std::function<RetType(Args…)> can adopt almost all callable that have the return type convertible to RetType and accept Args.
  • The member function even preserves polymorphism.
  • you can bind some parameters to get new functors.
  • Prefer lambda to std::bind
  • Calling null function will throw std::bad_function_call.

class Person {
public:
    unsigned int age;
    void addAge(unsigned int n) {
        age += n;
    }
    void printAge() const {
        std::println("age: {}", age);
    }
};

int main() {
    Person p { 0 };
    std::function<void(Person&, unsigned int)> f_add = &Person::addAge;
    std::function<void(const Person&)> f_print = &Person::printAge;
}

Defects#

• Performance: It roughly causes 10%-20% performance loss compared with direct function call.

  • It may need to new/delete a customized functor in the ctor/dtor.
  • When the functor is small enough, new/delete won’t be triggered.
  • It’s also regulated in the standard that constructing from a normal function pointer will never allocate dynamically.
  • Then you can use auto lambda = xx; and pass std::ref(lambda) to ctor of std::function. (or use std::function_ref)

• Cannot support functors which are not copiable.

  • Use std::move_only_function.
    • It cannot be copied.
    • It’s UB to call null move_only_function.
    • It will respect cv-qualifier, ref-qualifier of member functions, and noexcept specifier. e.g. F<Ret(Args…) const>

Predefined functors and transparent operator#

• They are …
  • Arithmetic functors: plus, minus, multiplies, divides, modulus, negate
  • Comparison functors: equal_to, not_equal_to, greater, less, greater_equal, less_equal, compare_three_way
  • Logical functors: logical_and, logical_or, logical_not
  • Bitwise functors: bit_and, bit_or, bit_xor, bit_not
  • identity
• These Functor<T> all have auto operator()(const T&, const T&) const.
• Specially, Functor<void> (or Functor<>) have auto operator()(const T&, const U&) const, which called transparent operator. e.g. use std::set<std::string, std::less<>> to enable this feature to gain performance.
• using is_transparent = void can customize your own transparent operator. (e.g. transparent hash)

struct CaseInsensitiveLess {
    using is_transparent = void;

    bool operator()(std::string_view a, std::string_view b) const {
        auto to_lower = [](char c) { return std::tolower(c); };
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [&](char x, char y) { return to_lower(x) < to_lower(y); }
        );
    }
};

int main() {
    std::set<std::string, CaseInsensitiveLess> s{"Apple", "Banana"};    
    bool found1 = s.contains("apple");
    bool found2 = s.contains(std::string("BANANA"));
    return !(found1 && found2);
}

Reinforcement on lambda#

• stateless lambda:
  • You can use the type to construct a new functor.
  • Use case: std::set<T, LambdaType>
• unevaluated lambda:
  • using T = decltype([](int) {});
  • int a = []() { return 0; } ();

Algorithm#

C++ Standard Library Algorithms Introduction | hacking C++ ↗

// TODO