Why are c++11 random distributions mutable?

I thought that the value generated by the c++11 random distribution (uniform_int_distribution, for instance), depends only on the state of the generator which is passed to the operator(). However, for some reason there is no const specifier in the signature of operator(). What does that mean, and how should I pass the distribution as a function parameter? I thought I had to pass it as any non-mutual parameter: by const reference, but now I'm not sure.

I misunderstood the question at first, however, now that I understand, it's a good question. Some digging into the source of the implementation of <random> for g++ gives the following (with a few bits left out for clarity):

template<typename _IntType = int>
  class uniform_int_distribution
  {

  struct param_type
  {
    typedef uniform_int_distribution<_IntType> distribution_type;

    explicit
    param_type(_IntType __a = 0,
       _IntType __b = std::numeric_limits<_IntType>::max())
    : _M_a(__a), _M_b(__b)
    {
      _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
    }

     private:
    _IntType _M_a;
    _IntType _M_b;
};

public:
  /**
   * @brief Constructs a uniform distribution object.
   */
  explicit
  uniform_int_distribution(_IntType __a = 0,
           _IntType __b = std::numeric_limits<_IntType>::max())
  : _M_param(__a, __b)
  { }

  explicit
  uniform_int_distribution(const param_type& __p)
  : _M_param(__p)
  { }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
    { return this->operator()(__urng, this->param()); }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
       const param_type& __p);

  param_type _M_param;
};

If we squint past all the _, we can see that it has only a single member parameter, param_type _M_param, which itself is simply a nested struct holding 2 integral values - in effect, a range. operator() is only declared here, not defined. Some more digging brings us to the definition. In lieu of posting all the code here, which is pretty ugly (and rather long), it suffices to say that nothing is mutated inside this function. In fact, adding const to definition and declaration will happily compile.

The question then becomes, is this true for every other distribution? The answer is no. If we look to the implementation for std::normal_distribution, we find:

template<typename _RealType>
template<typename _UniformRandomNumberGenerator>
  typename normal_distribution<_RealType>::result_type
  normal_distribution<_RealType>::
  operator()(_UniformRandomNumberGenerator& __urng,
     const param_type& __param)
  {
result_type __ret;
__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
  __aurng(__urng);

    //Mutation!
if (_M_saved_available)
  {
    _M_saved_available = false;
    __ret = _M_saved;
  }
    //Mutation!

This is all just theorizing, but I imagine the reason it is not restricted to const is to allow implementers to mutate their implementation if required. Further, it keeps a more uniform interface - if some operator() are const and some are non-const, it all becomes a bit messy.

However, why they didn't simply make them const and let the implementers utilize mutable I'm not sure. Likely, unless someone around here was involved with this part of the standardization effort, you may not get a good answer to this.

Edit: As MattieuM pointed out, mutable and multiple threads do not play nicely together.

Just as a minorly interesting aside, std::normal_distribution generates two values at once, caching one (hence the _M_saved). The operator<< that it defines actually lets you see this value before the next call to operator():

#include <random>
#include <iostream>
#include <chrono>

std::default_random_engine eng(std::chrono::system_clock::now().time_since_epoch().count());
std::normal_distribution<> d(0, 1);

int main()
{
   auto k = d(eng);
   std::cout << k << "\n";
   std::cout << d << "\n";
   std::cout << d(eng) << "\n";
}

Here, the output format is mu sigma nextval.