Suggestion: Weighted random number generation using maps.

[DolphyWind]

Currently, as far as I'm concerned, the only way to get weighted random number generation is using std::discrete_distribution.

int main()
{
    std::vector<double> weights = {3, 5, 2};
    std::vector<std::string> fruits = {"Apple", "Orange", "Banana"};
    std::discrete_distribution<int> distribution(weights.begin(), weights.end());

    std::cout << fruits[Random::get(distribution)] << std::endl;

    return 0;
}

But the problem with that approach is that you have to modify one vector after a change on the other one. So, my idea is using a std::map or std::unordered_map for weighted random numbers by assuming we have a map of pairs, each containing an object and its weight. I have a code snippet that works but, I am not sure whether if it should be implemented to the library yet. And it is also a bit messy because it is my first time using std::enable_if etc.

#include <iostream>
#include <map>
#include <unordered_map>
#include <type_traits>
#include <algorithm>
#include <numeric>
#include "random.hpp"
using Random = effolkronium::random_static;

template <typename Type, typename = void>
struct is_map : std::false_type {};

template<typename Type>
struct is_map<Type, std::void_t<typename Type::key_type, typename Type::mapped_type>>
{
    template <
        typename Key,
        typename T,
        typename Hash = std::hash<Key>,
        typename KeyEqual = std::equal_to<Key>,
        typename Allocator = std::allocator< std::pair<const Key, T> >
    >
    using UnorderedMapContainer = std::unordered_map<Key, T, Hash, KeyEqual, Allocator>;

    template <
        typename Key,
        typename T,
        typename Compare = std::less<Key>,
        typename Allocator = std::allocator<std::pair<const Key, T>>
    >
    using MapContainer = std::map<Key, T, Compare, Allocator>;

    static constexpr bool value =
        std::is_same<Type, UnorderedMapContainer<typename Type::key_type, typename Type::mapped_type>>::value ||
        std::is_same<Type, MapContainer<typename Type::key_type, typename Type::mapped_type>>::value;
};

template<class MapContainer>
typename std::enable_if<
    is_map<MapContainer>::value,
typename MapContainer::key_type>::type
get(const MapContainer& container)
{
    using KeyType = typename MapContainer::key_type;
    using MappedType = typename MapContainer::mapped_type;
    using PairType = typename MapContainer::value_type;
    // We find the total weight and pick a random weight in range [0; total_weight - 1]
    MappedType total_weight = std::accumulate(container.begin(), container.end(), 0, [](MappedType val, const PairType& p){
        return val + p.second;
    });
    MappedType random_weight = Random::get(0, total_weight - 1);

    // We define the sum variable. 
    MappedType sum = 0;
    
    // We iterate through the map. We add the weight of the current pair to the sum and check if sum is greater than random_weight.
    for(auto& p : container)
    {
        sum += p.second;
        if(sum > random_weight) return p.first;
    }
    // This return value will be reached if and only if the map is empty. 
    return KeyType();
}

int main()
{
    std::unordered_map<std::string, int> fruits = {{"Apple", 3}, {"Orange", 5}, {"Banana", 2}};
    std::cout << get(fruits) << std::endl;

    return 0;
}

[ilqvya]

The library it's a simple 'get' method templated "overloads"

They should not conflict with each other, in your example it will conflict with Random::get(my_map) which returns random iterator from any container so we need to think how the final end library user interface will look like for the feature

[DolphyWind]

Do you have any ideas on how can we implement this feature other than implementing it with a different function name? If you don't, are you ok with implementing it with a different name? Also, I realized the std::void_t was not available for c++11 and c++14 so, I made my own void_t and I shortened the is_map implementation. It now checks for whether the given type has a key_type, a mapped_type and a value_type defined or not. So it now allows custom map containers to be used as long as they have these types defined.

template<typename...>
using void_t = void;

template<typename Type, typename = void>
struct is_map : public std::false_type  {};

template<typename Type>
struct is_map<Type, void_t<typename Type::key_type, typename Type::mapped_type, typename Type::value_type>> : public std::true_type{};

[ilqvya]

Actually why do you think there is a vectors modifying problem with std::discrete_distribution ?

The indexed approach can be used with existing containers while hash-map of weights need to be constructed from its values

I would appreciate to see some specific use cases for this

Also it can be implemented with existing 'get' method using some explicit types like it done already for common type numbers with a key type:Random::common

And it would be much better to return iterators instead of value copies to prevent extra copies of a possible user defined heavy types

[DolphyWind]

My problem is, as I stated before, modifying one requires a modification to another and it feels a bit unsafe. It is not a specific one, but the use case scenario I've had in my mind is that I had a box object in a game and when it got destroyed, it would spit out a random game object based on its weight.

Also, there are probably no specific use cases for this method since we can just create a map from two same size vectors, one containing unique elements, one containing weights, and vice versa. But this method, by the design of the maps, ensures that the keys are unique.

And you are right, returning iterators instead of value copies makes much more sense. This way, when the map is empty, we don't have to return a new key type, we can just return the end iterator.

[ilqvya]

Yeah, are you planning to do a PR for this ?

[DolphyWind]

By the way, I did a PR #44. In case if you missed it.

[ilqvya]

#44 (comment)