Re: [boost] Re: Bidirectional map

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-02-07 21:29:55

----- Original Message -----
From: "George A. Heintzelman" <georgeh_at_[hidden]>
> Someone else wrote:
>
> > In the same way that I believe I've shown we can generalize the binary
> > search algorithms to use heterogeneous comparison operators, I believe
we
> > can generalize searching in the sorted associative containers. I want to
see
> > a generalization of the sorted associative container which supports
> > comparison operator arguments to the searching functions, and an insert
> > function where the iterator is more than just a hint.

That was me.

> I can see ways of doing this, but most of them involve building another
> index than the one the map itself uses (eg, a map<Key,map<Key,value>
> ::iterator>).

I don't see what this buys you.

> What I don't see is how supplying this in a standard way
> buys much over rolling your own, unless you wanted to building
> something like a map that maintained indices on a list of comparator
> functions or something. I think that's going to be rather specialized.
> Could you expand on this in more detail?

Ur, geez, I have to confess that I have no clue what you're talking about.
All I can do is describe what I'm talking about.

There's a broad (?) category of 1-to-1 associations where the domain and
range have a monotonic relationship. In other words, elements of type
pair<Key,Value> assume identical orders when sorted by the key sort function
and by the value sort function.

You can search a linear array of pair<Key,Value> that is ordered according
to such an association using binary search based on either the Key or Value
type (see http://groups.yahoo.com/group/boost/files/Binary%20Search/ for
details)

Similarly, the algorithm for searching a balanced binary tree can be used to
search on either the Key or the Value type. The associative containers
provided by the standard don't allow this, though. I propose that such a
facility should be available.

-Dave