1# `base::ranges` 2 3This directory aims to implement a C++14 version of the new `std::ranges` 4algorithms that were introduced in C++20. These implementations are added to the 5`::base::ranges` namespace, and callers can access them by including 6[`base/ranges/algorithm.h`](https://source.chromium.org/chromium/chromium/src/+/main:base/ranges/algorithm.h). 7 8## Similarities with C++20: 9 10### Automatically deducing `begin()` and `end()` 11As probably one of the most important changes for readability and usability, all 12algorithms in `base::ranges` have overloads for ranges of elements, which allow 13callers to no longer specify `begin()` and `end()` iterators themselves. 14 15Before: 16```c++ 17bool HasEvens(const std::vector<int>& vec) { 18 return std::any_of(vec.begin(), vec.end(), [](int i) { return i % 2 == 0; }); 19} 20``` 21 22After: 23```c++ 24bool HasEvens(const std::vector<int>& vec) { 25 return base::ranges::any_of(vec, [](int i) { return i % 2 == 0; }); 26} 27``` 28 29Furthermore, these overloads also support binding to temporaries, so that 30applying algorithms to return values is easier: 31 32```c++ 33std::vector<int> GetNums(); 34``` 35 36Before: 37 38```c++ 39bool HasEvens() { 40 std::vector<int> nums = GetNums(); 41 return std::any_of(nums.begin(), nums.end(), 42 [](int i) { return i % 2 == 0; }); 43} 44``` 45 46After: 47```c++ 48bool HasEvens() { 49 return base::ranges::any_of(GetNums(), [](int i) { return i % 2 == 0; }); 50} 51``` 52 53### Support for Projections 54In addition to supporting automatically deducing the `begin()` and `end()` 55iterator for ranges, the `base::ranges::` algorithms also support projections, 56that can be applied to arguments prior to passing it to supplied transformations 57or predicates. This is especially useful when ordering a collection of classes 58by a specific data member of the class. Example: 59 60Before: 61```cpp 62std::sort(suggestions->begin(), suggestions->end(), 63 [](const autofill::Suggestion& a, const autofill::Suggestion& b) { 64 return a.match < b.match; 65 }); 66``` 67 68After: 69```cpp 70base::ranges::sort(*suggestions, /*comp=*/{}, &autofill::Suggestion::match); 71``` 72 73Anything that is callable can be used as a projection. This includes 74`FunctionObjects` like function pointers or functors, but also pointers to 75member function and pointers to data members, as shown above. When not specified 76a projection defaults to `base::ranges::identity`, which simply perfectly 77forwards its argument. 78 79Projections are supported in both range and iterator-pair overloads of the 80`base::ranges::` algorithms, for example `base::ranges::all_of` has the 81following signatures: 82 83```cpp 84template <typename InputIterator, typename Pred, typename Proj = identity> 85bool all_of(InputIterator first, InputIterator last, Pred pred, Proj proj = {}); 86 87template <typename Range, typename Pred, typename Proj = identity> 88bool all_of(Range&& range, Pred pred, Proj proj = {}); 89``` 90 91## Differences from C++20: 92To simplify the implementation of the `base::ranges::` algorithms, they dispatch 93to the `std::` algorithms found in C++14. This leads to the following list of 94differences from C++20. Since most of these differences are differences in the 95library and not in the language, they could be addressed in the future by adding 96corresponding implementations. 97 98### Lack of Constraints 99Due to the lack of support for concepts in the language, the algorithms in 100`base::ranges` do not have the constraints that are present on the algorithms in 101`std::ranges`. Instead, they support any type, much like C++14's `std::` 102algorithms. In the future this might be addressed by adding corresponding 103constraints via SFINAE, should the need arise. 104 105### Lack of Range Primitives 106Due to C++14's lack of `std::ranges` concepts like sentinels and other range 107primitives, algorithms taking a `[first, last)` pair rather than a complete 108range, do not support different types for `first` and `last`. Since they rely on 109C++14's implementation, the type must be the same. This could be addressed in 110the future by implementing support for sentinel types ourselves. 111 112### Lack of `constexpr` 113The `base::ranges` algorithms can only be used in a `constexpr` context when 114they call underlying `std::` algorithms that are themselves `constexpr`. Before 115C++20, only `std::min`, `std::max` and `std::minmax` are annotated 116appropriately, so code like `constexpr bool foo = base::ranges::any_of(...);` 117will fail because the compiler will not find a `constexpr std::any_of`. This 118could be addressed by either upgrading Chromium's STL to C++20, or implementing 119`constexpr` versions of some of these algorithms ourselves. 120 121### Lack of post C++14 algorithms 122Since most algorithms in `base::ranges` dispatch to their C++14 equivalent, some 123`std::` algorithms that are not present in C++14 have no implementation in 124`base::ranges`. This list of algorithms includes the following: 125 126- [`std::sample`](https://en.cppreference.com/w/cpp/algorithm/sample) (added in C++17) 127 128### Return Types 129Some of the algorithms in `std::ranges::` have different return types than their 130equivalent in `std::`. For example, while `std::for_each` returns the passed-in 131`Function`, `std::ranges::for_each` returns a `std::ranges::for_each_result`, 132consisting of the `last` iterator and the function. 133 134In the cases where the return type differs, `base::ranges::` algorithms will 135continue to return the old return type. 136 137### No blocking of ADL 138The algorithms defined in `std::ranges` are not found by ADL, and inhibit ADL 139when found by [unqualified name lookup][1]. This is done to be able to enforce 140the constraints specified by those algorithms and commonly implemented by using 141function objects instead of regular functions. Since we don't support 142constrained algorithms yet, we don't implement the blocking of ADL either. 143 144[1]: https://wg21.link/algorithms.requirements#2 145