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
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.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk