C++ determine if a container has ::find()

Question

I have a functor which operates on a container of type U of elements of type T like so

template<typename T, template<typename...> class U>
class asserter 
{
public:
    asserter(U<T> &c) : container(c) { };
    void operator()(T lhs) 
    {
        CU_ASSERT(container.find(lhs) != container.end());
    };
private:
    U<T>    &container;
};

which I might use as

std::set<std::string> a, c;
...
asserter<std::string, std::set> ass(c);
for_each(a.begin(), a.end(), ass);

Where we are ignoring std::includes() for the moment.

This works great if the container is one where U::find() is defined. If it's not I'd like to fall back to std::find(). On the other hand I'd rather use U::find() over std::find() if it's available.

In C++11 (or 17 if necessary) can I determine if U::find() is available (possibly restricting to the STL) for U and if so use it, otherwise use std::find()?

T.C. · Accepted Answer · 2015-09-16T05:59:35.677

7

SFINAE on whether the expression c.find(value) is well-formed. Trailing return type is C++11, and not essential here anyway; it just makes the return type easier to write - decltype(c.find(value)) instead of decltype(std::declval<Container&>().find(std::declval<const T&>())).

If the expression would be ill-formed, the first overload of find_impl is removed from the overload set, leaving the second overload as the only viable one. The usual int/long/0 trick for the third parameter makes the first overload preferred when both are viable.

template<class Container, class T>
auto find_impl(Container& c, const T& value, int) -> decltype(c.find(value)){
    return c.find(value);
}

template<class Container, class T>
auto find_impl(Container& c, const T& value, long) -> decltype(std::begin(c)){
    return std::find(std::begin(c), std::end(c), value);
}

template<class Container, class T>
auto find(Container& c, const T& value) -> decltype(find_impl(c, value, 0)) {
    return find_impl(c, value, 0);
}

The usual disclaimer applies: this relies on expression SFINAE, which is not currently supported by MSVC; Microsoft does plan to add support in an update to MSVC 2015.

edited Sep 16 '15 at 05:59

answered Sep 16 '15 at 03:51

T.C.

133,968
17
288
421

4

A more useful answer would also explain why the code works. For example, I was expecting an answer that employed SFINAE. Is the `decltype(...)` portion a SFINAE technique in C++17 (I think this lambda expression syntax is C++17)? Also, is `int` used to force that signature to have preference over the `long` overload? – James Adkison Sep 16 '15 at 03:57
I have a worry that `std::find` is for equality while `std::set::find` etc is for equivalence. Do we need to consider that? – Sep 16 '15 at 04:19
@NickyC I know that *theoretically* they are different, but how often is that the case in the real world? I think `set` and `map` (and their `multi` cousins) are the only ones where it matters, `unordered_set` and `unordered_map` should use equality. – Mark Ransom Sep 16 '15 at 04:23
@JamesAdkison This is SFINAE and it works since C++11. There is no lambda here, but that is also C++11. – Potatoswatter Sep 16 '15 at 04:49
@Potatoswatter Yes, you're correct there is no lambda expression. My mistake. I quickly glanced at it and saw the `-> decltype(...)` return syntax which I've only really seen with lambda expressions. – James Adkison Sep 16 '15 at 05:05
+1, thanks for adding the details. The SFINAE disconnect for me was that I'm not familiar with "expression SFINAE" so I'll look that up. – James Adkison Sep 16 '15 at 05:12
1

TIL the int/long trick for overload selection. Although I would personally use two base and derived tag classes to more clearly express the hierarchy (like the iterator tags) – TemplateRex Sep 16 '15 at 05:46
my VS '13 have no problem with this code – sp2danny Sep 16 '15 at 08:10
@sp2danny MSVC's expression SFINAE is...spotty. STL [described how their standard library uses it](http://lists.boost.org/Archives/boost/2015/05/222101.php) as "1. Write the expressions required by `is_assignable` and `allocator_traits`. 2. Hope it works. 3. Complain to the compiler team when it explodes." – T.C. Sep 16 '15 at 08:16
@NickyC I considered that a property of the container, so the choice was in part an issue of what container you're using. That may not be correct but it's where I placed the choice. – Michael Conlen Sep 16 '15 at 13:31

C++ determine if a container has ::find()

1 Answers1