How to implement heterogenous lookup aka specialize a template class minimizing code repetition

Question

Consider a class like this (omitting details):

template<typename K, typename V>
class my_flat_map
{
    // A lot of member functions taking a const ref to key
    auto find(K const& key) { /*...*/ }
    auto contains(K const& key) { /*...*/ }
    auto insert_or_assign(K const& key, V const& val) { /*...*/ }
    auto insert_if_missing(K const& key, V const& val) { /*...*/ }
    // ...
};

When instantiating the template with a string-like key type I'd like to have all those member functions just accepting the corresponding string_view instead of a const reference to the actual key type. I know that I can obtain this with a partial specialization for each possible string class:

template<typename V>
class my_flat_map<std::u32string,V>
{
    auto find(std::u32string_view key) { /*...*/ }
    // ...
};

template<typename V>
class my_flat_map<std::u16string,V>
{
    auto find(std::u16string_view key) { /*...*/ }
    // ...
};

template<typename V>
class my_flat_map<std::u8string,V>
{
    auto find(std::u8string_view key) { /*...*/ }
    // ...
};

template<typename V>
class my_flat_map<other::esotic_string,V>
{
    auto find(other::esotic_string_view key) { /*...*/ }
    // ...
};

// ...

The bodies of all the member functions are exactly the same, the only change is the signature. Is there a mechanism to express this without repeating all the code?

Answer 1

Approach A

You could add an alias to your class:

#include <string>
#include <string_view>

// for all non-string types, we fall back to const T&
template <typename T>
struct key_view { using type = const T&; };

// For any specialization of std::basic_string, we use the
// corresponding std::basic_string_view.
// For example, key_view<std::string>::type = std::string_view
template <typename Char, typename Traits, typename Alloc>
struct key_view<std::basic_string<Char, Traits, Alloc>> {
    using type = std::basic_string_view<Char, Traits>;
};

// If the key is already a std::basic_string_view, we just use that as the type.
template <typename Char, typename Traits>
struct key_view<std::basic_string_view<Char, Traits>> {
    using type = std::basic_string_view<Char, Traits>;
};

template<typename K, typename V>
struct my_flat_map
{
    // No major change to the flat_map needed, we just use this alias
    using key_view = key_view<K>::type;

    auto find(key_view key) { /*...*/ }
    auto contains(key_view key) { /*...*/ }
    auto insert_or_assign(key_view key, V const& val) { /*...*/ }
    auto insert_if_missing(key_view key, V const& val) { /*...*/ }
    // ...
};

Without any further changes to my_flat_map, you can add more partial specializations of key_view to handle more string-like types (perhaps Qt or boost strings).

Further Notes

Also note that using key_view in insert_ functions makes no sense. When inserting, the standard library usually uses two overloads for K&& and const K&. You can't insert a view anyway, so keep it:

auto insert_or_assign(K const& key, V const& val) { /*...*/ }
auto insert_or_assign(K && key, V const& val) { /*...*/ }
auto insert_or_assign(K const& key, V && val) { /*...*/ }
auto insert_or_assign(K && key, V && val) { /*...*/ }

To avoid repetition, you can use a function template instead. Look into std::map::try_emplace for design inspiration:

template <typename Key, typename... Args>
auto try_emplace_or_assign(K && key, Args && ...args) { /*...*/ }

Approach B

You can simply turn some operations into templates to generally support heterogeneous lookup, not just in special cases like std::string_view:

#include <concepts>

template <typename T, typename U>
concept equality_with_impl = requires (const T& a, const U& b) {
    { a == b } -> std::convertible_to<bool>;
};

template <typename T, typename U>
concept equality_with = equality_with_impl<T, U> && equality_with_impl<U, T>;

template<typename K, typename V>
struct my_flat_map
{
    template <equality_with<K> T, typename Equal = std::ranges::equal_to>
    auto find(const T& key, Equal equal = {}) { /*...*/ }
    // ...
};

Now, if the user calls my_flat_map<std::string, ...>::find with a const char*, std::string, or std::string_view, it would always work because std::string has a == operator for these.

The user can also provide a custom Equal function object in case there is no appropriate ==.

---

Note: if you're wondering why both equality_with and equality_with_impl are necessary, refer to: Why does same_as concept check type equality twice?

Answer 2

If you want to map one type, K, to another, the argument to find, you can write a trait and specialze it:

template <typename K>
struct find_arg;

template <typename K>
using find_arg_t = typename find_arg::type;

// specialize for each type:
template <> struct find_arg<std::u16string> {
     using type = std::u16string_view;
};
// ...

However, std::u16string is just an alias for std::basic_string<char16_t> just as std::u16string_view is an alias for std::basic_string_view<char16_t>. Further, std::basic_string::CharT is the character type of the string. Hence, you can save all the above boilerplate and use std::basic_string_view< typename K::CharT>. And if other::esotic_string does not have a CharT (it should) you can fall back to the above that uses CharT when available and your custom specialization otherwise.

Answer 3

You specialize the class by checking whether basic_string_view can be constructed with the object of type const K:

template<typename K, typename V>
class my_flat_map
{
  // A lot of member functions taking a const ref to key
  auto find(K const& key) { /*...*/ }
  auto contains(K const& key) { /*...*/ }
  auto insert_or_assign(K const& key, V const& val) { /*...*/ }
  auto insert_if_missing(K const& key, V const& val) { /*...*/ }
  // ...
};

template<typename K, typename V>
  requires requires (const K& key) { 
    std::basic_string_view{key}; 
  }
class my_flat_map<K, V>
{
  using string_view_type = decltype(
    std::basic_string_view{std::declval<const K&>()}
  );
  auto find(string_view_type key) { /*...*/ }
  // ...
};

which covers other string-like types such as const char* or std::span<char8_t>.