Boost logo

Boost :

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; 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at