Для каких типов qsort не работает в C ++?

Question

std::sort меняет элементы, используя 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 s в конечном итоге будет указывать на неправильные элементы.

Мой вопрос: с какими другими типами не работают qsort?

Answer 1

Любой тип, который не является типом POD, не может использоваться с qsort().Может быть больше типов, которые можно использовать с qsort(), если рассматривать C ++ 0x, так как это меняет определение POD .Если вы собираетесь использовать не-POD типы с qsort(), то вы находитесь на земле UB, и демоны вылетят из вашего носа.

Answer 2

Это также не работает для типов, которые имеют указатели на «связанные» объекты.Такие указатели имеют много проблем, связанных с «внутренними» указателями, но гораздо сложнее точно доказать, что такое «связанный» объект.

Конкретный вид «связанных» объектов - это объекты с обратными указателями.Если объекты A и B меняются битами, а A и C указывают друг на друга, то впоследствии B будет указывать на C, а C будет указывать на A.

Answer 3

«Если я не ошибаюсь, он будет работать со всеми стандартными контейнерами»

Весь вопрос сводится к тому, в какой реализации? Вы хотите написать код в соответствии со стандартом или кодировать детали реализации компилятора, который у вас есть сегодня? Если последнее, то, если все ваши тесты пройдены, я думаю, что это работает.

Если вы спрашиваете о языке программирования C ++, то qsort требуется для работы только с типами POD. Если вы спрашиваете о конкретной реализации, какой? Если вы спрашиваете обо всех реализациях, то вы упустили свой шанс, поскольку лучшим местом для такого рода опросов были встречи рабочей группы C ++ 0x, так как они собрали представителей практически каждой организации с активно поддерживаемая реализация C ++.

Что бы это ни стоило, я могу довольно легко представить реализацию std::list, в которой узел списка встроен в сам объект списка и используется в качестве сторожа головы / хвоста. Я не знаю, какие реализации (если таковые имеются) на самом деле это делают, поскольку также часто используется нулевой указатель в качестве начального / хвостового стража, но, безусловно, есть некоторые преимущества для реализации двусвязного списка с фиктивным узлом на каждом конец. Экземпляр такого std::list, конечно, не будет тривиально подвижным, поскольку узлы для его первого и последнего элементов больше не будут указывать на страж. Его реализация swap и (в C ++ 0x) его конструктор перемещения будут учитывать это, обновляя эти первый и последний узлы.

Ничто не мешает вашему компилятору переключиться на эту реализацию std::list в следующем выпуске, хотя это нарушит бинарную совместимость, поэтому, учитывая то, как управляется большинство компиляторов, это должен быть основной выпуск.

Аналогично, квартет map / set / multimap / multiset может иметь узлы, которые указывают на их родителей. Итераторы отладки для любого контейнера могут содержать указатель на контейнер. Чтобы сделать то, что вы хотите, вы должны (по крайней мере) исключить существование какого-либо указателя на контейнер в любой части его реализации, и такой быстрый вывод, как «ни одна реализация не использует ни одного из этих приемов», является довольно неразумным. Весь смысл наличия стандарта состоит в том, чтобы делать заявления обо всех соответствующих реализациях, поэтому, если вы не сделали вывод из стандарта, то даже если ваше утверждение верно сегодня, оно может стать неверным завтра.

Answer 4

Вы полностью ошибаетесь.Любой не POD-тип, работающий с qsort, полон удачи.То, что это работает для вас на вашей платформе с вашим компилятором на голубой луне, если вы жертвуете кровью девственницы Богам и сначала делаете маленький танец, не означает, что это действительно работает.

О, и вот еще один для нетривиально подвижных типов, случаи которых наблюдаются извне.Вы перемещаете его, но не уведомляете наблюдателя, потому что вы никогда не вызывали функции подкачки или копирования.