Использует ли сортировка STL своп или двоичную копию?

У меня возникли проблемы с поиском хорошего ответа на этот вопрос. По какой-то причине я думал, что сортировка STL будет реализована с использованием swap для лучшей поддержки сложных типов, но, поскольку я в конечном итоге копал код, кажется, что он фактически выполняет двоичную копию. Может кто-то подтвердить это? Я предполагаю, что бинарная копия будет предпочтительнее поменять местами.

Боковой вопрос: реализованы ли какие-либо из алгоритмов STL или контейнерных операций с помощью swap? (Вне std::swap очевидно.) Я хочу знать, когда разумно реализовать свою собственную своп для сложных типов.

Изменить: Причина, о которой я спрашиваю, это если у вас есть что-то вроде:

class MyClass {
  vector<int> vec_data;
  int a;
  int b;
}
vector<MyClass> my_vec;
sort(my_vec.begin(), my_vec.end(), MyCustomCompare);

Я хочу убедиться, что сортировка не вызывает конструктор копирования вектора, что произойдет, если вы вызываете конструктор копирования по умолчанию MyData. Поэтому мой вопрос - это сортировка вызовов, копирование и т.д.

Ответы

Ответ 1

Это зависит от вашей реализации STL. GCC STL-реализация использует комбинацию типа introsort и insertion. Похоже, что std::swap (или ваша специализация) будет вызываться в цикле introsort, но он не будет вызван сортировкой вставки.

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

Он не использует двоичную копию (за исключением некоторых типов POD, которые могут иметь специализации, скрытые в глубинах библиотек STL).

Кроме того, в С++ 0x кажется вероятным, что сортировка вставки будет использовать семантику перемещения (ссылки rvalue).

Ответ 2

Нет, std::sort из стандартной библиотеки С++ не разрешено выполнять двоичную копию объектов с нетривиальными операциями копирования/присваивания. Я не понимаю, почему он не может делать двоичные копии на объектах с тривиальными операциями копирования/присваивания. Рассмотрим этот объект:

class Explosive {
    Explosive* const self;
public:
    Explosive() :self(this) {}
    Explosive(const Explosive&) :self(this) {}
    ~Explosive() {assert(this==self);}
    Explosive& operator=(const Explosive& rhs) {
        assert(this==self && rhs.self==&rhs); 
        return *this;
    }
    bool operator<(const Explosive& rhs) const 
    {return std::less<Explosive*>(self,rhs.self);}
};

Алгоритмы С++ гарантируют, что не будут заданы либо assert, что означает, что двоичная копия не будет действительна.

Ответ 3

Я видел, прежде чем std::copy использует memmove в GNU libstdС++, в зависимости от того, является ли тип элемента POD has_trivial_assignment_operator. Смотрите источник здесь:

template<typename _Tp>
   inline _Tp*
   __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
   {
      std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
      return __result + (__last - __first);
   }

По крайней мере, в SGI, rotate, reverse, swap_ranges, random_shuffle, partition, next_permutation все используют swap.

См. http://www.sgi.com/tech/stl/stl_algo.h

Кроме того, стандартный документ С++ 11 для std::sort конкретно упоминается в § 25.4.1.1:

Требуется: RandomAccessIterator должно удовлетворять требованиям ValueSwappable (17.6.3.2). Тип *first должен удовлетворять требованиям MoveConstructible (таблица 20) и MoveAssignable(Таблица 22).

Теперь в § 17.6.3.2 содержится следующее:

Объект t заменяется с объектом u тогда и только тогда, когда:

  • выражения swap(t, u) и swap(u, t) действительны при оценке в контексте, описанном ниже, и
  • эти выражения имеют следующие эффекты:
    • объект, на который ссылается t, имеет значение, первоначально сохраненное u и
    • объект, на который ссылается u, имеет значение, первоначально сохраненное символом t.

Контекст, в котором оцениваются swap(t, u) и swap(u, t), должен гарантировать, что двоичная функция нечлена с именем "swap" выбирается с помощью разрешения перегрузки (13.3) в наборе кандидатов, который включает в себя:

  • два шаблона функции свопинга, определенные в (20.2) и
  • набор поиска, созданный зависимым от аргумента поиска (3.4.2).

Ответ 4

Он меняет местами, но поскольку он является функцией шаблона, он может встроить код подкачки. Компилятор может выбрать двоичный обмен в качестве оптимизации, если это простой тип.