11 сентября 2009 г.

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

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



Пример:

У нас есть массив 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.

Комментариев нет:

Отправить комментарий