5

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

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

我可以使用任何其他 stl 容器/机制来允许三个行为属性吗？它非常类似于堆，我认为 usingmake_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();
    }
4

3 回答 3

4

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

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

然后你会自动得到 sorted 属性，你会得到恒定时间删除最低元素。

您还可以更新日志复杂性的成本值：只需从集合中删除对象并重新添加它。这将与排序容器一样快。

在集合中插入和删除速度很快。

于 2013-03-25T11:58:53.277 回答
2

我将开始使用智能指针而shared_ptr不是原始指针（原始指针很好，例如，如果它们正在观察指针，例如作为函数参数传递的指针，但是当您具有所有权语义时，例如在这种情况下，最好使用智能指针）。

然后，我将从std::vector一个容器开始。

所以，试着做吧vector<shared_ptr<MyObject>>。

您可以比较它的性能来衡量它list<shared_ptr<MyObject>>。

（还要注意，它std::list比 具有更多的开销std::vector，因为它是一个基于节点的容器，并且每个节点都有一些开销；而是std::vector分配一个连续的内存块来存储其数据，在这种情况下是shared_ptrs; 所以std::vector也更多“缓存-友好的”等）

总的来说，std::vector它提供了非常好的性能，作为“首选”容器是一个不错的选择。在任何情况下，您的里程可能会非常多，最好的办法是衡量性能（速度），以便更好地了解您的特定情况。

于 2013-03-25T11:36:17.827 回答
1

如果我正确理解您的要求，那么您正在寻找要使用的正确容器。

Indeedstd::set似乎是您想要做的事情的正确容器，但这取决于所有用例

  • 您是否需要 O(1) 访问元素？
  • 成本最高的操作是什么？

std::set使用键对元素进行排序并且不允许重复（如果您想要重复，请查看std::multiset）。添加元素时，它会自动插入到正确的位置。通常，您不想使用原始指针作为键，因为对象可以为空。

另一种选择可能是使用 a std::vector<std::shared_ptr>>，正如@MikePro 所说，将指针放在智能指针中是一个好习惯，以防止必须手动删除它们（并避免在发生异常时发生任何内存泄漏）。如果您使用向量，则必须使用诸如std::sort,std::find出现在<algorithm>header 或std::vector::insert.

通常，此图像有助于找到您的容器。它并不完美（因为您必须比显示的内容多了解一点），但它通常可以很好地完成工作：

标准容器选择

于 2013-03-25T11:49:52.833 回答