Boost logo

Boost :

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-01-28 00:17:37

----- Original Message -----
From: "John E. Potter" <jpotter_at_[hidden]>

> Are bidirectional maps really dynamic?
> I leave the rest for consideration of the above. It may be the case
> that bidirectional maps are only constructed and used.

Bidirectional maps really are dynamic. I've given examples before of
bidirectional maps which model monotonic piecewise linear functions (e.g.
mapping between word index and layout position in a text document, or time
and position in music, or time and word index in a speech transcription...)
in the context of our discussion on heterogeneous comparison operators with
the standard binary search functions. It's common to want to change these
things dynamically. For example, as one is editing a document in a word
processor, line breaks tend toward stability, so it's easy to imagine an
application making dynamic modifications to small regions of such a map when

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.


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