1

根据this question中使用boost::bimap的建议，我有一个关于如何解决bimap中重复键的问题。

如果我有： <key1, value1>, <key1, value2>，是否可以在 bimap 中插入两次？

我看到描述CollectionType_of的页面，默认类型是 set for bimap< CollectionType_of<A>, CollectionType_of<B> >。所以密钥在双方都是唯一的。更重要的是，我想知道是否有更好的方法可以快速找到 key1 的 value1、value2？但是 key1, 不好，因为使用值作为键进行搜索。

谢谢你的建议！

4

1 回答 1

2

您的案例需要一个自定义容器。它将有两张地图std::map<string, std::set<string>>。像这样的东西：

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 */
};

用法类似于：

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 -> ()

这种数据结构存在明显的缺陷，因为它没有清理到空集的映射。在最后一条语句中说， pic2 现在有一个空映射。您可以调整此类以确保从valueToKeysorkeyToValues映射中删除此类到空集的映射，具体取决于它是removeKey()还是removeValue()操作。

于 2013-06-11T23:09:02.660 回答