CODEWITHSUNDEEP
c++design-patternsboostdictionary
CJAN.LEE
CJAN.LEE

Reputation: 1118

bimap usage for repeated keys

According to the suggestion of using boost::bimap in this question, I have a question about how to solve repeated keys in bimap.

if I have: <key1, value1>, <key1, value2>, is it possible to insert in bimap two times?

I saw the page to describe the CollectionType_of, the default type is the set for bimap< CollectionType_of<A>, CollectionType_of<B> >. So the key is unique in both sides. What's more, I want to know is there some better ways to find value1, value2 for key1 quickly? But key1, is not good, because of searching with values as keys.

Thanks for your suggestion!

Upvotes: 1

Views: 937

Answers (1)

Vite Falcon
Vite Falcon

Reputation: 6645

Your case requires a custom container. It would have two maps of std::map<string, std::set<string>>. Something like this:

template <typename K, typename V>
class ManyToManyMap
{
public:
    typedef std::set<K> SetOfKeys;
    typedef std::set<V> SetOfValues;
    typedef std::map<K, SetOfValues> KeyToValuesMap;
    typedef std::map<V, SetOfKeys> ValueToKeysMap;

private: // I usually put this to the bottom. But it's here for readability.
    KeyToValuesMap keyToValues;
    ValueToKeysMap valueToKeys;

public:
    /* I leave it to requester to implement required functions */

    void insert(const K& key, const V& value)
    {
        keyToValues[key].insert(value);
        valueToKeys[value].insert(key);
    }

    void removeKey(const K& key)
    {
        KeyToValuesMap::iterator keyIterator = keyToValues.find(key);
        if (keyToValues.end() == keyIterator) {
            return;
        }
        SetOfValues& values = keyIterator->second;
        SetOfValues::const_iterator valueIterator = values.begin();
        while (values.end() != valueIterator) {
            valueToKeys[*valueIterator++].remove(key);
        }
        keyToValues.erase(keyIterator);
    }
    /* Do the reverse for removeValue() - leaving to OP */

    SetOfValues getValues(const K& key) const
    {
        KeyToValuesMap::const_iterator keyIterator = keyToValues.find(key);
        if (keyToValues.end() == keyIterator) {
             return SetOfValues(); // Or throw an exception, your choice.
        }
        return keyIterator->second;
    }
    /* Do the reverse for getKeys() - leaving to OP */
};

Usage would be something like:

typedef ManyToManyMap<string, string> LinksMap;
LinksMap links;
links.insert("seg1", "pic1"); // seg1 -> (pic1) and pic1 -> (seg1)
links.insert("seg1", "pic2"); // seg1 -> (pic1, pic2) and pic2 -> (seg1)
links.insert("seg2", "pic1"); // seg2 -> (pic1) and pic1 -> (seg1, seg2)
....
links.removeKey("seg1"); // pic1 -> (seg2) and pic2 -> ()

There are obvious flaws in this data-structure in that it doesn't clean-up mappings to empty sets. Say in the last statement, pic2 now has an empty mapping. You can tweak this class to make sure such mappings to empty set gets removed from the valueToKeys or keyToValues maps, depending on whether it's removeKey() or removeValue() operations, respectively.

Upvotes: 2

Related Questions