[boost] Re: Metaprogramming: map.

From: David Abrahams (dave_at_[hidden])
Date: 2003-10-01 08:13:35

Anatoli Tubman <anatoli_at_[hidden]> writes:

> Hi all:
>
> I need a metaprogramming construct which is essentially a map where both
> keys and values are types. I understand a map can be implemented as a list of
> pairs, but this is not very efficient (i.e. compilation time would suck).
>
> I need following operations:
>
> 1. Comparison for equality. Ideally, equal maps would be represented
>    identically (by the same C++ type) but this is not a hard requirement.
>
> 2. Singleton. Given a (key, value) pair, create a singleton map.

Everything is a singleton in generic programming.

> 3. Merge. Given two maps and a function "merge_values", create a merged map.
>    If a key is present in only one map, get the value from there, otherwise
>    the value is merge_values<value1, value2>::type.
>
> All operations need to be as efficient as possible.
>
> I have a solution where maps are represented by *sorted* list, but this
> requires that all values have unique and arbitrary integer keys associated
> with them (C++ types themselves are unordered). Though all requirements
> are met, this is ugly.
>
> Any ideas?

I did some research on maps and sets for the upcoming MPL book and
discovered an approach which essentially provides O(1) lookup, though
I don't think we have an implementation in the MPL just yet.
Unfortunately, I no longer have the prototype.  I'm sure Aleksey has a
copy.

You might look at http://tinyurl.com/paxu; I think that represents
Aleksey's implementation of my set prototype for the next version of MPL.
I don't see an implementation of map there, though it works on the
same basic principles.

HTH,
-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com