Why doesn't std::ranges::contains try using member contains just like std::ranges::begin tries using member begin? Or does it?

Question

std::begin can call the .begin member function if the argument has it. Also std::ranges::begin seems to do the same.

However, at the page for std::ranges::contains I see no mention of the word member, nor of .contains. Why is that?

I mean, if I was to write std::ranges::contains(someRange, someVal) I would really want it result in a call to member contains, if someRange happened to be a std::map and someVal a key in it.

I've also looked at ranges::contains from Range-v3, and it looks to me that too just makes a linear search through the range, with no special treatment for arguments supporting member contains.

Divorce

contains was added in C++20. ranges-v3 and its standard introduction all predate that. – Kotto

that said other functions like ranges::find also don't use the containers find if it has it, so maybe it was just a missed optimization in the proposal. – Kotto

@NathanOliver, yeah, I only mentioned contains but maybe find would have been a better choice in the first place, considering it is C++20, rather than C++23. – Divorce

Answer 1

I mean, if I was to write std::ranges::contains(someRange, someVal) I would really want it result in a call to member contains, if someRange happened to be a std::map and someVal a key in it.

The problem is that these mean very different things. Given a std::map<int, string> m, m.contains(42) checks if the key 42 exists in the map, but ranges::contains(m, 42) would check if 42 exists as a value in the range - but the value type is pair<int const, string>, which isn't comparable to int, so this wouldn't even compile.

The two algorithms simply do different things, so you can't have ranges::contains(m, v) try to call m.contains(v). That would be correct (though unnecessary) for string and string_view. It could be correct and an improvement for set but might be wrong (see below), but would be wrong for map.

The same is true for other algorithms where the general algorithm is based on the whole value type but some specific containers apply the algorithm to just the key (e.g. find, count, etc.).

Trying to check if m.contains(v) becomes a problem because these things in general tend to be very fragile in the presence of loose constraints (maybe the expression is valid because there's just no constraints on it, but there should be) or more flexible types (maybe some type just compares equal to everything, so the constraint is misleading - the canonical example here is using std::any when considering rules for constructibility).

And even if all the constraints are even legit and pass in a sensible way, that still doesn't mean that using the member algorithm is correct. For example:

struct Point {
    int x, y;
    friend auto operator==(Point, Point) -> bool = default;
};
struct JustXs {
    auto operator()(Point a, Point b) const -> bool {
        return a.x < b.x;
    }
};

int main() {
    std::set<Point, JustXs> points = {Point{1, 2}};
    bool a = points.contains(Point{1, 3});               // true
    bool b = std::ranges::contains(points, Point{1, 3}); // false
}

Pirali

It's not really right for set either - you don't know what the set's comparator does and whether it is compatible with ==. – Belva

But my point is why not having an overload valid only for types having .contains and calling that instead of the general-purpose algorithm? I'm precisely asking why can't ranges::contains(m, 42) have an overload that calls m.contains(42) enabled only for types of m that supports it? Passing, say, a map<int, int> and a pair<int, int> would fail to compile, and that would be ok. – Divorce

@Divorce Fundamentally - ranges::contains(m, 42) and m.contains(42) can be different algorithms, and we have no way of knowing whether member contains is the same algorithm as non-member contains. – Pirali

Answer 2

ranges::begin is not an algorithm; it is a fundamental operation on a range (indeed, part of the definition of the std::ranges::range concept is that ranges::begin works). The entire purpose of ranges::begin is to interface with a range. Mechanically, ranges::begin is a customization point object for which an individual type that wants to be a range will provide a certain interface. That is the purpose of the object.

ranges::contains is an algorithm; it is a thing that can be done to a range, which has a specific meaning and purpose. Algorithms are not customizable, nor are they intended to be. If a particular range has a function that is named the same as an algorithm, then from the perspective of the algorithm, this is a coincidence. Algorithms are not a way to call a range's interface; they are a way to act on a range, to access or manipulate it through a range interface.

You should not confuse algorithms with customization points.

Elnora

What does it mean that they are not intended to be customizable? What is the flaw in thinking that contains is an algorithm to check if an "item" is in a "collection", that it has a default behavior (linear scan of the collection), and that some "collections" can customize it for better performance (map using a binary search)? – Divorce

@Enlico: "What does it mean that they are not intended to be customizable?" It's not a difficult concept: the behavior of algorithms is not meant to be modified by the ranges on which they operate. Algorithms might have different implementations based on range properties (input-range vs. random-access), but they do not defer to individual functions on a range. – Elnora

Maybe in the first comment I should have asked why are they not intended to be customizable?. Maybe I'm just making the mistake of thinking of std::/ranges::contains as a task/query/operation/utility that can be implemented with one or another algorithm, and for which it provides a default algorithm. Instead it is an algorithm. So I guess the point is that contains, despite the general idea that its name conveys, is making a decision of an implementation detail on my behalf. – Divorce