Здравствуйте, Тролль зеленый и толстый, Вы писали:

C>>Поскольку qsort — функция стандартной библиотеки C и не имеет информации о типе элементов сортируемого массива (а только о размере), следует предположить, что она обменивает элементы через memcpy или memmove. Следовательно, её нельзя применять к не-POD-типам. Структура Entry содержит член типа std::string, не являющийся POD-типом.

ТЗИ>Кстати, распространенное заблуждение. POD здесь не при чем. Здесь важно лишь можно ли объект перемещать в памяти или нет. Существуют не POD-типы, которые можно перемещать, и POD-типы, которые нельзя перемещать (например, если в структуре имеется указатель, указывающий на одно из полей этой же структуры). Можно ли перемещать std::string, зависит от его реализации, вполне может быть, что можно.

В действующем стандарте 2003 (выделены изменения между 2003 и 0x):

3.9 Types [basic.types]

2: For any object (other than a base-class subobject) of POD type T, whether or not the object holds a valid value of type T, the underlying bytes (1.7) making up the object can be copied into an array of char or unsigned char.[36] If the content of the array of char or unsigned char is copied back into the object, the object shall subsequently hold its original value. [example/]

3: For any POD type T, if two pointers to T point to distinct T objects obj1 and obj2, where neither obj1 nor obj2 is a base-class subobject, if the value of obj1 is copied into obj2, using the memcpy library function, obj2 shall subsequently hold the same value as obj1. [example/]

В стандартопроекте C++0x, n3035:

3.9 Types [basic.types]

2: For any object (other than a base-class subobject) of trivially copyable type T, whether or not the object holds a valid value of type T, the underlying bytes (1.7) making up the object can be copied into an array of char or unsigned char.[39] If the content of the array of char or unsigned char is copied back into the object, the object shall subsequently hold its original value. [example/]

3: For any trivially copyable type T, if two pointers to T point to distinct T objects obj1 and obj2, where neither obj1 nor obj2 is a base-class subobject, if the underlying bytes (1.7) making up obj1 are copied into obj2,[40] obj2 shall subsequently hold the same value as obj1. [example/]

40) By using, for example, the library functions (17.6.1.2) std::memcpy or std::memmove.

Далее:

3.9/9: Scalar types, trivially copyable class types (Clause 9), arrays of such types, and cv-qualified versions of these types (3.9.3) are collectively called trivially copyable types.

9/5: A trivially copyable class is a class that:

• has no non-trivial copy constructors (12.8),
  
• has no non-trivial copy assignment operators (13.5.3, 12.8), and
  
• has a trivial destructor (12.4).

12.8/6: A copy constructor for class X is trivial if it is not user-provided (8.4) and if

• class X has no virtual functions (10.3) and no virtual base classes (10.1), and
  
• the constructor selected to copy each direct base class subobject is trivial, and
  
• for each non-static data member of X that is of class type (or array thereof), the constructor selected to copy that member is trivial;

otherwise the copy constructor is non-trivial.

12.8/13 A copy assignment operator for class X is trivial if it is not user-provided and if

• class X has no virtual functions (10.3) and no virtual base classes (10.1), and
  
• the assignment operator selected to copy each direct base class subobject is trivial, and
  
• for each non-static data member of X that is of class type (or array thereof), the assignment operator selected to copy that member is trivial;
  otherwise the copy assignment operator is non-trivial.

12.4/3: […] A destructor is trivial if it is not user-provided and if:

• the destructor is not virtual,
  
• all of the direct base classes of its class have trivial destructors, and
  
• for all of the non-static data members of its class that are of class type (or array thereof), each such class has a trivial destructor.

An implicitly-declared destructor for a class X is defined as deleted if:

• X is a union-like class that has a variant member with a non-trivial destructor,
  
• any of the non-static data members has class type M (or array thereof) and M has an deleted destructor or a destructor that is inaccessible from the implicitly-declared destructor, or
  
• any direct or virtual base class has a deleted destructor or a destructor that is inaccessible from the implicitly-declared destructor.

Otherwise, the destructor is non-trivial.

Далее, 21.4 перечисляет copy constructor, copy assignment operator и destructor. Все они, насколько я могу интерпретировать, относятся к user-provided и, следовательно, non-trivial. Таким образом, std::string (и любой класс, включающий std::string в качестве базы или члена) не является trivially copyable, следовательно, стандарт не гарантирует, что сортировка массива таких объектов через qsort будет корректна.

Кроме того, стандартопроект C++0x в 25.5/4 гласит:

25.5/4: The function signature:

qsort(void *, size_t, size_t, int (*)(const void *, const void *));

is replaced by the two declarations:

extern "C" void qsort(void* base, size_t nmemb, size_t size,
                      int (*compar)(const void*, const void*));
extern "C++" void qsort(void* base, size_t nmemb, size_t size,
                        int (*compar)(const void*, const void*));

both of which have the same behavior as the original declaration. The behavior is undefined unless the objects in the array pointed to by base are of trivial type.

— то есть налагается ограничение даже более сильное, чем trivially copyable type:

3.9/9: […] Scalar types, trivial class types (Clause 9), arrays of such types and cv-qualified versions of these types (3.9.3) are collectively called trivial types.

9/5: A trivial class is a class that has a trivial default constructor (12.1) and is trivially copyable.