Re: [boost] Bidirectional map

From: Gregory Seidman (gseidman_at_[hidden])
Date: 2001-01-27 18:51:27

John E. Potter sez:
} 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 mostly agree with you, but not quite. I have often wished that map's
op[] did not insert but, instead, threw an exception if the key was not
found (especially if there were a const version that did). This
bidirectional map could take that approach.

Also, while I agree that many times a bimap would have Key1 == Key2, this
is an opportunity for partial specialization; op[] is defined for neither
if Key1 == Key2, and both if Key1 != Key2.

} 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?

I do not think it is especially useful to keep the pairs as a set. If we
one map<Key1, Key2> and one map<Key2, map<Key1, Key2>::const_iterator> then
we have the functionality we need with a minimum of overhead. A map is,
effectively, a set of pairs with a more convenient interface and a
specialized comparator. Of course, for Mto1, 1toN, and MtoN we simply
replace one or both of the maps with multimaps.

} > 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.

Since I do database research, relations and indices rather appeal to me.
In fact, the primary use I have for such a structure is to cache a table in
memory rather than doing lots of ODBC calls. Nonetheless, generalizing to
more columns is a task for another day.

} > 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->.

There is no reason to talk of "iteration over the second key" since there
is no good reason to guarantee an ordering. A single iterator is right and
proper, and should probably be exactly a map<Key1, Key2>::const_iterator. I
do like the idea of op[] which throws and exception if the key is not found
when Key1 != Key2. More comments in the code below:

} 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;
    // this needs to be const //////////////////////
    //typedef pair<Key1, Key2> value_type;
    typedef pair<const Key1, const Key2> value_type;
    ////////////////////////////////////////////////
    typedef Compare1 key1_compare;
    typedef Compare2 key2_compare;
    //I am not too familiar with the innards of Allocators, so I will not
    //comment on anything having to do with them
    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;
    // I disagree with the above iterator types; try these:
    typedef map<Key1, Key2>::const_iterator iterator;
    typedef iterator const_iterator;
    ///////////////////////////////////////////////////////
    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;
    // reverse iterators are inappropriate; we should not guarantee an
    // ordering, therefore reverse is not meaningful

    // I don't know what you mean here
    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;
    // bad, bad, bad; no ordering, one iterator type, and it's const
    const_iterator begin() const;
    const_iterator end() 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;
    // I don't like the name, and they are no different from op[] in that
    // they have all the same problems with insertion (though it works if
    // Key1 == Key2). No, use a find returning an iterator, just like with
    // a map. Maybe findbyfirst and findbysecond.

    //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&);
    // again with the two iterator types
    pair<iterator, bool> insert (value_type const&);
    iterator insert (iterator, value_type const&);
    ////////////////////////////////////
    template <class InputIterator>
    void insert (InputIterator, InputIterator);

    // and again
    //void erase (iterator1);
    //void erase (iterator2);
    void erase (iterator);
    ////////////
    size_type erase1 (Key1 const&);
    size_type erase2 (Key2 const&);
    size_type erase (value_type const&);
    // without an ordering guarantee, range deletion makes me edgy
    //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;

    // just one iterator type, plus I don't like numbers
    //iterator1 find1 (Key1 const&) const;
    //iterator2 find2 (Key2 const&) const;
    iterator findbyfirst (Key1 const&) const;
    iterator findbysecond (Key2 const&) const;
    ////////////////////////////////////////////////////
    // typo below, key1 and key2 should be capitalized
    size_type count1 (key1 const&) const;
    size_type count2 (key2 const&) const;
    // since we can do these more efficiently by operating on internal
    // structures, it is worth exposing them. Still, just one iterator
    //iterator1 lower_bound1 (Key1 const&) const;
    //iterator2 lower_bound2 (Key2 const&) const;
    //iterator1 upper_bound1 (Key1 const&) const;
    //iterator2 upper_bound2 (Key2 const&) const;
    iterator lower_bound1 (Key1 const&) const;
    iterator lower_bound2 (Key2 const&) const;
    iterator upper_bound1 (Key1 const&) const;
    iterator upper_bound2 (Key2 const&) const;
    //////////////////////////////////////////////////////////////////
    // these require a guaranteed order on both keys, plus two separate
    // iterators
    //pair<iterator1, iterator1> equal_range1 (Key1 const&) const;
    //pair<iterator2, iterator2> equal_range2 (Key2 const&) const;
    ///////////////////////////////////////////////////////////////////
};

//my additions below

//Key1 == Key2
template <class Key, class Key,
        class Compare1 = less<Key>, class Compare2 = less<Key>,
        class Allocator = allocator<pair<Key, Key> > >
class bimap : public map1to1<Key, Key, Compare1, Compare2, Allocator> {
public:
    //copy constructors and such just like above
};

//Key1 != Key2
template <class Key1, class Key2,
        class Compare1 = less<Key>, class Compare2 = less<Key>,
        class Allocator = allocator<pair<Key, Key> > >
class bimap : public map1to1<Key1, Key2, Compare1, Compare2, Allocator> {
public:
    //copy constructors and such just like above
    const Key2 &operator[](const Key1 &) const throws(something);
    const Key1 &operator[](const Key2 &) const throws(something);
};

--Greg