Qsort 在 C++ 中不适用于哪些类型？
std::sort 使用 std::swap 交换元素，而 std::swap 又使用复制构造函数和赋值运算符，保证交换值时获得正确的语义。
qsort 通过简单地交换元素的底层位来交换元素，忽略与要交换的类型相关的任何语义。
尽管 qsort 不了解您正在排序的类型的语义，但它对于非平凡类型仍然非常有效。如果我没记错的话，它适用于所有标准容器，尽管它们不是 POD 类型。
我认为 qsort 在类型 T 上正常工作的先决条件是 T 是/可以轻松移动的/。在我的脑海中，唯一不可移动的类型是那些具有内部指针的类型。例如：
struct NotTriviallyMovable
{
NotTriviallyMovable() : m_someElement(&m_array[5]) {}
int m_array[10];
int* m_someElement;
};
如果您对 NotTriviallyMovable 数组进行排序，那么 m_someElement 最终将指向错误的元素。
我的问题是：还有哪些类型不能与 qsort 一起使用？
std::sort swaps elements by using std::swap, which in turn uses the copy constructor and assignment operators, guaranteeing that you get correct semantics when exchanging the values.
qsort swaps elements by simply swapping the elements' underlying bits, ignoring any semantics associated with the types you are swapping.
Even though qsort is ignorant of the semantics of the types you are sorting, it still works remarkably well with non-trivial types. If I'm not mistaken, it will work with all standard containers, despite them not being POD types.
I suppose that the prerequisite for qsort working correctly on a type T is that T is /trivially movable/. Off the top of my head, the only types that are not trivially movable are those that have inner pointers. For example:
struct NotTriviallyMovable
{
NotTriviallyMovable() : m_someElement(&m_array[5]) {}
int m_array[10];
int* m_someElement;
};
If you sorted an array of NotTriviallyMovable then the m_someElements would end up pointing to the wrong elements.
My question is: what other kinds of types do not work with qsort?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
任何不是 POD 类型的类型都不能与 qsort() 一起使用。如果您考虑 C++0x，则可能有更多类型可用于
qsort()，因为它更改了 POD。如果您打算在qsort()中使用非 POD 类型，那么您就进入了 UB 领域，守护进程将从您的鼻子中飞出。Any type that is not a POD type is not usable with
qsort(). There might be more types that are usable withqsort()if you consider C++0x, as it changes definition of POD. If you are going to use non-POD types withqsort()then you are in the land of UBs and daemons will fly out of your nose.这对于具有指向“相关”对象的指针的类型也不起作用。此类指针具有许多与“内部”指针相关的问题，但要准确证明“相关”对象是什么要困难得多。
一种特定类型的“相关”对象是具有反向指针的对象。如果对象 A 和 B 进行了位交换，并且 A 和 C 彼此指向，那么之后 B 将指向 C，但 C 将指向 A。
This doesn't work either for types that have pointers to "related" objects. Such pointers have many of the issues associated with "inner" pointers, but it's a lot harder to prove precisely what a "related" object is.
A specific kind of "related" objects are objects with backpointers. If object A and B are bit-swapped, and A and C pointed to each other, then afterwards B will point to C but C will point to A.
你完全错了。任何使用
qsort的非 POD 类型都是完整的并且非常幸运。仅仅因为它恰好在你的平台上为你工作，而你的编译器在蓝月亮上，如果你向诸神牺牲处女的鲜血并先跳一小段舞蹈，并不意味着它真的有效。哦，这是另一种针对非平凡可移动类型的类型，其实例是从外部观察到的。您移动它，但没有通知观察者，因为您从未调用交换或复制构造函数。
You are completely mistaken. Any non-POD type working with
qsortis complete and utter luck. Just because it happens to work for you on your platform with your compiler on a blue moon if you sacrifice the blood of a virgin to the Gods and do a little dance first doesn't mean that it actually works.Oh, and here's another one for not trivially movable- types whose instances are externally observed. You move it, but you don't notify the observer, because you never called the swap or copy construction functions.
“如果我没记错的话，它将适用于所有标准容器”
整个问题归结为，在什么实现中？您想要按照标准进行编码，还是想要按照您今天面前的编译器的实现细节进行编码？如果是后者，那么如果你所有的测试都通过了，我想它是有效的。
如果您询问的是 C++ 编程语言，则需要
qsort仅适用于 POD 类型。如果您询问具体的实现，是哪一个？如果您询问所有实现，那么您就错过了机会，因为进行此类民意调查的最佳场所是 C++0x 工作组会议，因为他们将几乎每个组织的代表聚集在一起，并以积极维护的 C++ 实现。就其价值而言，我可以很容易地想象一个 std::list 的实现，其中列表节点嵌入到列表对象本身中，并用作头/尾哨兵。我不知道什么实现（如果有）实际上是这样做的，因为使用空指针作为头/尾哨兵也很常见，但肯定有一些优点来实现每个节点都有一个虚拟节点的双向链表结尾。这样的 std::list 实例当然不能轻易移动，因为它的第一个和最后一个元素的节点将不再指向哨兵。它的
swap实现和（在 C++0x 中）它的移动构造函数将通过更新第一个和最后一个节点来解决这个问题。没有什么可以阻止你的编译器在下一个版本中切换到 std::list 的这种实现，尽管这会破坏二进制兼容性，因此考虑到大多数编译器的管理方式，它必须是一个主要版本。
类似地，map/set/multimap/multiset 四重奏可以具有指向其父级的节点。可以想象，任何容器的调试迭代器都可能包含指向该容器的指针。为了做你想做的事，你必须（至少）排除容器实现的任何部分中存在任何指向容器的指针，而像“没有实现使用任何这些技巧”这样的笼统声明是非常不明智的。制定标准的全部意义在于对所有符合要求的实现做出声明，因此，如果您没有从标准中推断出结论，那么即使您的声明今天正确，明天也可能变得不正确。
"If I'm not mistaken, it will work with all standard containers"
The whole question boils down to, in what implementation? Do you want to code to the standard, or do you want to code to implementation details of the compiler you have in front of you today? If the latter, then if all your tests pass I guess it works.
If you're asking about the C++ programming language, then
qsortis required to work only for POD types. If you're asking about a specific implementation, which one? If you're asking about all implementations, then you've sort of missed your chance, since the best place for that kind of straw poll was C++0x working group meetings, since they gathered together representatives of pretty much every organization with an actively-maintained C++ implementation.For what it's worth, I can pretty easily imagine an implementation of
std::listin which a list node is embedded in the list object itself, and used as a head/tail sentinel. I don't know what implementations (if any) actually do that, since it's also common to use a null pointer as a head/tail sentinel, but certainly there are some advantages to implementing a doubly-linked list with a dummy node at each end. An instance of such astd::listwould of course not be trivially movable, since the nodes for its first and last elements would no longer point to the sentinel. Itsswapimplementation and (in C++0x) its move constructor would account for this by updating those first and last nodes.There is nothing to stop your compiler switching to this implementation of
std::listin its next release, although that would break binary compatibility so given how most compilers are managed it would have to be a major release.Similarly, the map/set/multimap/multiset quartet could have nodes that point to their parents. Debugging iterators for any container might conceivably contain a pointer to the container. To do what you want, you'd have to (at least) rule out the existence of any pointer into the container in any part of its implementation, and a sweeping statement like "no implementation uses any of these tricks" is pretty unwise. The whole point of having a standard is to make statements about all conforming implementations, so if you haven't deduced your conclusion from the standard, then even if your statement is true today it could become untrue tomorrow.