Выполнение перестановки на месте с помощью std :: move

Question

Я написал алгоритм перестановки на месте [упражнение в TAOCP3], где внутренний цикл равен

template<typename T>
void inplace_permute(T *pT, int *P, const int n)
{
  // part of the inner loop
  pT[j] = std::move(pT[k]);
  P[j] = j;

  // more logic to update j, k, etc.
}

Здесь pT - массив элементов для сортировки, P - таблица перестановок, а n - количество элементов.

Увеличит ли std::move производительность, если T - сложный тип, например, строка? Также важно, можно ли оптимизировать его, если T является примитивным типом (например, int?)

Answer 1

Я подведу ваш вопрос как:

Что делает std::move?

По сути, std::move делает возможным использование Конструктора перемещения и Оператора назначения перемещения.

Как правило, они близки к побитовой копии (они , а не ровно один), поэтому производительность обычно связана с sizeof классом.

Следовательно, std::move(someint) и std::move(somestring) будут иметь одинаковую производительность, если они будут иметь одинаковый размер, даже если один является встроенным, а другой - классом пользователя.

Хотя есть некоторые различия.

• на встроенном шаге - просто побитовая копия. Поскольку значение перемещения не указано, обнуление не требуется. Возможно, вы захотите после перемещения присвоить ему известное значение (0 или что-то еще)
• для пользовательского класса, который обычно имеет ресурсов (такой динамически распределенный буфер), перемещение подразумевает: очистка экземпляра перемещенного объекта (для назначения), создание несколько побитовой копии, сброс перемещенного объекта от экземпляра. Так что работы немного больше.

Чтобы понять, мы можем проиллюстрировать это на примере реализации строки:

class String {
public:
  // Many things
  String(String&& right);
  String& operator=(String right);

  friend void swap(String& left, String& right);

private:
  // On 64 bits platform, 4x as big as an `int`
  size_t capacity;
  size_t size;
  char* buffer;
};

// Move Constructor
String::String(String&& right):
   capacity(right.capacity), size(right.size), buffer(right.buffer)
{
  right = String(); // reset right
}


// Assignment Operator
String& String::operator=(String right) {
  swap(*this, right);
  return *this;
}

// Swap
void swap(String& left, String& right) {
  using std::swap;
  swap(left.capacity, right.capacity);
  swap(left.size    , right.size);
  swap(left.buffer  , right.buffer);
}

Как видите, присвоение pT[j] = std::move(pT[k]); означает (семантически):

• создание временного (сделать побитовую копию pT[k])
• сброс pT[k]
• обмен состояния между временным и pT[j]
• уничтожить временное хранилище (которое обычно освобождает хранилище, унаследованное от pT[j])

Компилятор должен, более или менее, иметь возможность оптимизировать его в:

• обмен состояния между pT[j] и pT[k]
• уничтожить pT[k] (просто освободить хранилище)
• перестроить новый экземпляр в pT[k]

Или, грубо:

swap(ptj, ptk);    // swap 3 fields
delete ptk.buffer; // might be a no-op
ptk = String();    // 0-out 3 fields

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

Answer 2

Если T имеет оператор присваивания перемещения, который будет использоваться для значений r и, возможно, для повышения производительности.

Если тип не имеет назначения перемещения, но имеет назначение копирования (например, int), вместо этого будет скопировано значение.