4

我有一张地图：

std::map<TyString, int> myMap;

但是，在某些情况下，我想std::map::find通过比较来输入一个条目TyString == TyStringRef，即

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

原因是 TyString 包装了const char *它自己分配和释放的 a。但是，为了只找到一个条目，我不想分配一个新字符串，而是只想使用引用（TyStringRef只包装一个 constchar *而不分配或释放内存）。

当然我可以将 转换TyStringRef为 a TyString，但是我有上面描述的内存开销。

有没有聪明的方法来解决这个问题？

谢谢！

4

2 回答 2

5

请注意，默认std::map::find使用或用户定义的比较函子。因此，除非您为andoperator<重载，否则您无法在对数时间内查找键。重载后，您仍然可以在线性时间内查找，但不能使用.operator<TyStringTyStringRefoperator==std::map::find

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

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

但是，有一个问题：由于您有一个std::map，它使用对作为迭代器，因此将比较键值对。所以你必须使用std::find_if，它需要一个谓词而不是一个要搜索的值。此谓词应返回true您要查找的元素。您想要拥有 which 的元素（对）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;
}

活生生的例子

于 2013-05-31T18:26:45.393 回答
0

您可以使用 STLport，它已经自行完成了这项工作。也许其他标准库实现也是如此？或者，您可以使用 std::find()，但这会花费您对数查找。

于 2013-05-31T18:24:32.043 回答