0

我需要一长串按其中一个参数排序的对象。在 C++ 中执行此操作的最快方法是什么？我需要能够在此列表中添加和删除元素，并且仍然按该特定参数进行排序。

Class Foo {
private:
  int rank;
}

我希望我的所有Foo对象都按升序排列，当添加或删除新对象时，它应该在顺序中占据正确的位置。也可以有多个相同的对象，rank因此键值是不可能的。

知道如何在 C++ 中做到这一点吗？我正在查看make_heap()但我不确定如何将它与对象一起使用（或者是否可以使用）。

4

1 回答 1

2

首先，您可能应该operator<为Foo（类似这样的东西）定义...

inline bool operator< (const Foo& lhs, const Foo& rhs) {
  return lhs.rank < rhs.rank;
}

需要将其声明为Foo's 的朋友：

class Foo {
 public:
  explicit Foo(int rank_init) : rank(rank_init) {}
  friend bool operator< (const Foo&, const Foo&);
 private:
  int rank;
};


现在您可以创建一个std::multiset<Foo>保持Foos 升序排序的 s rank，例如

std::multiset<Foo> foo_multiset;
foo_multiset.insert(Foo(5));  // 5
foo_multiset.insert(Foo(3));  // 3, 5
foo_multiset.insert(Foo(1));  // 1, 3, 5
foo_multiset.insert(Foo(3));  // 1, 3, 3, 5
size_t erased_count(foo_multiset.erase(Foo(3)));  // 1, 5 (erased_count == 2)

但是，不能保证这将是您特定情况下的“最快”选项。您需要为此进行概要分析。根据元素的数量、插入/擦除操作的频率以及 STL 实现，您会发现 sortedstd::vector<Foo>更适合您的需求。

Scott Meyers 的有效 STL在第 23 项中描述了这种情况。

于 2012-04-11T01:46:48.143 回答