在C++中，qsort不能用于哪些类型？

Question

std::sort使用std::swap交换元素，而std::swap使用复制构造函数和赋值运算符进行交换，确保在交换值时获得正确的语义。

qsort通过简单地交换元素的基础位来交换元素，并忽略与正在交换的类型相关联的任何语义。

尽管qsort对于您要排序的类型的语义一无所知，但它仍然能够非常好地处理非平凡类型。如果我没记错的话，它将适用于所有标准容器，尽管它们不是POD类型。

我认为qsort在类型T上正常工作的先决条件是T可以/trivially movable/。从我的经验来看，唯一不是trivially movable的类型是具有内部指针的类型。例如：

struct NotTriviallyMovable
{
    NotTriviallyMovable() : m_someElement(&m_array[5]) {}

    int m_array[10];
    int* m_someElement;
};

如果您对一个NotTriviallyMovable数组进行排序，那么m_someElement指针将指向错误的元素。

我的问题是：还有哪些类型无法与qsort一起使用？

- Peter Alexander

---

我觉得在这里使用move-semantics标签有点令人困惑，因为它通常与C++0x的移动语义相关联。 - Björn Pollex

基本上，在C++中使用qsort对于任何非POD类型都是未定义的行为。从那里开始，它将会破坏哪些特定情况以及如何破坏并不重要：无论如何都不应该使用它。 - David Rodríguez - dribeas

你为什么要首选使用qsort？在我检查的所有平台上，std::sort都更快（对于可平凡交换的对象类型），这是完全合理的，因为可以选择内联比较运算符。 - Christopher Creutzig

我上次测试std::sort时，它的速度大约快了两倍，因为它是原地排序（没有内存分配）。使用C++0x，对于大多数类型，我们甚至可以免费获得移动构造函数，因此当安全时，交换操作就像位拷贝一样好。那么你为什么还要费心去使用qsort呢？ - Matthieu M.

@Christopher @Matthieu：一个很好的理由是因为代码膨胀。上次我检查时，每个独特的使用方式会增加约5KB的代码。在不在热路径上的代码中，拥有更小的代码比拥有更快的代码更好。此外，即使在热路径上，使用qsort也可能更好，这样可以获得更好的I-cache使用率。 - Peter Alexander

Answer 1

任何不属于POD类型的类型都不能与qsort()一起使用。如果考虑C++0x，可能会有更多可用于qsort()的类型，因为它改变了POD的定义。如果您要使用非POD类型与qsort()一起使用，则会遇到未定义行为（UBs），并且恶魔将从您的鼻子中飞出。

- wilx

---

这不是真的。例如，std::vector 只是有一个指向外部数据的指针，在交换底层字节时将保持其所有不变量。诚然这有点‘hacky’，但如果我没有错的话，它就可以工作。 - Peter Alexander

@Peter：你完全错了。这样做不仅仅是“hacky”或使用特定实现的行为，而是明显未定义的。 - Puppy

@DeadMG：标准规定的未定义行为和编译器实际执行的行为之间存在很大差异。例如，极其流行的Fast Delegates库（http://www.codeproject.com/KB/cpp/FastDelegate.aspx）充斥着技术上未定义的行为，但仍然被使用（并且有效）。 - Peter Alexander

@Peter Alexander：区别在于这些实现不能随意更改行为。他依赖于实践中定义良好的实现方面，即使不是按字母顺序。另一方面，你只是祈祷，任何实现都可能改变自身的几乎任何方面，并可怕地破坏你正在做的事情并保持符合性。 - Puppy

即使是像 std::string 这样“简单”的类型，在具有小字符串优化等智能实现时也变得不再简单。这些实现可能会在 std::string 本身中具有指针。 - MSalters

@Peter Alexander：当我们谈论POD时，我们谈论的是所包含类型的POD属性，而不是容器本身的POD属性。您可以使用qsort对包含POD类型的std::vector元素进行排序。 - David Rodríguez - dribeas

Answer 2

对于具有指向"相关"对象的指针的类型，此方法也不起作用。这些指针具有许多与"内部"指针相关的问题，但是很难准确证明什么是"相关"对象。

一种特定类型的"相关"对象是带有反向指针的对象。如果将对象A和B进行位交换，并且A和C相互指向，则之后B将指向C，但C将指向A。

- MSalters

Answer 3

你完全错了。任何非 POD 类型与 qsort 一起使用都是完全靠运气。仅仅因为它在你的平台上、你的编译器上偶尔能工作，如果你献祭了处女的鲜血并先跳了个小舞，这并不意味着它真正有效。

哦，还有另一个对于那些实例被外部观察的不易移动类型的问题。你移动了它，但你没有通知观察者，因为你从未调用过交换或复制构造函数。

- Puppy

---

对于外部观察者而言，即使使用std::sort也无法解决这个问题（除非被排序的对象“知道”其外部观察者）。 - Peter Alexander

@Peter：在你的类型的复制/交换函数中，暗示着你会通知它们。 - Puppy

Answer 4

如果我没记错的话，它将与所有标准容器一起使用。

整个问题归结为，在哪种实现中？你想编写标准代码，还是想编写面前编译器的实现细节？如果是后者，那么如果所有测试都通过，我猜它就可以工作。

如果您正在询问C++编程语言，则qsort仅需要适用于POD类型。如果您正在询问特定的实现，那么是哪一个？如果您正在询问所有实现，那么您已经错过了机会，因为进行这种稻草投票的最佳场所是C++0x工作组会议，因为他们聚集了几乎每个具有积极维护的C++实现的代表。

就我所知，可以很容易地想象出一种实现方式，即在列表对象本身中嵌入列表节点，并将其用作头/尾哨兵。我不知道有哪些实现（如果有的话）实际上这样做，因为使用空指针作为头/尾哨兵也很常见，但肯定有一些优点是使用带有虚拟节点的双向链表。这样的std::list实例当然不会轻松移动，因为其第一个和最后一个元素的节点将不再指向哨兵。它的swap实现以及（在C++0x中）其移动构造函数将通过更新这些第一个和最后一个节点来解决这个问题。

没有什么能阻止你的编译器在下一个版本中切换到这种std::list的实现方式，尽管这将破坏二进制兼容性，因此考虑到大多数编译器的管理方式，这必须是一个重大的发布。

同样，map/set/multimap/multiset 四个容器也可能有指向其父节点的节点。任何容器的调试迭代器都可能包含指向容器的指针。要做到你想要的，你必须（至少）排除任何部分实现中存在指向容器的指针，并且像“没有任何实现使用这些技巧”这样的 sweeping statement 是相当不明智的。拥有标准的整个意义在于对所有符合规范的实现进行陈述，因此，如果您没有从标准中推断出结论，即使您的陈述今天是正确的，明天也可能变得不正确。

- Steve Jessop

---

记录一下，我有一个列表实现，它的工作方式与Steve的描述完全相同。链表的“链接”部分与数据分开，list_node和list_head（没有数据成员）都继承自链接部分。list_head嵌入到列表对象本身中，以节省动态分配。list_head的交换函数和移动构造函数调整第一个和最后一个列表元素的指针，使它们跟随list_head的移动。这在qsort中不起作用！ - Bo Persson

我实际上并不关心标准容器，我只是用它们作为非POD类型的例子，这些类型可能可以通过交换字节来交换。我的问题是询问哪些类型无法使用此方法，而不是是否适用于标准容器。 - Peter Alexander

你的问题是：“还有哪些类型无法使用？”。我的回答是：“除其他事项外，标准容器也无法使用”。 - Steve Jessop