std :: map <key_type,value_type> :: find(different_key_type)

Question

我有一张地图:

std::map<TyString, int> myMap;

但是,在某些情况下,我希望std::map::find通过比较来进入TyString == TyStringRef,即

myMap.find(TyStringRef("MyString"));

原因是TyString包装了一个const char *它自己分配和释放的东西.但是,对于只找到一个条目我不喜欢分配一个新的字符串,而是我只想使用引用(TyStringRef只包装一个const char *而不分配或释放内存).

当然我可以将其转换TyStringRef为a TyString,但后来我有上面描述的内存开销.

有没有一种智能的解决方法？

谢谢!

Answer 1

请注意,默认std::map::find使用operator<或用户定义的比较仿函数.所以,除非你重载operator<为TyString和TyStringRef,则无法查找在对数时间的关键.由于operator==过载,您仍然可以在线性时间内查找,但不能使用std::map::find.

为此,您应该使用一个通用算法#include <algorithm>,它独立于容器类.它可以采用任何类型T,并使用您传入的迭代器operator==的结果进行比较operator*().

std::find(sequence.begin(), sequence.end(), myKey);

但是,有一个问题:由于你有一个std::map使用迭代器对的 a ,因此将比较键值对.所以你必须使用std::find_if,它采用谓词而不是值来搜索.此谓词应返回true您要查找的元素.你想要有元素(对)first == myKey,所以你得到这样的代码:

std::find_if(myMap.begin(), myMap.end(), [](const std::pair<TyString,int> & pair) {
    return pair.first == TyStringRef("MyString");
};

这在概念上有效,但它不会使用二进制树std::map.因此,与对数时间相比,它需要线性时间std::map::find.

有一种替代方案,在开始时看起来有点奇怪,但它的优势在于它将是对数时间查找.它需要你超载operator<(TyString,TyStringRef).您可以使用相对于给定比较函数std::lower_bound来查找不小于(大于或等于)某个元素的第一个元素.

std::lower_bound(myMap.begin(), myMap.end(), TyStringRef("MyString"),
    [](const std::pair<TyString,int> & entry, const & TyStringRef stringRef) {
        return entry.first < stringRef;
    }
);

找到"下限"后,您仍然需要测试密钥是否相等.如果他们不这样做,则找不到该元素.由于所有元素可能与您正在寻找的元素相比较少,因此返回的迭代器可能是结束迭代器,不应该取消引用.所以完整的代码变成了这个,类似于std::map::find并且如果找不到密钥则返回结束迭代器:

template<class Map, class KeyCompareType,
         class Iterator = typename Map::const_iterator>
Iterator findInMap(const Map &map, const KeyCompareType &key)
{
    typedef typename Map::value_type value_type;
    auto predicate = [](const value_type & entry, const KeyCompareType & key) {
        return entry.first < key;
    };
    Iterator it = std::lower_bound(map.begin(), map.end(), key, predicate);
    if (it != map.end()) {
        if (!(it->first == key))
            it = map.end();
    }
    return it;
}

实例