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
> > can generalize searching in the sorted associative containers. I want to
> > 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>
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk