0

我已经编写了我自己的双向链表，包括 begin() 和 end() 迭代器。这些可以很好地使用循环遍历列表。但是，作为我的任务的一部分，我需要根据某些标准对列表进行排序。由于我们还没有介绍排序算法的章节，我们可以使用标题中定义的排序函数。但是 sort(list.begin(), list.end(), compare) 返回很多与我的迭代器类相关的错误：

error: no type named iterator_category
error: no type named value_type
error: no type named difference_type
error: no type named pointer
error: no type named reference

此外，我收到有关 + 和 - 运算符的错误。我了解如何定义 value_type、指针和引用，但是当涉及到其他人时我迷失了。我正在尝试做的事情可能吗？谢谢！

4

1 回答 1

1

这是可能的，但可能会有些痛苦，因为您最终会编写大量的样板代码。

更糟糕的是，当你完成后，它不会很好地工作 -std::sort并不绝对需要随机访问迭代器，但是使用（比如说）双向迭代器，性能通常会相当差。举个例子，它（与大多数标准容器不同）std::list有一个sort成员函数来弥补std::sort在链表上效果不佳的事实已经很糟糕了。

基本上，operator+只需operator-向前或向后推进一个指针 N 项。通常，您会超载operator++以推进一个，例如pos = pos -> next;（并operator--使用类似的东西pos = pos->prev;。然后您可以一次使用std::advance或std::next推进多个项目（但请注意：对于双向迭代器，它将通过调用++或--重复来做到这一点- - 性能不佳的原因之一）。

于 2013-10-08T22:11:15.473 回答