6

std::sort通过 using 交换元素std::swap，后者又使用复制构造函数和赋值运算符，确保在交换值时获得正确的语义。

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

即使qsort不知道要排序的类型的语义，它仍然可以很好地处理非平凡的类型。如果我没记错的话，它适用于所有标准容器，尽管它们不是 POD 类型。

我认为qsort在一个类型上正确工作T的先决条件T是 /trivially 可移动 /。在我的脑海中，唯一不能轻易移动的类型是那些具有内部指针的类型。例如：

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

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

如果你对一个数组进行排序，NotTriviallyMovable那么m_someElements 最终会指向错误的元素。

我的问题是：还有哪些其他类型不适用qsort？

4

4 回答 4

5

任何不是 POD 类型的类型都不能用于qsort(). qsort()如果您考虑 C++0x，可能会有更多可用的类型，因为它会更改POD的定义。如果您要使用非 POD 类型，qsort()那么您将处于 UB 的领域，并且守护程序将从您的鼻子中飞出。

于 2011-05-30T10:19:21.833 回答
2

这对于具有指向“相关”对象的指针的类型也不起作用。这样的指针有许多与“内部”指针相关的问题，但是要准确地证明什么是“相关”对象要困难得多。

一种特定的“相关”对象是具有反向指针的对象。如果对象 A 和 B 进行了位交换，并且 A 和 C 相互指向，那么之后 B 将指向 C，而 C 将指向 A。

于 2011-05-30T11:11:19.507 回答
1

你完全错了。使用任何非 POD 类型qsort都是完全幸运的。如果您将处女的血献给众神并先跳一小段舞，那么它恰好在您的平台上与您的编译器一起在蓝月亮上为您工作并不意味着它确实有效。

哦，这是另一个用于非平凡可移动类型的，其实例是从外部观察的。你移动它，但你没有通知观察者，因为你从未调用过交换或复制构造函数。

于 2011-05-30T10:26:45.530 回答
1

“如果我没记错的话，它适用于所有标准容器”

整个问题归结为，在什么实施中？您是想按照标准编写代码，还是按照今天摆在您面前的编译器的实现细节编写代码？如果是后者，那么如果你所有的测试都通过了，我想它会起作用。

如果您询问的是 C++ 编程语言，则qsort必须仅适用于 POD 类型。如果您要询问具体的实现，是哪一个？如果你问的是所有的实现，那么你就错过了机会，因为这种投票表决的最佳地点是 C++0x 工作组会议，因为他们聚集了几乎每个组织的代表积极维护的 C++ 实现。

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

没有什么可以阻止你的编译器std::list在下一个版本中切换到这个实现，尽管这会破坏二进制兼容性，所以考虑到大多数编译器的管理方式，它必须是一个主要版本。

类似地，map/set/multimap/multiset 四重奏可以有指向其父节点的节点。任何容器的调试迭代器都可能包含指向容器的指针。为了做你想做的事，你必须（至少）在其实现的任何部分排除指向容器的任何指针的存在，并且像“没有实现使用任何这些技巧”这样的笼统声明是非常不明智的。拥有标准的全部意义在于对所有符合标准的实现做出陈述，因此，如果您还没有从标准中得出结论，那么即使您的陈述今天是正确的，明天也可能变得不正确。

于 2011-05-30T11:01:32.877 回答