[boost] Re: Two way maps/multimaps

From: Andy Glew (glew_at_[hidden])
Date: 1999-10-08 00:16:08

I'm enjoying this discussion about two-way maps/multimaps,
since it is yet another example of the sort of internally consistent
data structure that I would like to collect - as exemplified
by my recent post on bidirectional pointers (which are
basically a two-way map, with an optimization for quick access).

Niko should probably also look at Jiri Soukup's stuff
in a recent Dr Dobb's.  http://www.codefarms.com/

> We could acomplish the structure with a second multimap (not map) as
> follows:
>  
> typedef map<key_type, value_type>  regular_map;
> typedef multimap<value_type, regular_map::iterator> reverse_map;
> 
> The reason for this is that values (of type value_type) in the
> regular_map are not unique, and thus can not be used as key in the
> reverse_map (if reverse_map is a map). 
> 
> The problem is that insertions/iterations/search are slow.
> 
> Is there any way in which i can make regular_map have key_type as its
> key and iterator to reverse_map as its value_type, and reverse_map has
> value_type as its key and iterator to regular_map as its value type. 
> Something like :
> 
> typedef map<key_type, XXXX /*itarator of reverse_map*/>  regular_map;
> typedef multimap<value_type, regular_map::iterator> reverse_map;
> 
> 'On the face of it' it looks easy but the declaration is 'recursive'.

I've encountered the same problem, e.g. with my bidirectional pointers.
In that example, I basically fudged it, by not requiring the bidirectional 
pointers to be declared in terms of each other, and instead having
them linked through another data structure that new both.

In general, C++ does not allow mutually recursive data structure definitions,
even if the recursion changes type only, and not size.

Another approach is to use casts and overlays. Evil.

Let's see about making the first approach work, with a level of indirection:

template<class KeyType, class ValueType> 
class reln_1_to_N 
{
public:
    class Pallet; // forward declaration

    typedef map<KeyType,Pallet*> forward_map_t;
    typedef multimap<ValueType,Pallet*> reverse_map_t;

    class Pallet {
        forward_map_t::iterator f;
        reverse_map_t::iterator r;
    };

    forward_map_t forward_map;
    reverse_map_t reverse_map;
    
public:
    void insert( KeyType k, ValueType v ) {
        forward_map_t::iterator f = forward_map.find(k);
        assert( f != forward_map.end() );

        Pallet* p = new Pallet;

        reverse_map_t::iterator r = reverse_map.insert(v,p);

        forward_map[k] = p;

        p->f = forward_map.find(k);
        p->r = r;   
    }

public:
    // ...   provide forward_map and reverse_map function interfaces

}

Yeah, I think this approach can work, although I hesitate to say so
since I haven't actually tested this code. But I have made it work in other
situations, and 1:N relations are somewhere near the top of my list.

---
By the way, above I use what seems to be a personal pattern,
what I call a palletized container that carries the index info.  
If anyone has seen generic descriptions of this approach, undoubtedly
under a different name, I'd appreciate hearing.
---
Oh, yeah:  in my work I often find that I want not just 1:N relations of key to value;
I usually want to establish quick links between data structures at both sides,
of whom the key is just a subfield.
In the bidirectional pointers example, I showed how to use pointers to
members as template parameters to establish such linkages.
e.g.
class Producer;
class Consumer;
class Producer {
    ...
    reln_1_to_N_base::forward_list<Consumer> consumers;
    ...
};
class Consumer {
    ...
    reln_1_to_N_base::backward_ptr<Producer> producer;
    ...
};
reln_1_to_N<Producer, Consumer, &Producer::consumers, &Consumer::producer> P_C_reln;
This allows you to say things like
    Consumer c;
    ...
    Producer* p = c->producer;
The main difference between my approach and Jiri Soukup's, so far as I can see,
is that Jiri has a preprocess that automatically generates the member declarations,
whereas I must utter them explicitly. But my approach is standard C++.
---
The level of indirection to the Pallet in reln_1_to_N is unfortunate,
and costs performance.  You can eliminate one of the indirections
- I would suggest doing so in the forward map, by defining it later,
and having the reverse_map be a simple map, with a list or map
of keys to forward_map iterators in the Pallet.
---
Damn, life would be easier if recursive definitions that did not affect size were
allowed.
 
> The situation i face is far more demanding. This type of associative
> container has to be templete base and should be useable/reusable as
> other STL containers and should provide same interface as STL
> containers.
> The regular_map could be a map or multimap and iterations/insertions/de
> letions have to be very fast.
Then use hash_map<> instead of map<>.
Red/black trees are too slow for serious work,
but are damned convenient - hash map implementations have
been really poor, so far as I can see.
---
If you only want the special type of iteration
that involves going from key to value,
or going from value to all keys, then you should
definitely consider the pointer to member template approach that
I describe above, since it creates a custom accessor for each key/value.
More general iterations....   good luck, I'd have to see exactly
what you want.