# `base::ranges` This directory aims to implement a C++14 version of the new `std::ranges` algorithms that were introduced in C++20. These implementations are added to the `::base::ranges` namespace, and callers can access them by including [`base/ranges/algorithm.h`](https://source.chromium.org/chromium/chromium/src/+/main:base/ranges/algorithm.h). ## Similarities with C++20: ### Automatically deducing `begin()` and `end()` As probably one of the most important changes for readability and usability, all algorithms in `base::ranges` have overloads for ranges of elements, which allow callers to no longer specify `begin()` and `end()` iterators themselves. Before: ```c++ bool HasEvens(const std::vector& vec) { return std::any_of(vec.begin(), vec.end(), [](int i) { return i % 2 == 0; }); } ``` After: ```c++ bool HasEvens(const std::vector& vec) { return base::ranges::any_of(vec, [](int i) { return i % 2 == 0; }); } ``` Furthermore, these overloads also support binding to temporaries, so that applying algorithms to return values is easier: ```c++ std::vector GetNums(); ``` Before: ```c++ bool HasEvens() { std::vector nums = GetNums(); return std::any_of(nums.begin(), nums.end(), [](int i) { return i % 2 == 0; }); } ``` After: ```c++ bool HasEvens() { return base::ranges::any_of(GetNums(), [](int i) { return i % 2 == 0; }); } ``` ### Support for Projections In addition to supporting automatically deducing the `begin()` and `end()` iterator for ranges, the `base::ranges::` algorithms also support projections, that can be applied to arguments prior to passing it to supplied transformations or predicates. This is especially useful when ordering a collection of classes by a specific data member of the class. Example: Before: ```cpp std::sort(suggestions->begin(), suggestions->end(), [](const autofill::Suggestion& a, const autofill::Suggestion& b) { return a.match < b.match; }); ``` After: ```cpp base::ranges::sort(*suggestions, /*comp=*/{}, &autofill::Suggestion::match); ``` Anything that is callable can be used as a projection. This includes `FunctionObjects` like function pointers or functors, but also pointers to member function and pointers to data members, as shown above. When not specified a projection defaults to `base::ranges::identity`, which simply perfectly forwards its argument. Projections are supported in both range and iterator-pair overloads of the `base::ranges::` algorithms, for example `base::ranges::all_of` has the following signatures: ```cpp template bool all_of(InputIterator first, InputIterator last, Pred pred, Proj proj = {}); template bool all_of(Range&& range, Pred pred, Proj proj = {}); ``` ## Differences from C++20: To simplify the implementation of the `base::ranges::` algorithms, they dispatch to the `std::` algorithms found in C++14. This leads to the following list of differences from C++20. Since most of these differences are differences in the library and not in the language, they could be addressed in the future by adding corresponding implementations. ### Lack of Constraints Due to the lack of support for concepts in the language, the algorithms in `base::ranges` do not have the constraints that are present on the algorithms in `std::ranges`. Instead, they support any type, much like C++14's `std::` algorithms. In the future this might be addressed by adding corresponding constraints via SFINAE, should the need arise. ### Lack of Range Primitives Due to C++14's lack of `std::ranges` concepts like sentinels and other range primitives, algorithms taking a `[first, last)` pair rather than a complete range, do not support different types for `first` and `last`. Since they rely on C++14's implementation, the type must be the same. This could be addressed in the future by implementing support for sentinel types ourselves. ### Lack of `constexpr` The `base::ranges` algorithms can only be used in a `constexpr` context when they call underlying `std::` algorithms that are themselves `constexpr`. Before C++20, only `std::min`, `std::max` and `std::minmax` are annotated appropriately, so code like `constexpr bool foo = base::ranges::any_of(...);` will fail because the compiler will not find a `constexpr std::any_of`. This could be addressed by either upgrading Chromium's STL to C++20, or implementing `constexpr` versions of some of these algorithms ourselves. ### Lack of post C++14 algorithms Since most algorithms in `base::ranges` dispatch to their C++14 equivalent, some `std::` algorithms that are not present in C++14 have no implementation in `base::ranges`. This list of algorithms includes the following: - [`std::sample`](https://en.cppreference.com/w/cpp/algorithm/sample) (added in C++17) ### Return Types Some of the algorithms in `std::ranges::` have different return types than their equivalent in `std::`. For example, while `std::for_each` returns the passed-in `Function`, `std::ranges::for_each` returns a `std::ranges::for_each_result`, consisting of the `last` iterator and the function. In the cases where the return type differs, `base::ranges::` algorithms will continue to return the old return type. ### No blocking of ADL The algorithms defined in `std::ranges` are not found by ADL, and inhibit ADL when found by [unqualified name lookup][1]. This is done to be able to enforce the constraints specified by those algorithms and commonly implemented by using function objects instead of regular functions. Since we don't support constrained algorithms yet, we don't implement the blocking of ADL either. [1]: https://wg21.link/algorithms.requirements#2