包含指向对象的指针的STL堆

Question

我有一个std::list<MyObject*> objectList容器,我需要在以下场景中进行排序和维护:

• 每个对象都有一个提供成本的字段(例如浮点值).该成本值用于比较两个对象,就好像它们是浮点数一样
• 必须订购(升序)集合,并且必须快速找到新插入元素的正确位置.
• 可以删除最低元素(就成本而言),并且还可以更新几个任意定位元素的成本.然后必须尽快重新排序该列表,利用其已经排序的性质.

我可以使用任何其他stl容器/机制来允许三种行为属性吗？它几乎像一堆,我认为使用它make_heap可能是一个很好的方式来排序列表.我需要一个指针容器,因为有几个其他数据结构依赖于这些指针.

那么我怎么能选择一个更好的容器,它也是指针友好的,并允许通过查看指向类型的比较运算符进行排序？

澄清:我需要一个最适合该场景的stl容器,并且可以成功地包装指针或引用.(例如,我简要地读到std::set容器可能是一个很好的候选者,但我没有经验).

目前的实施,基于以下答案:

struct SHafleEdgeComparatorFunctor
    {
        bool operator()(SHEEdge* lhs, SHEEdge* rhs)
        {
            return (*lhs) < rhs;
        }
    };

std::multiset<SHEEdge*, SHafleEdgeComparatorFunctor>    m_edges;

当然,SHEEdge数据结构有一个重载的运算符:

bool operator<(SHEEdge* rhs) 
    {
        return this->GetCollapseError() < rhs->GetCollapseError();
    }

Answer 1

我确实会使用std::set. 您的需求中棘手的一点是更新现有元素。

Astd::set总是排序的。您必须使用有用的比较运算符将指针包装在类中，或者必须将比较谓词传递给集合。

然后，您将自动获得排序属性，并以恒定时间删除最低元素。

您还可以更新日志复杂性中的成本值：只需从集合中删除对象并重新添加它即可。对于已排序的容器来说，这将是尽可能快的。

插入、删除速度很快。