Re: [boost] [gsoc16] Can I quickly check if the below really is the best approach?

Subject: Re: [boost] [gsoc16] Can I quickly check if the below really is the best approach?
From: Lee Clagett (forum_at_[hidden])
Date: 2016-01-14 21:07:44

At Fri, 15 Jan 2016 00:46:51 +0000 (UTC) Louis Dionne wrote:
> Niall Douglas <s_sourceforge <at> nedprod.com> writes:
> 
> > 
> > Dear Boost,
> > 
> > In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at 
> > https://goo.gl/1CQAuQ I claim "Even with all of Boost's facilities 
> > [1] and using C++ 14, this program represents the currently best 
> > available method of implementing a static constant associative map
> > of keys to values" and you can find either the code at the link or 
> > pasted below.
> > 
> > Can I quickly check here if that claim is true? Is there a better
> > way than my example program?
> 
> I don't see an __easy__ way to do better, i.e. without writing your
> own map.
> 
> 
> > BTW by static constant associative map of keys to values I mean the 
> > thing me and Tony van Eerd were speaking about here last year and
> > the year before, and indeed frequently at BlackBerry!
> > 
> > Niall
> > 
> > [1]: I believe Boost.Hana could implement a static constan 
> > associative map quite easily, but I'd be fairly sure Hana will
> > likely be beyond most students.
> 
> Only if the keys are known at compile-time. Otherwise, it's out of
> Hanaland.
> 
> Anyway, here's an attempt to implement such a map:
>     
>     https://gist.github.com/ldionne/f7ff609f00dc7025a213
> 
> I don't know if it's worthwhile, but it's there. Don't hesitate to
> let me know what you think.
> 
> Regards,
> Louis
> 

This mockup did highlight that a constexpr hash function needs to be
implemented for this potential GSoC project. `std::hash` and the boost
equivalent are not constexpr. `find_if`, also not constexpr (mentioned
in comments), should be easier to implement. Also, seeing this code made
me think about a collision threshold, which would trigger a compile-time
error if reached. A user could then tweak the load-factor, hash
function, keys, or readjust their target. The threshold would be useful
in reducing the scanning during a miss on a dense hash map, since the
max collisions would be known at compile-time. Although, static maps are
generally going to be smaller in the number of keys than the dynamic
counterparts, and increasing the load factor will leave gaps in the
hash map (which identify a miss), so maybe this won't be useful.

Lee