Язык программирования C++ от Страуструпа

       

Индексация


Операторная функция operator[] задает для объектов классов интерпретацию индексации. Второй параметр этой функций (индекс) может иметь произвольный тип. Это позволяет, например, определять ассоциативные массивы. В качестве примера можно переписать определение из $$2.3.10, где ассоциативный массив использовался в небольшой программе, подсчитывающей число вхождений слов в файле. Там для этого использовалась функция. Мы определим настоящий тип ассоциативного массива:

class assoc {

  struct pair {

     char* name;

     int val;

  };

  pair* vec;

  int max;

  int free;

  assoc(const assoc&);             // предотвращает копирование

  assoc& operator=(const assoc&);  // предотвращает копирование

  public:

     assoc(int);



     int& operator[](const char*);

     void print_all();

};

В объекте assoc хранится вектор из структур pair размером max. В переменной free хранится индекс первого свободного элемента вектора.

Чтобы предотвратить копирование объектов assoc, конструктор копирования и операция присваивания описаны как частные. Конструктор выглядит так:

assoc::assoc(int s)

{

  max = (s<16) ? 16 : s;

  free = 0;

  vec = new pair[max];

}

В реализации используется все тот же неэффективный алгоритм поиска,

что и в $$2.3.10. Но теперь, если вектор переполняется, объект assoc увеличивается:

#include <string.h>

int& assoc::operator[](const char* p)

/*

  работает с множеством пар (структур pair):

  проводит поиск p, возвращает ссылку на целое значение из найденной пары,

  создает новую пару, если p не найдено

*/

{

  register pair* pp;

  for (pp=&vec[free-1]; vec<=pp; pp-- )

     if (strcmp(p,pp->name) == 0) return pp->val;

  if (free == max) {               //переполнение: вектор увеличивается

     pair* nvec = new pair[max*2];

     for (int i=0; i<max; i++) nvec[i] = vec[i];

       delete vec;

     vec = nvec;

     max = 2*max;

  }

  pp = &vec[free++];

  pp->name = new char[strlen(p)+1];


  strcpy(pp->name,p);

  pp->val = 0;                     // начальное значение = 0

  return pp->val;

}

Поскольку представление объекта assoc скрыто от пользователя, нужно иметь возможность напечатать его каким-то образом. В следующем разделе будет показано как определить настоящий итератор для такого объекта. Здесь же мы ограничимся простой функцией печати:

void assoc::print_all()

{

  for (int i = 0; i<free; i++)

     cout << vec[i].name << ": " << vec[i].val << '\n';

}

Наконец, можно написать тривиальную программу:

main()    // подсчет числа вхождений во входной

          // поток каждого слова

{

  const MAX = 256;  // больше длины самого длинного слова

  char buf[MAX];

  assoc vec(512);

  while (cin>>buf) vec[buf]++;

  vec.print_all();

}

Опытные программисты могут заметить, что второй комментарий можно легко опровергнуть. Решить возникающую здесь проблему предлагается в упражнении $$7.14 [20]. Дальнейшее развитие понятие ассоциативного массива получит в $$8.8.

Функция operator[]() должна быть членом класса. Отсюда следует, что эквивалентность x[y] == y[x] может не выполняться, если x объект класса. Обычные отношения эквивалентности, справедливые для операций со встроенными типами, могут не выполняться для пользовательских типов ($$7.2.2, см. также $$7.9).


Содержание раздела