Take-home message

• Static dispatch is useful to handle uniform types without common base class
• Often used to enable faster code for subset of types
• Many ways to do it, I show here an elegant and efficient method

Basic find

• Example case: write a find function that works with many containers

  #include <iterator>  // std::begin, std::end
  #include <algorithm> // std::find
  #include <set>       // needed later
  
  template <class Container, class Value>
  auto find(Container const& c, Value const& v) {
    // ADL-friendly use of begin, end
    using std::begin; using std::end;
    return std::find(begin(c), end(c), v);
  }

• Like std::find, but we pass container and not pair of iterators

• Passing the container itself allows us to enable optimisations

• Explicit includes will be omitted in the following

Better find

• If container is std::set, can do better by calling std::set::find

// simple find, has O(N) complexity
template <class Container, class Value>
auto find(Container const& c, Value const& v) {
  // ADL-friendly use of begin, end
  using std::begin; using std::end;
  return std::find(begin(c), end(c), v);
}

// specialization for std::set, has O(logN) complexity
template <class K, class C, class A>
auto find(std::set<K, C, A> const& s, V const& v) {
  return s.find(v);
}

• Works, but we also want to support std::unordered_set and any other class which has a compatible interface, e.g. boost::set, absl::btree_set …

Generic find

• To work with any std::set-like container, need to detect find method and use it
• Use Substitution-Failure-Is-Not-An-ERROR (SFINAE)
  • Make test part of the interface: Use trailing return type and decltype

template <class Container, class Value>
auto find(Container const& c, Value const& v) {
  // ADL-friendly use of begin, end
  using std::begin; using std::end;
  return std::find(begin(c), end(c), v);
}

// implementation for set-like, delegates to `find` method, if it exists
template <class Set, class Value>
auto find(Set const& s, Value const& v) -> decltype(s.find(v)) {
  return s.find(v);
}

• Second implementation is ignored by containers without find method
• Elegant and fast to compile: No std::enable_if needed, no detection framework needed
• Are we done?

Fighting ambiguity

• Previous code works for std::vector, but fails for std::set<int>

error: call of overloaded 'find(std::set<int> const&, int)' is ambiguous

• Overload resolution first builds list of candidates from templates (substitution), then selects best match
  • Candidates for std::set<int>:

  return_type_1 find(std::set<int> const&, int const&); // from first template
  return_type_2 find(std::set<int> const&, int const&); // from second template

  • Return type is ignored in overload resolution → overloads are ambiguous
• Overload resolution prefers
  • … further specialised templates over more generic templates, e.g. these are not ambiguous

  template <class V> auto find(std::vector<int, std::allocator<T>> const& c, V const&);
  template <class T, class V> auto find(std::vector<T, std::allocator<T>> const& c, V const&);
  template <class T, class A, class V> auto find(std::vector<T, A> const&, V const&);
  template <class C, class V> auto find(C const&, V const&);

  • … exact matches over matches with implicit conversion (e.g. float -> int)

Resolving ambiguity

• Exploit second rule that exact type match is better than implicit cast

// helper class to resolve ambiguity by hand
template <int N>
struct priority : priority<N-1> {}; // derived class

template <>
struct priority<0> {}; // base class

template <class Container, class Value>
auto find_impl(Container const& c, Value const& v, priority<0>) {
  using std::begin; using std::end;
  return std::find(begin(c), end(c), v); // delegate to stdlib
}

template <class Container, class Value>
auto find_impl(Container const& c, Value const& v, priority<1>) -> decltype(c.find(v)) {
  return c.find(v); // use that find method if it exists
}

template <class Container, class Value>
auto find(Container const& c, Value const& v) {
  return find_impl(c, v, priority<1>{}); // calls find_impl with highest priority that passes substitution test
}

Summary

• Writing generic templated code often produces ambiguities
• Use priority helper type to resolve such ambiguities in an elegant and efficient way
• No need for std::enable_if or detection framework
• Compiler will inline find_impl, priority never appears in compiled code
• Technique used in stdlib and Boost implementations
• In C++20, language support to do this is added with constraints and concepts