Re: [boost] Bidirectional map

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-27 17:41:05

On Wed, 24 Jan 2001, George A. Heintzelman wrote:

> One of the things I find most lacking in the standard containers as 
> they stand is a bidirectional map, or in mathematical terms an 
> isomorphism, where lookups in both directions are O(log n).

This has been mentioned several times on the news groups.  There does
seem to be a demand.  Let me take a shot at what it isn't first.

   Key2 const& operator[] (Key1 const&) const;
   Key1 const& operator[] (Key2 const&) const;

1.  The only associative container which has operator[] is map and
    there is only a non-const version because it inserts.
2.  Operator[] does not throw.
3.  Operator[] can not do an insert here.
4.  Many (most?) useful bidirectional maps have Key1 == Key2.

This thing does not have an operator[].

I see it as a set<Pair<Key1, Key2> >.  This leaves four possibilities
when we project the two keys.  Map1to1 is a set<Key1> and a set<Key2>.
Map1toN is a multiset<Key1> and a set<Key2>.  MapMto1 is a set<Key1>
and a multiset<Key2>.  MapMtoN is a multiset<Key1> and a multiset<Key2>.
We could also allow associated non-key values which would then lead to
MultimapXtoY also.  What are the use cases and demands for other than
the map1to1?

> Of course, there are ways to do this. One way is to represent this 
> internally is to use two maps, each between a key and a pointer to the 
> other type, stored in the other map. But writing the bookkeeping for 
> such a container is somewhat annoying and painful, so I would rather do 
> it once in template form and then forget about it. Alternatively, you 
> might use a more explicitly-written form more purely optimized to 
> storing this special situation (say, as linked pairs with a link field 
> for each key'd item. You might even be able to generalize this to an 
> ntuple'd isomorphism with lookups on each key... ).

You could save a little space by putting all of the links needed into
one node and writing all of that code.  The number of links will depend
upon the interface required.  A simple inplementation might be a set of
pairs and a set of iterators into the first set.  This might generalize
to many keys, but it is starting to sound like a relation and indicies.
I think that interface would be different.

> However you do the 
> underlying implementation, I think that specifying an interface to such 
> a container would be useful.

Yes.  Let me take a shot at it with everything required by the standard
and variations that might be useful.  Did I miss anything?  Would usage
allow cutting everything related to iteration over the second key?  That
would give a single iterator and come close to a standard associative.
The iterators are constant iterators which return a const& from operator*
and a const* from operator->.

John

template <class Key1, class Key2,
        class Compare1 = less<Key1>, class Compare2 = less<Key2>,
        class Allocator = allocator<pair<Key1, Key2> > >
class map1to1 {
public :
    typedef Key1 key1_type;
    typedef Key2 key2_type;
    typedef Key2 mapped1_type;
    typedef Key1 mapped2_type;
    typedef pair<Key1, Key2> value_type;
    typedef Compare1 key1_compare;
    typedef Compare2 key2_compare;
    typedef Allocator allocator_type;
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    class const_iterator1;
    typedef const_iterator1 iterator1;
    class const_iterator2;
    typedef const_iterator2 iterator2;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef typename Allocator::pointer pointer;
    typedef typename Allocator::const_pointer const_pointer;
    typedef std::reverse_iterator1<iterator1> const_reverse_iterator1;
    typedef const_reverse_iterator1 reverse_iterator1;
    typedef std::reverse_iterator2<iterator2> const_reverse_iterator2;
    typedef const_reverse_iterator2 reverse_iterator2;

    class value_compare; // Hum, uses both compares?

    explicit map1to1 (Compare1 const& = Compare1(),
            Compare2 const& = Compare2(),
            Allocator const& = Allocator());
    template <class InputIterator>
    map1to1 (InputIterator, InputIterator,
            Compare1 const& = Compare1(),
            Compare2 const& = Compare2(),
            Allocator const& = Allocator());
    map1to1 (map1to1 const&);
    ~map1to1 ();
    map1to1& operator= (map1to1 const&);

    iterator1 begin1 () const;
    iterator2 begin2 () const;
    iterator1 end1 () const;
    iterator2 end2 () const;
    reverse_iterator1 rbegin1 () const;
    reverse_iterator2 rbegin2 () const;
    reverse_iterator1 rend1 () const;
    reverse_iterator2 rend2 () const;

    bool empty () const;
    size_type size () const;
    size_type max_size () const;

    Key2 const& at1 (Key1 const&) const;
    Key1 const& at2 (key2 const&) const;

    pair<pair<iterator1, iterator2>, bool> insert (value_type const&);
    iterator1 insert (iterator1, value_type const&);
    iterator2 insert (iterator2, value_type const&);
    pair<iterator1, iterator2> insert (iterator1, iterator2,
            value_type const&);
    template <class InputIterator>
    void insert (InputIterator, InputIterator);

    void erase (iterator1);
    void erase (iterator2);
    size_type erase1 (Key1 const&);
    size_type erase2 (Key2 const&);
    size_type erase (value_type const&);
    void erase (iterator1, iterator1);
    void erase (iterator2, iterator2);

    void swap (map1to1&);
    void clear ();

    key1_compare key1_comp () const;
    key2_compare key2_comp () const;
    value_compare value_comp () const;

    iterator1 find1 (Key1 const&) const;
    iterator2 find2 (Key2 const&) const;
    size_type count1 (key1 const&) const;
    size_type count2 (key2 const&) const;
    iterator1 lower_bound1 (Key1 const&) const;
    iterator2 lower_bound2 (Key2 const&) const;
    iterator1 upper_bound1 (Key1 const&) const;
    iterator2 upper_bound2 (Key2 const&) const;
    pair<iterator1, iterator1> equal_range1 (Key1 const&) const;
    pair<iterator2, iterator2> equal_range2 (Key2 const&) const;
    };