使用重复键对对象进行排序 [英] Sort objects with duplicate keys

问题描述

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

I need a long list of objects ordered by one of they're parameters. What is the fastest way to do this in C++? I need to be able to add and remove elements to this list and still be sorted by that specific parameter.

Class Foo {
private:
  int rank;
}

我希望所有我的Foo对象以升序列出，并且添加或删除新对象时，该对象应该在该顺序中排在正确的位置.相同的rank也可以有多个对象，因此不可能使用键值.

I want all my Foo objects to be listed in ascending order and when a new one is added or deleted it should take the right spot in the order. There can also be more than one object with the same rank so key-value is not possible.

有什么想法可以用C ++做到吗?我正在查看 make_heap()，但是我不确定如何使用它(或是否可以使用)对象.

Any idea how I can do this in C++? I was looking at make_heap() but I'm not sure how to use it (or if it can be used) with objects.

推荐答案

首先，您应该为Foo定义operator<(类似这样)...

First you should probably define operator< for Foo (something like this)...

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

，需要将其声明为Foo的朋友:

which will need to be declared as a friend of 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>，以使Foo的排序方式按rank升序排列，例如

Now you can create a std::multiset<Foo> which will keep the Foos sorted ascending by rank, e.g.

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的实现，您会发现排序后的std::vector<Foo>更适合您的需求.

There are no guarantees however that this will be the "fastest" option in your particular case. You'll need to profile for that. Depending on the number of elements, the frequency of insert/erase operations, and the STL implementation, you could find that a sorted std::vector<Foo> better suits your needs.

Scott Meyers的有效的STL 描述了如何在第23条中可能就是这种情况.

Scott Meyers' Effective STL describes how this could be the case in Item 23.

这篇关于使用重复键对对象进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！