Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)

Subject: Re: [boost] [Hana] Announcing Hana's formal review next week (June 10th)
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-06-12 16:29:17

Paul Fultz II <pfultz2 <at> yahoo.com> writes:

> 
> > Actually, I just realized something. While it is documented that Map and
> Set
> > require compile-time Comparable keys, there are some operations that make
> > sense to perform on Sets and Maps with runtime-Comparable keys.
> 
> Would this even give good performance? It seems there would need to be
> sorting or some form hashing for this to reasonable for runtime.

Indeed, a naive implementation would be O(n^2). However, the interest of 
providing this might be if you have mixed compile-time and runtime objects 
in your set. Then, part of the comparisons (or maybe even all of them) could
be avoided at runtime because of that compile-time information:

    auto xs = make_set("huge-string"s, int_<1>);
    auto ys = make_set("huge-string"s, int_<2>);
    assert(xs != ys);

In theory, the above can be done at compile-time, because we could compare
int_<1> with "huge-string"s and then with int_<2>, and then conclude that
the sets are different at compile-time because they have the same size but 
we can't find int_<1> in ys.

I'm not sure how clever Hana would need to be to achieve this, and I'm also
not sure whether that's very useful. I'll have a look at the problem and 
only then I'll be able to take a good decision for the future. For now,
I think the only sane decision is to support compile-time keys only.

Regards,
Louis