Использует ли сортировка STL своп или бинарную копию? - PullRequest
Новая
       47

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

10 голосов
/ 22 ноября 2011

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

Дополнительный вопрос : Какие-нибудь алгоритмы STL или контейнерные операции реализованы с использованием подкачки?(Очевидно, за пределами 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.Следовательно, мой вопрос - сортировка, вызывающая обмен, копирование и т. Д.?

Ответы [ 4 ]

6 голосов
/ 22 ноября 2011

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

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);}
};

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

3 голосов
/ 22 ноября 2011

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

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

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

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

3 голосов
/ 22 ноября 2011

Я видел раньше, что std::copy использует memmove в GNU libstdc ++, в зависимости от того, является ли тип элемента 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

Кроме того, стандартный документ c ++ 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).
2 голосов
/ 22 ноября 2011

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

...