Home > OS >  c map and unordered_map template parameter: check for common behavior using c 20 concepts
c map and unordered_map template parameter: check for common behavior using c 20 concepts

Time:11-10

In short:

  • it is possible to write a C 20 function that accepts as argument a map, unordered_map or any other (present or future) implementation of a map ?

  • if I want restrict some parameter of a template to values with the behavior of a map (map, unordered_map or any other that appears), which C 20 concept must I use?

Long explanation:

When switching from one programming language to another, it is usual that you miss some features of the previous one in the next one. Usually that does means one language better than another (please, no answers nor comments to start a language war) , but is the result of design decisions in the languages and personal preferences of the coder.

In particular, when switching from Java to C , I miss the strongly structured schema of classes of Java. By example, there are one interface Map that defines what is expected of a Map, and there are the different implementations (HashMap, TreeMap, ...) of it, optimized to some scenarios. In this way, the user can create code independent of the implementation (except when constructing the container). In C , the are two usual map templates, "map" and "unordered_map":

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    class map
    { ...


template<typename _Key, typename _Tp,
       typename _Hash = hash<_Key>,
       typename _Pred = equal_to<_Key>,
       typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
    class unordered_map
    { ...

as you can see, they do not share any common base class, thus, it is not possible (?) define an user function that accepts both kind of maps.

In addition, C 20 templates allows "concepts" to restrict the template parameters. How to write a concept equivalent to Java "<T implements Map<String,Integer>" ?. It seems necessary reimplement as concepts near than all class interfaces (?).

CodePudding user response:

There's no unsorted_map in the C standard libraries that I'm aware of, so I assume you mean std::unordered_map defined in header <unordered_map>. I also assume that by saying

I want restrict some parameter of a template to values with the behavior of a map

you mean that you want a template type parameter to be a map-like type. I can actually answer both parts of this question with one function prototype (see doMapStuff below). First, you need to check if a given type is a "map" or "map-like".

Checking the argument type

Normally, you need first some sort of interface to check if a member has specific common members. But because we're just checking if a type is "map-like", we can just check member types. In the case of map-like types, a simple way would be to test the value_type, key_type, and mapped_type member types.This can easily be done even without C 20
Starting with C 11, we can use std::is_same<T> with a static assert like this:

template<class MapTy>
struct is_map_type : std::is_same<typename MapTy::value_type, std::pair<const typename MapTy::key_type, typename MapTy::mapped_type>> {};

Or, in C 17 and onwards you can even do this (using C 17's std::is_same_v helper):

template<class MapTy>
constexpr bool is_map_type_v = std::is_same_v<typename MapTy::value_type, std::pair<const typename MapTy::key_type, typename MapTy::mapped_type>>

What these do is essentially check if the template type's value_type (which exists for many different collection types) is exactly astd::pair of the type's const key_type and mapped_type. This is true and thus will check for "any" map-like type, including std::multimap and std::unordered_multimap. There are multiple ways to implement is_map_type, even Pre-C 11, some of which can be seen in this StackOverflow question (my code snippet above was partially taken from that question).

However, if you specifically want to use C 20 concepts, it's also very simple to do so if you want to implement it the same way:

template<class MapTy>
concept is_map_type = std::is_same_v<typename MapTy::value_type, std::pair<const typename MapTy::key_type, typename MapTy::mapped_type>>

Or if you want to use C 20's built-in std::same_as concept:

template<class MapTy>
concept is_map_type = std::same_as<typename MapTy::value_type, std::pair<const typename MapTy::key_type, typename MapTy::mapped_type>>;

The actual function

it is possible to write a C 20 function that accepts as argument a map, unsorted_map or any other (present or future) implementation of a map ?

if I want restrict some parameter of a template to values with the behavior of a map (map, unsorted_map or any other that appears), which C 20 concept must I use?

You can actually do both with one function, like I said, both with and without C 20.
In C 11 onward:

template <class MapTy>
void doMapStuff(const MapTy& m) { //function argument doesn't have to be const reference, I'm just doing that in the example
    static_assert(is_map_type<MapTy>::value, "Passed map type isn't a valid map!");
    //Or, if using the C  17 onward version:
    static_assert(is_map_type_v<MapTy>, "Passed map type isn't a valid map!");
    //Do something with argument 'm'...
}

Or, using C 20 requires with the C 20 concept we made:

template <class MapTy>
requires is_map_ty<MapTy>
void doMapStuff(const MapTy& m) {
    //...
}

Basically, in either version the function will make sure that the passed template parameter will always satisfy the requirements we set for our map-like type (which in this case checks value_type, key_type, and mappped_type like I said). Otherwise, the program won't compile; In the case of the static_assert version, you'll get the message string and a compilation error during compiling. With the C 20 concept version, you'' get a compilation error saying that the arguments passed to the doMapStuff are of incorrect type.

Since the template type is used as the type of the first argument, you can use the function like this (without having to explicitly specify the type separately):

std::map<std::string, int> myMap;
doMapStuff(myMap);
//...
std::vector<int> myVec;
doMapStuff(myVec); //compile error! MapTy = std::vector<int>

CodePudding user response:

Java has its own way to implement generics, and for that in C we have templates. Therefore, the answer to your first question is "just use a template".

But it's important to understand that when you define a templated function you are not defining an actual function, you are defining a "recipe" that the compiler can use to create a function. The compiler will create a different function (a template instantiation, if you will) for every different parameter type that is used in the template. This is all done at compile type and thus with templates you get static polymorphism.

Consider the following code

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

template <typename T>
void print(const T& map) {
    std::cout << "Map:\n";

    for(const auto& [key, value] : map) {
        std::cout << "  " << key << ": " << value << "\n";
    }
}

int main(int argc, char* argv[]) {
    std::map<std::string, double> m;
    std::unordered_map<std::string, double> m2;

    m.insert({"one", 1});
    m.insert({"two", 2});
    m.insert({"three", 3});

    m2.insert({"ten", 10});
    m2.insert({"twenty", 20});
    m2.insert({"thirty", 30});

    print(m);
    print(m2);

    return 0;
}

Running this program produces

Map:
  one: 1
  three: 3
  two: 2
Map:
  thirty: 30
  twenty: 20
  ten: 10

This will work for any type as long as the type passed to print can be iterated with a range for, and each "element" can be decomposed into two values using structured binding. If you use some method more specific to a map, for instance insert, then the type provided to the print function must also have that method defined.

Now let's confirm that indeed we have two different functions in the binary. Suppose the generated binary name is "main", we can inspect the generated binary using the nm program in Linux to see search for functions named "print" in the binary.

With

nm -C main | grep print

we get something like

00000000000033f1 W void print<std::unordered_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, double, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, double> > > >(std::unordered_map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, double, std::hash<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, double> > > const&)
00000000000032b3 W void print<std::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, double, std::less<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, double> > > >(std::map<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, double, std::less<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, double> > > const&)

The output is a bit ugly, but we can see that we get two completely independent functions. If we add a std::unordered_map<std::string, int> variable and use the print function to print it, we will get another implementation of print, since that is a different type.

What if we want to print a std::vector? A vector supports range for (any type that has a begin and end methods returning iterators will work), but if each element in the vector cannot be decomposed into two values with structured binding, then it will not work and we get a compile error. That means something like std::vector<std::pair<double, double>> will work, but std::vector<double> won't.

But our print function prints "Map" in the beginning it could be better if it didn't match std::vector<std::pair<double, double>> at all. That comes to your second question. Templates are "too flexible" and that can cause problems (including hard to understand error messages). Sometimes we want to reduce that flexibility.

To illustrate this, let's try to use print with a std::vector<double>.

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <vector>

template <typename T>
void print(const T& map) {
    std::cout << "Map:\n";

    for(const auto& [key, value] : map) {
        std::cout << "  " << key << ": " << value << "\n";
    }
}

int main(int argc, char* argv[]) {
    std::map<std::string, double> m;
    std::unordered_map<std::string, double> m2;
    std::vector<double> v{1, 2, 3};

    m.insert({"one", 1});
    m.insert({"two", 2});
    m.insert({"three", 3});

    m2.insert({"ten", 10});
    m2.insert({"twenty", 20});
    m2.insert({"thirty", 30});

    print(m);
    print(m2);
    print(v);

    return 0;
}

If we try to compile this we get an error like

<path>/main.cpp: In instantiation of ‘void print(const T&) [with T = std::vector<double>]’:
<path>/main.cpp:47:10:   required from here
<path>/main.cpp:11:21: error: cannot decompose non-array non-class typeconst double11 |     for(const auto& [key, value] : map) {
      |                     ^~~~~~~~~~~~

We can define a separated print function for std::vector<T>. For instance, running the code below

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <vector>

template <typename T>
void print(const T& map) {
    std::cout << "Map:\n";

    for(const auto& [key, value] : map) {
        std::cout << "  " << key << ": " << value << "\n";
    }
}

template <typename T>
void print(const std::vector<T>& v) {
    std::cout << "v: [";
    for (const auto& elem : v) {
        std::cout << elem << ", ";
    }
    std::cout << "]\n";
}

int main(int argc, char* argv[]) {
    std::map<std::string, double> m;
    std::unordered_map<std::string, double> m2;
    std::vector<double> v{1, 2, 3};

    m.insert({"one", 1});
    m.insert({"two", 2});
    m.insert({"three", 3});

    m2.insert({"ten", 10});
    m2.insert({"twenty", 20});
    m2.insert({"thirty", 30});

    print(m);
    print(m2);
    print(v);

    return 0;
}

results in

Map:
  one: 1
  three: 3
  two: 2
Map:
  thirty: 30
  twenty: 20
  ten: 10
v: [1, 2, 3, ]

That is good, but what if we want our print function for vectors to work with anything that behaves like a vector? If we use just void print(const T& v) for our "vector-like" print function we get a compile error due to a redefinition of print. We have to limit each print function to work with disjoints "sets of types", each obeying some condition.

Previously to c 20 your option was using type traits with static assert (previous to C 17) or with if constexpr. With C 20 you get a better (simpler) way using concepts.

Arastais's answer covers this and I'll just add a few comments. Requiring existence of value_type and key_type is perfectly fine and any third party "map-like" class is encouraged to implement these aliases as a way to work with generic code (your templates) that were created with the STL containers in mind. That is why the STL containers have these aliases1 in the first hand, to make it easier to write generic code. But, it is possible that some third map types does not have these aliases while still having a "map-like" interface2 as far as your use of that "map-like" type is concerned about. In that case you might consider using the existence of the actual used member functions as the condition for accepting a template. This is where C 20 concepts really shine. It's really easy to define such concepts either combining existing concepts or using requires expressions.

Footnotes

1 See the "Member types" section in cppreference for stl types, such as vector, unordered_map, set, etc.

2 Maybe all you need is the insert method, or accessing a value using something lime mymap[key], for instance. If that is enough you can use that as your "map interface" when defining the conditions.

  • Related