c++ - 自定义严格弱排序

Question

背景:我正在编写一种算法，将对象映射存储到我想要累积的关联属性。这是一个级联分配程序，它使用通过网络的预定义路径将此属性加载到网络上。该路径被定义为从网络中的原点到网络中所有点的构建前向路径。

问题:为了实现这一点，我使用了带有自定义比较器的 map

bool pathLinkComp(const PathLink* lhs, const PathLink* rhs) 
{
    return (lhs != rhs) && (lhs->cost < rhs->cost);
}

然后在我的级联方法中，我按以下方式使用它

PathLinkTripsMap myMap(pathLinkComp);
myMap[pathLinkOfInterest] = 100.0;
// populate other pathLinksOfInterest with initial values

while (myMap.size())
{
    // pop
    auto  firstIterator = myMap.end(); --firstIterator;
    PathLink* link  = firstIterator->first;
    double    trips = firstIterator->second;
    myMap.erase(firstIterator);

    // do something with the popped data

    // move the trips back onto the previous link (unless we are at the end of the path)
    PathLink* backLink = link->backLink;
    if (backLink) myMap[backLink] += trips;
}

这个问题是，如果我使用严格的弱排序，那么我最终会遇到这样的情况:如果两个 PathLink 对象具有完全相同的成本，那么它们实际上成为同一个对象以用于索引目的。如果我使用 <= 而不是 <=，我会得到正确的行为，但这显然没有给出严格的弱排序，而这正是 std::map 的比较器应该做的……这是一个大问题吗？ std::map 以这种方式运作？

或者，我如何构造我的比较器以实现严格弱和保持单独的键分开？

Answer 1

听起来您需要一个 std::multimap，它允许使用非唯一键。

顺便说一句，我认为您的比较器中不需要 (lhs != rhs) 表达式。