Блог

std::sort элементы меняются местами с помощью std::swap , которая, в свою очередь, использует конструктор копирования и операторы присваивания, гарантируя, что вы получите правильную семантику при обмене значениями.

qsort элементы меняются местами, просто меняя местами базовые биты элементов, игнорируя любую семантику, связанную с типами, которые вы меняете местами.

Даже при том, что qsort не осведомлен о семантике сортируемых вами типов, он все равно замечательно работает с нетривиальными типами. Если я не ошибаюсь, это будет работать со всеми стандартными контейнерами, несмотря на то, что они не являются типами POD.

Я полагаю, что предпосылкой для qsort корректной работы с типом T является то, T что он / тривиально подвижен/. На мой взгляд, единственные типы, которые не являются тривиально перемещаемыми, — это те, у которых есть внутренние указатели. Например:

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

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

Если бы вы отсортировали массив из, NotTriviallyMovable тогда m_someElement s в конечном итоге указывали бы на неправильные элементы.

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

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

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

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

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

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

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

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

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

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

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

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