# Discrete selector

## Background

I tried to make the underlying container resizable if the corresponding weights are provided. But then, I faced a problem: C++ doesn't have standard interface for resize() or push_back()/insert(). As a result, I had to fall back to solving a much more simple problem:

Select an element in [container.begin(), container.end()) according to discrete distribution.

discrete_select.hpp

#ifndef AREA51_DISCRETE_SELECT_HPP
#define AREA51_DISCRETE_SELECT_HPP

#include <random>
#include <iterator>
#include <utility>

template <typename Container, typename PredefinedGenerator>
class discrete_select
{
const Container container;
PredefinedGenerator generator;
std::discrete_distribution<typename std::iterator_traits<typename Container::const_iterator>::difference_type> distribution;
public:
using iterator = typename Container::const_iterator;

template <typename OtherContainer, typename ... GeneratorArgs, typename InputIterator>
discrete_select(OtherContainer&& container_,
InputIterator weights_first,
InputIterator weights_last,
GeneratorArgs&& ... gen_args):
container(std::forward<OtherContainer>(container_)),
generator(std::forward<GeneratorArgs>(gen_args)...),
distribution(weights_first, weights_last)
{}

//rule of 0

iterator operator()()
{
return std::next(container.begin(), distribution(generator));
}

const Container& underlying_container()
{
return container;
}
};

template <typename PredefinedGenerator, typename Container, typename InputIt, typename ... GeneratorArgs>
auto discrete_selector(Container&& container, InputIt first, InputIt last, GeneratorArgs&& ... gen_args)
{
return discrete_select<std::decay_t<Container>,
PredefinedGenerator>(std::forward<Container>(container),
first,
last,
std::forward<GeneratorArgs>(gen_args)...);
}

#endif //AREA51_DISCRETE_SELECT_HPP


Demo:

#include <random>
#include <vector>
#include <iostream>
#include <string>
#include <array>
#include <map>
#include <stdexcept>

#include <discrete_select.hpp>

int main()
{
std::array<std::string, 9> names
{
"Annie",
"Ashley",
"Beatrice",
"Cassandra",
"Garrick",
"James",
"Jay",
"John",
"Peter"
};

std::array<unsigned int, 9> weights
{
1,
2,
1,
2,
1,
2,
1,
2,
1
};

auto selector = discrete_selector<std::mt19937_64>(names, weights.begin(), weights.end());

unsigned int sum = 0;
std::map<std::string, unsigned int> selection_count;
unsigned int sample_count = 10'000;
for (std::size_t i = 0; i < sample_count; ++i)
{
auto which = selector();
++selection_count[*which];
}

for (const auto& kv: selection_count)
{
std::cout << kv.first << " has been selected " << kv.second << " times\n";
sum += kv.second;
}

if (sum != sample_count)
{
throw std::logic_error("sum of selection counts is not equal to sample count");
}
}


## Possible output:

Annie has been selected 773 times
Ashley has been selected 1575 times
Beatrice has been selected 750 times
Cassandra has been selected 1462 times
Garrick has been selected 789 times
James has been selected 1551 times
Jay has been selected 765 times
John has been selected 1588 times
Peter has been selected 747 times


## Design decisions

• No checks if amount of provided weights is the same as container size.

It would be simple to do, but I don't know if it is need. I don't think this is the biggest problem.

• Quite hard to manage dependency between weight and an element.

Since I'm unaware of how the weights are generated, I don't know of convenient and efficient way of doing this. So I decided to just leave it out for the user.

• Factory function.

The code is oriented for C++14 users, and I believe it is impossible to detect the PredefinedGenerator type just looking at input arguments. So, this is just a convenience.

• Returning an iterator.

I'm not sure why I've done this, but my intuition tells me this would be better. It provides more information, so users could do something like std::distance(underlying_container().begin(), selected) to know the index of the selected element.

## Concerns

• Too complex dependency management between weights and elements
• Interface usability
• General code quality

This looks pretty good in general to my eyes, however, there are a few alterations I would do:

I see no real need for discrete_select to make a copy of the source data. It's an adapter, I would make container a const reference, and create a wrapper around this + a container if I ever need an owning version.

To elaborate on this: I would operate on a pair of iterators for the source container instead of a range. This will allow you to apply your code to sub-ranges.

If you want to stick with the container-based interface, I think the OtherContainer template parameter in discrete_select's constructor is just overkill. You can get forwarding semantics by simply taking the object by value:

