是否有更好的替代STL比较器的状态？
我有一个相当大的、复杂的算法，它使用std::priority_queue。在某些情况下，我希望队列是一个最小队列，而在另一些情况下，则是一个最大队列。因此，我必须提供一个比较器类型，做一个或另一个。因为比较器是一个模板参数，所以它基本上是std::priority_queue类型的一部分。因此，在任何引用队列的地方，代码都必须知道类型。
当然，有一种选择是提供一个具有状态的自定义比较器，并在每次调用operator()时在升序和降序之间进行选择，但我试图避免在每次比较时拥有这个分支的性能开销。我看到的另一个选择是复制整个算法，一个用于排序升序，另一个用于降序。
除了这个问题，还有什么更好的选择吗？
编辑：由于有些人似乎非常渴望帮助，而没有真正理解这里的问题，我将尝试详细阐述一下。
我实现的是一个外部排序算法(外部合并排序)。该算法在合并阶段使用std::priority_queue。现在，排序可以是升序的，也可以是下降的。对于这两种情况，std::priority_queue比较器必须是不同的。您可能会想到，一个简单的排序算法可以很容易地参数化，以便像这样处理升序/降序：
// psuedocode...
if (ascending) {
if (a > b) // do something
} else {
if (a < b) // do something
}这方面的一个问题是，必须在排序循环的每个迭代ascending 中检查标志。‘'jalf’表示编译器可以“内联”这个分支，但我认为我没有看到这种情况发生，至少在VC++中是这样的(是的，我看过一些程序集)。
现在，当使用std::priority_queue按排序顺序保存某些事情时，队列的实际类型对于升序排序和降序排序是不同的(因为比较器必须是不同的，并且它是一个模板参数)。因此，备选方案是：
case.
- Parameterize
- 复制降序的算法(函数)，排序顺序上的算法使用一个队列进行升序，对descending.
- Use使用一个不同的队列，一个具有单个状态的比较器函子(isAscending)，这样
operator()()可以为升序和descending.
- Templatize函数执行正确的比较，并要求将比较器作为模板传递，将一个函数指针作为比较器模板参数。
请注意，我是，而不是在算法期间在两个不同队列行为之间切换的(正如一些人所问的)。在算法开始时，我将队列设置为最小队列或最大队列，对于特定类型的队列仍然是这样。
现在来比较上面的选项。
选项1由于不必要的代码重复和维护(虽然它可能会产生性能最好的代码)而退出。
选项2是不可取的，因为所有额外的运行时检查和分支，以及不必要的队列创建将不会被使用。
选项3更有吸引力，因为分支被封装/隔离在比较器函子中--但仍然需要对每个比较进行运行时检查(这基本上是我想要避免的)。
选项4将问题推到了一个层次，并要求调用者知道并访问比较器函子--有点麻烦。
选项5看起来非常好--它允许比较器函数在运行时不同，而不更改队列的类型，从而提供了干净的代码。决策逻辑不需要公开给调用者(就像选项4一样)。
我在选项5中看到的唯一负面消息是，编译器可能无法通过函数指针内联调用--但在我的示例中，是这样做的，因为被调用的函数是在同一个转换单元中本地定义的。如果没有内联，我猜选项3会更好，但在我的情况下，性能更好的选项5。
而且，在我意识到选项5是可能的(一开始我没有)之后，我突然意识到使用函数指针而不是函子可能做得不多，我怀疑人们有时会跳过圈来使用函子(就像我必须要做的那样)，当函数指针可能会产生更清晰的代码时(特别是在性能不受关注的时候)。
回答 3
Stack Overflow用户
发布于 2010-10-28 15:21:55
使用模板
template <typename Comparator>
void algo()
{
std::priority_queue<int, std::vector<int>, Comparator> pqueue;
...
}-编辑
我读过你的编辑，但我还是不太明白你有什么烦恼。你说
Option 4 pushes the problem up one level and requires the
caller to know and have access to the comparator functors
-- kind of messy.无论如何，调用者将不得不在升序或不提升之间进行选择。当然，他没有必要知道使用哪种比较器类型：
void algo_ascending() {
algo<Ascending_Comparator>();
}
void algo_descending() {
algo<Descending_Comparator>();
}甚至
void algo(bool ascending) {
if (ascending)
algo<Ascending_Comparator>();
else
algo<Descending_Comparator>();
}Stack Overflow用户
发布于 2010-10-28 15:30:36
如果要使用具有状态的比较器，则不能更改该状态，因为比较器是由队列复制的。为了在创建队列之后更改比较器的状态，可以使用共享状态。
但是，在将元素添加到队列后，不应使用状态来更改比较结果。这可能会导致队列的奇怪行为。
struct shared_state_t
{
int number;
};
struct compare_t
{
bool operator <(const record_t &left, const record_t &right) const { left < right; }
tr1::shared_ptr<shared_state_t> shared;
};
void func()
{
tr1::shared_ptr<shared_state_t> state(new shared_state_t());
state->number = 42;
compare_t comp;
comp.shared = state;
std::priority_queue<record_t, vector<record_t>, compare_t> queue(comp);
// do something with queue
state->number = 999;
// compare object of queue is aware of the new state
}Stack Overflow用户
发布于 2010-10-28 18:15:38
std::priority_queue在其构造函数中接受一个比较器对象。将对象作为函数参数并将其传递给构造函数。每个调用将根据参数创建不同的容器。因此，分支只在施工时。
template<class C>
void the_algorithm(const C& compare)
{
std::priority_queue<Type> q(compare);
// ...
}
bool this_before_that(const Type& op1, const Type& op2);
// ...
{
the_algorithm(this_before_that);
the_algorithm(ThatBeforeThis_Functor());
}这里的分支计数只是按对算法调用的顺序进行的。
https://stackoverflow.com/questions/4044186
复制相似问题
腾讯云开发者
