Впорядкування даних і повернення їм попереднього порядку

Досить часто в спортивному програмуванні або ж просто реалізації алгоритмів необхідно відсортувати масив вхідних даних за певним критерієм. У той час як у відповіді потрібен вихідний порядок. У статті я розгляну декілька способів зробити це мінімальною кров'ю на C++. Якщо цікава ця тематика або є цікаві пропозиції, прошу під кат...

Автор зображення: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported

Перша ідея була відсортувати масив своїм алгоритмом, запам'ятати всі пари обмінів значень в масиві, кого з ким міняли місцями. І коли потрібно повернути вихідний порядок, повторити ці ж обміни в зворотному порядку. Звичайно ж свій алгоритм сортування, написаний за пару хвилин, навіть віддалено не наздоганяє std::sort(). Тому з'явилася друга ідея, запам'ятовувати початкові індекси записів і сортувати за ними за допомогою std::sort().

У наведених способах при заповненні масиву даними необхідно поле Domino::index заповнювати порядковим номером запису.

Перший спосіб, з використанням статичного члена і функтора:

Вихідник можна взяти тут: http://codepad.org/0PWSzTBc

Другий спосіб, за допомогою статичного члена і оператора <:

Вихідник можна взяти тут: http://codepad.org/1zsTnk4s

Третій спосіб, за допомогою лямбд (C++ 0x):

Вихідник можна взяти тут: http://codepad.org/5WRgCxLw

Перші два способи дуже схожі, за винятком оператора, який передається явним чином або використовується за замовчуванням функцією сортування. Третій спосіб просто показує наскільки простіше можна отримати той же результат, описуючи оператор прямо в місці його використання. На жаль, далеко не всі платформи для проведення змагань зі спортивного програмування підтримують C++ 0x.