Сортировка указателей

При необходимости сортировки массивов структур данных иногда полезно сортировать не сами данные, а массив указателей на эти структуры. Например, это может пригодиться, когда нам нужно отсортировать массив и записать его на диск, но указатель на массив — константный. А при работе с большими массивами мы можем получить выигрыш в производительности за счет того, что в памяти будут передвигаться не структуры, а указатели (понятно, что это имеет смысл, когда размер структуры больше размера указателя).



Пример:

У нас есть массив arr, состоящий из структур Rec. Нужно получить отсортированную последовательность данных, не изменяя исходный массив.

Мы создаем новый массив ptrarr с указателями на исходные структуры и используем std::sort для его сортировки. Для того, чтобы указатели были отсортированы в порядке возрастания данных, нам нужно определить функцию сравнения указателей (lessFunc) и передать ее в std::sort.

1. #include <algorithm>
2. #include <iostream>
3.  
4. using namespace std;
5.  
6. //////////////////////////////////////////////////////
7.  
8. struct Rec
9. {
10.  Rec () : _a(0), _b(0)
11.  {
12.  }
13.  
14.  Rec (int a, int b) : _a(a), _b(b)
15.  {
16.  }
17.  
18.  Rec (const Rec &r)
19.  {
20.   _a = r._a;
21.   _b = r._b;
22.  }
23.  
24.  bool operator< (const Rec &r)
25.  {
26.   if (_a < r._a)
27.   {
28.    return true;
29.   }
30.   else if (_a == r._a && _b < r._b)
31.   {
32.    return true;
33.   }
34.  
35.   return false;
36.  }
37.  
38.  int _a;
39.  int _b;
40. };
41.  
42. typedef Rec * RecPtr;
43.  
44. //////////////////////////////////////////////////////
45.  
46. void printRec (const RecPtr &r)
47. {
48.  cout << (*r)._a << " - " << (*r)._b << endl;
49. }
50.  
51. //////////////////////////////////////////////////////
52.  
53. bool lessFunc (const RecPtr &l, const RecPtr &r)
54. {
55.  return ((*l) < (*r));
56. }
57.  
58. //////////////////////////////////////////////////////
59.  
60. int main (int, char **)
61. {
62.  // Array size
63.  const size_t len = 5;
64.  
65.  // Data array
66.  Rec *arr = new Rec[len];
67.  
68.  arr[0] = Rec(5, 5);
69.  arr[1] = Rec(1, 1);
70.  arr[2] = Rec(3, 0);
71.  arr[3] = Rec(1, 2);
72.  arr[4] = Rec(5, 1);
73.  
74.  // Pointer array
75.  RecPtr *ptrarr = new RecPtr[len];
76.  
77.  for (size_t i = 0; i < len; ++i)
78.  {
79.   ptrarr[i] = arr + i;
80.  }
81.  
82.  cout << "--- before" << endl;
83.  for_each(ptrarr, ptrarr + len, printRec);
84.  
85.  sort(ptrarr, ptrarr + len, lessFunc);
86.  
87.  cout << "--- after" << endl;
88.  for_each(ptrarr, ptrarr + len, printRec);
89.  
90.  delete [] ptrarr;
91.  delete [] arr;
92.  
93.  return 0;
94. }
95.  
96. //////////////////////////////////////////////////////

* This source code was highlighted with Source Code Highlighter.