bimap usage for repeated keys

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.