c++ - std::sort 过火了

Question

我正在尝试使用谓词函数对对象 vector 进行排序，但遇到了一些段错误...

我有一个类Item和 vector< Item > _items 中的项目列表.我需要根据显示顺序(类的数字成员)对其进行排序，我只是调用了一个带有谓词函数的简单排序。

sort(_items.begin(), _items.end(), sort_item_by_display_order);

谓词函数在哪里

bool sort_item_by_display_order (Item i, Item j)
{
    return i.GetDisplayOrder()>j.GetDisplayOrder();
}

GetDisplayOrder 是

int Item::GetDisplayOrder()
{
    return display_order;
}

但是...我在执行此操作时遇到了一些段错误。然后，我向谓词函数添加了一个计数器来检查它被调用了多少次，我发现当它崩溃时，计数器的大小大于 vector 的大小。

阅读一些内容后，我将代码更改为使用迭代器而不是使用 .begin() 和 .end()(这不应该一样吗？!)

所以我现在拥有的是

vector<Item>::iterator it_start, it_end;
it_start = _items.begin();
it_end = _items.end();
sort(it_start, it_end, sort_item_by_display_order);

具有相同的谓词功能。

现在它没有崩溃，但是......对于我做的大部分排序，我得到的迭代次数超过了我正在排序的 vector 的大小(这可能是正常的)

所以...用_items.begin()调用排序有什么区别？或 _it_start .据我所知，它们是相同的，对吧？!

还有一点。 Item是声明为的简单基类

class Item
{
  private:
  (...)
  public:
  (...)
}

作为引用，我使用了 http://www.cplusplus.com/reference/algorithm/sort/和 http://www.codeguru.com/forum/showthread.php?t=366064 .

在第二个链接中，他们向谓词函数参数添加了一个 const 和 &，这将使我的函数类似于这样

bool sort_item_by_display_order (const Item& i, const Item& j)
{
    return i.GetDisplayOrder()>j.GetDisplayOrder();
}

但是我得到一个编译器错误:

Item.cpp|1485|error: passing `const Item' as `this' argument of `int Item::GetDisplayOrder()' discards qualifiers|

啊……问题是……我做错了什么？

Answer 1

首先，比较函数的调用次数超过集合中元素的调用次数是完全正常的。例如，当我们说排序算法的复杂度 为 O(n log n) 时，这就是部分含义。对大小为 n 的集合执行的比较次数约为 n × log(n)。 (事实上​​，n 几乎是调用它的最小 次数；否则，我们甚至无法判断集合是否已经在第一名。)

其次，当您将参数设为 const 引用时会出现错误，因为您已将 GetDisplayOrder 声明为非 const 方法。不允许在 const 对象上调用非 const 成员函数，因为编译器假定该方法将尝试修改该对象，即使在这种情况下它不会修改任何内容。在声明和定义的末尾添加const:

int GetDisplayOrder() const;

int Item::GetDisplayOrder() const {
  return display_order;
}

最后，还有段错误的问题。您在此处显示的代码不足以查明原因。您是正确的，更改将迭代器传递给 sort 的方式不应该有任何效果。我怀疑您的 Item 类需要复制构造函数和赋值运算符，但它们要么没有实现，要么没有正确实现。对 vector 进行排序显然涉及在集合中移动项目，这需要一个有效的赋值运算符。将这些项目传递给原始比较函数(按值而不是常量引用接受参数)需要一个有效的复制构造函数。如果您正在进行任何动态内存分配(例如使用 new 或 malloc)，您需要确保在分配时对内存进行“深度复制”或复制一个对象，或者您想出一种方法让多个对象共享相同的分配。如果多个对象认为它们都拥有相同的内存块，那么其中一个可能会在其他对象完成之前释放该内存，这肯定会导致段错误(当您访问已释放的内存时)。