template <typename ... GeneratorArgs, typename InputIterator>
discrete_select(Container container_,
InputIterator weights_first,
InputIterator weights_last,
GeneratorArgs&& ... gen_args):
container(std::move(container_)),
generator(std::forward<GeneratorArgs>(gen_args)...),
distribution(weights_first, weights_last)
{}


Similarly to my comments related to the container, I would also pass the generator as reference. If I were to use this, I would really need the ability to share the random number generation with other systems in order to maintain program-wide determinism (if only for testing).

• It just came to me that you’re that Frank. I’m happy to see you back! We certainly need some diversity of opinions. Nov 4, 2017 at 7:50

No checks if amount of provided weights is the same as container size.

It would be simple to do, but I don't know if it is need. I don't think this is the biggest problem.

It's currently the biggest problem. Let's have a look at

const std::vector<int> empty;
auto weights = {0.5,0.5};

auto selector = discrete_selector<std::mt19937_64>(empty, weights.begin(),weights.end());


As soon as we use selector we get undefined behaviour. This holds for all weights that have more entries than the container. You can put that risk on your user, but you then there should be at least some comment.

Even better, add some documentation. As long as you're the only user, you might want to skip documentation, but even after as little as three months you'll be glad to find some lines that explain how to use discrete_selector.

I concur with Frank, by the way. I don't think that a copy of the container is necessary. I don't think that a container is necessary at all. We can make discrete_selector a lot more powerful if we simply strip its container:

template <typename PredefinedGenerator>
class discrete_select
{
PredefinedGenerator generator;
std::discrete_distribution distribution;
public:

template <typename ... GeneratorArgs, typename InputIterator>
discrete_select(InputIterator weights_first,
InputIterator weights_last,
GeneratorArgs&& ... gen_args):
generator(std::forward<GeneratorArgs>(gen_args)...),
distribution(weights_first, weights_last)
{}

size_t size() const {
return distribution.max();
}

/**
* @brief Draws a random element from @a container's first size() items.
* @pre std::distance(std::begin(container), std::end(container))
*      must be at least size(), otherwise the behavior is undefined.
*/
template <typename Container>
auto operator()(Container && container) -> decltype(std::begin(container))
{
using std::next;
using std::begin;
return next(begin(container), distribution(generator));
}
};

template <typename PredefinedGenerator, typename InputIt, typename ... GeneratorArgs>
auto discrete_selector(InputIt first, InputIt last, GeneratorArgs&& ... gen_args)
{
return discrete_select<PredefinedGenerator>(
first,
last,
std::forward<GeneratorArgs>(gen_args)...);
}


Note that std::begin instead of .begin() makes it possible to use an array. Also, std::begin is one of the functions that a user may overload. The documentation example above uses Doxygen with JavaDoc style, but it's just an example.

Unfortunately, we lose the difference_type as discrete_distribution's underlying type on the way, but that's the price we pay for not knowing the container at all.

We can model your original variant now as

const auto data = makeData();
const auto weights = makeWeights();

auto selector = [&data,
distribution = discrete_selector<std::mt19937_64>(weights.begin(),weights.end())]() {
return distribution(data);
};


The user can now choose whether they want to copy data or to use a reference. It's a little bit more flexible, but we're now very close to pure lambda usage in terms of usability:

auto selector = [ gen = std::mt19937_64{}
, dc = std::discrete_distribution(weights.begin(), weights.end())](auto && container) {
return std::next(std::begin(container), dc(gen));
};


I guess that shows more what is possible with C++14 lambda initialization than actually reviewing your code, so let's get back to your code.

Well, there's nothing else to say, to be honest. Your code was cleanly written, and if you really want to couple the container and the discrete selection strongly there's nothing to improve (aside from using std::begin). As Frank said, I think the OtherContainer is an overkill, but if we ignore that it's a solid piece of code.

• Dang, I just assigned the bounty. Nov 8, 2017 at 19:22
• @Incomputable ¯\_(ツ)_/¯. It's not upsetting. It's my own fault for not looking into c++ lately.
– Zeta
Nov 8, 2017 at 19:25
• C++ tag has quite low activity in terms of answerers in general lately (though Frank was doing great job). I'll try to not assign the bounty until the very end next time. Thanks for the answer! Nov 8, 2017 at 19:27