Программирование — страница 36 из 57

“Покупатель, будь бдителен!”

Полезный совет

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

18.1. Введение

Для того чтобы подняться в воздух, самолет должен разогнаться до скорости взлета. Пока самолет грохочет по взлетной полосе, он представляет собой не более чем тяжелый и неуклюжий грузовик. Однако, поднявшись в воздух, самолет становится необыкновенным, элегантным и эффективным транспортным средством. Это объясняется тем, что в воздухе самолет находится в своей стихии.

 В этой главе мы находимся на середине взлетной полосы. Ее цель — с помощью языковых инструментов и технологий программирования избавиться от ограничений и сложностей, связанных с использованием памяти компьютера. Мы стремимся достичь той стадии программирования, на которой типы обладают именно теми свойствами, которые соответствуют логическим потребностям. Для этого мы должны преодолеть фундаментальные ограничения, связанные с аппаратным обеспечением.

• Объект в памяти имеет фиксированный размер.

• Объект в памяти занимает конкретное место.

• Компьютер предоставляет только самые необходимые операции над объектами (например, копирование слова, сложение двух слов и т.д.).

По существу, эти ограничения относятся к встроенным типам и операциям языка С++ (и унаследованы от языка С; см. раздел 22.2.5 и главу 27). В главе 17 мы уже ознакомились с типом vector, управляющим доступом ко всем своим элементам и обеспечивающим операции, которые выглядят натурально с точки зрения пользователя, но не с точки зрения аппаратного обеспечения.

В этой главе мы сосредоточим свое внимание на копировании. Это важное, но скорее техническое понятие. Что мы имеем в виду, копируя нетривиальный объект? До какой степени копии являются независимыми после выполнения операции копирования? Какие виды копирования существуют? Как их указать? Как они связаны с другими фундаментальными операциями, например с инициализацией и очисткой?

Мы обязательно обсудим проблему манипуляции памятью без помощи высокоуровневых типов, таких как vector и string, изучим массивы и указатели, их взаимосвязь и способы применения, а также ловушки, связанные с их использованием. Это важная информация для любого программиста, вынужденного работать с низкоуровневыми кодами, написанными на языке C++ или C.

Отметим, что детали класса vector характерны не только для векторов, но и для других высокоуровневых типов, которые создаются из низкоуровневых. Однако каждый высокоуровневый тип (string, vector, list, map и др.) в любом языке создается из одинаковых машинных примитивов и отражает разнообразие решений фундаментальных проблем, описанных в этой главе.

18.2. Копирование

Рассмотрим класс vector в том виде, в каком он был представлен в конце главы 17.

class vector {
  int sz; // размер
  double* elem; // указатель на элементы
public:
  vector(int s) // конструктор
  :sz(s), elem(new double[s]) { /* */ } // выделяет
                                        // память
  ~vector()           // деструктор
  { delete[ ] elem; } // освобождает
  // память
  // ...
};

Попробуем скопировать один из таких векторов.

void f(int n)
{
  vector v(3);   // определяем вектор из трех элементов
  v.set(2,2.2);  // устанавливаем v[2] равным 2.2
  vector v2 = v; // что здесь происходит?
 // ...
}

Теоретически объект v2 должен стать копией объекта v (т.е. оператор = создает копии); иначе говоря, для всех i в диапазоне [0:v.size()] должны выполняться условия v2.size()==v.size() и v2[i]==v[i]. Более того, при выходе из функции f() вся память возвращается в свободный пул. Именно это (разумеется) делает класс vector из стандартной библиотеки, но не наш слишком простой класс vector. Наша цель — улучшить наш класс vector, чтобы правильно решать такие задачи, но сначала попытаемся понять, как на самом деле работает наша текущая версия. Что именно она делает неправильно, как и почему? Поняв это, мы сможем устранить проблему. Еще более важно то, что мы можем распознать аналогичные проблемы, которые могут возникнуть в других ситуациях.

По умолчанию копирование относительно класса означает “скопировать все данные-члены”. Это часто имеет смысл. Например, мы копируем объект класса Point, копируя его координаты. Однако при копировании членов класса, являющихся указателями, возникают проблемы. В частности, для векторов в нашем примере выполняются условия v.sz==v2.sz и v.elem==v2.elem, так что наши векторы выглядят следующим образом:

Иначе говоря, объект v2 не содержит копии элементов объекта v; он ими владеет совместно с объектом v. Мы могли бы написать следующий код:

v.set(1,99);  // устанавливаем v[1] равным 99
v2.set(0,88); // устанавливаем v2[0] равным 88
cout << v.get(0) << ' ' << v2.get(1);

В результате мы получили бы вектор

88

99. Это не то, к чему мы стремились. Если бы не существовало скрытой связи между объектами v и v2, то результат был бы равен 00, поскольку мы не записывали никаких значений в ячейку v[0] или v2[1]. Вы могли бы возразить, что такое поведение является интересным, аккуратным или иногда полезным, но мы не этого ждали, и это не то, что реализовано в стандартном классе vector. Кроме того, когда мы вернем результат из функции f(), произойдет явная катастрофа. При этом неявно будут вызваны деструкторы объектов v и v2; деструктор объекта v освободит использованную память с помощью инструкции

delete[] elem;

И то же самое сделает деструктор объекта v2. Поскольку в обоих объектах, v и v2, указатель elem ссылается на одну ту же ячейку памяти, эта память будет освобождена дважды, что может привести к катастрофическим результатам (см. раздел 17.4.6). 

18.2.1. Конструкторы копирования

Итак, что делать? Это очевидно: необходимо предусмотреть операцию копирования, которая копировала бы элементы и вызывалась при инициализации одного вектора другим. Следовательно, нам нужен конструктор, создающий копии. Такой конструктор, очевидно, называется копирующим (copy constructor). В качестве аргумента он принимает ссылку на объект, который подлежит копированию. Значит, класс vector должен выглядеть следующим образом:

vector(const vector&);

Этот конструктор будет вызываться, когда мы попытаемся инициализировать один объект класса vector другим. Мы передаем объект по ссылке, поскольку не хотим (очевидно) копировать аргумент конструктора, который определяет суть копирования. Мы передаем эту ссылку со спецификатором const, потому что не хотим модифицировать аргумент (см. раздел 8.5.6). Уточним определение класса vector.

class vector {
  int sz;
  double* elem;
  void copy(const vector& arg); // копирует элементы copy
                                // из arg в *elem
public:
  vector(const vector&);        // конструктор копирования
  // ...
};

Функция-член copy() просто копирует элементы из вектора, являющегося аргументом.

void vector::copy(const vector& arg)
 // копирует элементы [0:arg.sz–1]
{
  for (int i = 0; i
}

Подразумевается, что функции-члену copy() доступны sz элементов как в аргументе arg, так и в векторе, в который он копируется. Для того чтобы обеспечить это, мы сделали функцию-член copy() закрытой. Ее могут вызывать только функции, являющиеся частью реализации класса vector. Эти функции должны обеспечить совпадение размеров векторов.

Конструктор копирования устанавливает количество элементов (sz) и выделяет память для элементов (инициализируя указатель elem) перед копированием значений элементов из аргумента vector.

vector::vector(const vector& arg)
// размещает элементы, а затем инициализирует их путем копирования
       :sz(arg.sz), elem(new double[arg.sz])
{
  copy(arg);
}

Имея конструктор копирования, мы можем вернуться к рассмотренному выше примеру.

vector v2 = v;

Это определение инициализирует объект v2, вызывая конструктор копирования класса vector с аргументом v. Если бы объект класса vector содержал три элемента, то возникла бы следующая ситуация:

Теперь деструктор может работать правильно. Каждый набор элементов будет корректно удален. Очевидно, что два объекта класса vector теперь не зависят друг от друга, и мы можем изменять значения элементов в объекте v, не влияя на содержание объекта v2, и наоборот. Рассмотрим пример.

v.set(1,99);  // устанавливаем v[1] равным 99
v2.set(0,88); // устанавливаем v2[0] равным 88
cout << v.get(0) << ' ' << v2.get(1);

Результат равен

0

0.

Вместо инструкции

vector v2 = v;

мы могли бы написать инструкцию

vector v2(v);

Если объекты v (инициализатор) и v2 (инициализируемая переменная) имеют одинаковый тип и в этом типе правильно реализовано копирование, то приведенные выше инструкции эквивалентны, а их выбор зависит от ваших личных предпочтений. 

18.2.2. Копирующее присваивание

 Копирование векторов может возникать не только при их инициализации, но и при присваивании. Как и при инициализации, по умолчанию копирование производится поэлементно, так что вновь может возникнуть двойное удаление (см. раздел 18.2.1) и утечка памяти. Рассмотрим пример.

void f2(int n)
{
  vector v(3); // определяем вектор
  v.set(2,2.2);
  vector v2(4);
  v2 = v;      // присваивание: что здесь происходит?
  // ...
}

Мы хотели бы, чтобы вектор v2 был копией вектора v (именно так функционирует стандартный класс vector), но поскольку в нашем классе vector смысл копирования не определен, используется присваивание по умолчанию; иначе говоря, присваивание выполняется почленно, и члены sz и elem объекта v2 становятся идентичными элементам sz и elem объекта v соответственно.

Эту ситуацию можно проиллюстрировать следующим образом:

При выходе из функции f2() возникнет такая же катастрофа, как и при выходе из функции f() в разделе 18.2, до того, как мы определили копирующий конструктор: элементы, на которые ссылаются оба вектора, v и v2, будут удалены дважды (с помощью оператора delete[]). Кроме того, возникнет утечка памяти, первоначально выделенной для вектора v2, состоящего из четырех элементов. Мы “забыли” их удалить. Решение этой проблемы в принципе не отличается от решения задачи копирующей инициализации (см. раздел 18.2.1). Определим копирующий оператор присваивания.

class vector {
  int sz;
  double* elem;
  void copy(const vector& arg); // копирует элементы из arg
                                // в *elem
public:
  vector& operator=(const vector&) ; // копирующее присваивание
  // ...
};

vector& vector::operator=(const vector& a)
 // делает этот вектор копией вектора a
{
  double* p = new double[a.sz]; // выделяем новую память
  for (int=0; i
    p[i]=a.elem[i];             // копируем элементы
  delete[] elem;                // освобождаем память
  elem = p;                     // теперь можно обновить elem
  sz = a.sz;
  return *this;      // возвращаем ссылку
                     // на текущий объект
 (см. раздел 17.10)
}

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

double* p = new double[a.sz]; // выделяем новую память
for(int=0; i

Теперь освобождаем старые элементы из целевого объекта класса vector.

delete[] elem; // освобождаем занятую память

В заключение установим указатель elem на новые элементы.

elem = p; // теперь можем изменить указатель elem
sz = a.sz;

Теперь в классе vector утечка памяти устранена, а память освобождается только один раз (delete[]).

 Реализуя присваивание, код можно упростить, освобождая память, занятую старыми элементами, до создания копии, но обычно не стоит стирать информацию, если вы не уверены, что ее можно заменить. Кроме того, если вы это сделаете, то при попытке присвоить объект класса vector самому себе могут возникнуть странные вещи.

vector v(10);
v=v; // самоприсваивание

Пожалуйста, убедитесь, что наша реализация функционирует правильно (если не оптимально). 

18.2.3. Терминология, связанная с копированием

Копирование встречается в большинстве программ и языков программирования. Основная проблема при этом заключается в том, что именно копируется: указатель (или ссылка) или информация, на которую он ссылается.

• Поверхностное копирование (shallow copy) предусматривает копирование только указателя, поэтому в результате на один и тот же объект могут ссылаться два указателя. Именно этот механизм копирования лежит в основе работы указателей и ссылок.

• Глубокое копирование (deep copy) предусматривает копирование информации, на которую ссылается указатель, так что в результате два указателя ссылаются на разные объекты. На основе этого механизма копирования реализованы классы vector, string и т.д. Если мы хотим реализовать глубокое копирование, то должны реализовать в наших классах конструктор копирования и копирующее присваивание.

Рассмотрим пример поверхностного копирования.

int* p = new int(77);
int* q = p; // копируем указатель p
*p = 88;    // изменяем значение переменной int, на которую
            // ссылаются указатели p и q 

Эту ситуацию можно проиллюстрировать следующим образом.

В противоположность этому мы можем осуществить глубокое копирование.

int* p = new int(77);
int* q = new int(*p); // размещаем новую переменную int,
                      // затем копируем значение, на которое
                      // ссылается p
*p = 88;              // изменяем значение, на которое ссылается p

Эту ситуацию можно проиллюстрировать так.

 Используя эту терминологию, мы можем сказать, что проблема с нашим исходным классом vector заключалась в том, что мы выполняли поверхностное копирование и не копировали элементы, на которые ссылался указатель elem. Наш усовершенствованный класс vector, как и стандартный класс vector, выполняет глубокое копирование, выделяя новую память для элементов и копируя их значения. О типах, предусматривающих поверхностное копирование (таких как указатели и ссылки), говорят, что они имеют семантику указателей (pointer semantics) или ссылок (reference semantics), т.е. копируют адреса. О типах, осуществляющих глубокое копирование (таких как string и vector), говорят, что они имеют семантику значений (value semantics), т.е. копируют значения, на которые ссылаются. С точки зрения пользователя типы с семантикой значений функционируют так, будто никакие указатели не используются, а существуют только значения, которые копируются. С точки зрения копирования типы, обладающие семантикой значений, мало отличаются от типа int. 

18.3. Основные операции

 Настал момент, когда мы можем приступить к обсуждению того, какие конструкторы должен иметь класс, должен ли он содержать деструктор и требуется ли копирующее присваивание. Следует рассмотреть пять важных операций.

• Конструкторы с одним или несколькими аргументами.

• Конструктор по умолчанию.

• Копирующий конструктор (копирование объектов одинаковых типов).

• Копирующее присваивание (копирование объектов одинаковых типов).

• Деструктор.

Обычно класс должен иметь один или несколько конструкторов, аргументы которых инициализируют объект.

string s(" Триумф "); // инициализируем объект s строкой "Триумф"
vector v(10); // создаем вектор v, состоящий из 10 чисел
                      // double

Как видим, смысл и использование инициализатора полностью определяются конструктором. Стандартный конструктор класса string использует в качестве начального значения символьную строку, а стандартный конструктор класса vector в качестве параметра получает количество элементов. Обычно конструктор используется для установки инварианта (см. раздел 9.4.3). Если мы не можем определить хороший инвариант для класса, то, вероятно, плохо спроектировали класс или структуру данных.

Конструкторы, имеющие аргументы, сильно зависят от класса, в котором они реализованы. Остальные операции имеют более или менее стандартную структуру.

Как понять, что в классе необходим конструктор по умолчанию? Он требуется тогда, когда мы хотим создавать объекты класса без указания инициализатора. Наиболее распространенный пример такой ситуации возникает, когда мы хотим поместить объекты класса в стандартный контейнер, имеющий тип vector. Приведенные ниже инструкции работают только потому, что для типов int, string и vector существуют значения, предусмотренные по умолчанию.

vector vi(10); // вектор из 10 элементов типа double,
                       // каждый из них инициализирован 0.0
vector vs(10); // вектор из 10 элементов типа string,
                       // каждый из них инициализирован ""
vector> vvi(10); // вектор из 10 векторов,
                               // каждый из них
                               // инициализирован конструктором
 vector()

Итак, иметь конструктор по умолчанию часто бывает полезно. Возникает следующий вопрос: а когда именно целесообразно иметь конструктор по умолчанию? Ответ: когда мы можем установить инвариант класса с осмысленным и очевидным значением по умолчанию. Для числовых типов, таких как int и double, очевидным значением является 0 (для типа double оно принимает вид 0.0). Для типа string очевидным выбором является "". Для класса vector можно использовать пустой вектор. Если тип T имеет значение по умолчанию, то оно задается конструктором T(). Например, double() равно 0.0, string() равно "", а vector() — это пустой vector, предназначенный для хранения переменных типа int.

 Если класс обладает ресурсами, то он должен иметь деструктор. Ресурс — это то, что вы “где-то взяли” и должны вернуть, когда закончите его использовать. Очевидным примером является память, выделенная с помощью оператора new, которую вы должны освободить, используя оператор delete или delete[]. Для хранения своих элементов наш класс vector требует память, поэтому он должен ее вернуть; следовательно, он должен иметь деструктор. Другие ресурсы, которые используются в более сложных программах, — это файлы (если вы открыли файл, то должны его закрыть), блокировки (locks), дескрипторы потоков (thread handles) и двунаправленные каналы (sockets), используемые для обеспечения взаимосвязи между процессами и удаленными компьютерами.

 Другой признак того, что в классе необходим деструктор, — это наличие членов класса, которые являются указателями или ссылками. Если одним из членов класса является указатель или ссылка, скорее всего, в нем требуются деструктор и операции копирования.

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

 Если производный класс должен иметь деструктор, то базовый класс должен иметь виртуальный деструктор (см. раздел 17.5.2).

18.3.1. Явные конструкторы

Конструктор, имеющий один аргумент, определяет преобразование типа этого аргумента в свой класс. Это может оказаться очень полезным. Рассмотрим пример.

class complex {
public:
  complex(double); // определяет преобразование double в complex
  complex(double,double);
  // ...
};

complex z1 = 3.18; // OK: преобразует 3.18 в (3.18,0)
complex z2 = complex(1.2, 3.4);

 Однако неявные преобразования следует применять скупо и осторожно, поскольку они могут вызвать неожиданные и нежелательные эффекты. Например, наш класс vector, определенный выше, имеет конструктор, принимающий аргумент типа int. Отсюда следует, что он определяет преобразование типа int в класс vector. Рассмотрим пример.

class vector {
  // ...
vector(int);
  // ...
};

vector v = 10;  // создаем вектор из 10 элементов типа double
v = 20;         // присваиваем вектору v новый вектор
                // из 20 элементов типа double to v
void f(const vector&);
f(10);          // Вызываем функцию f с новым вектором,
                // состоящим из 10 элементов типа double

 Кажется, мы получили больше, чем хотели. К счастью, подавить такое неявное преобразование довольно просто. Конструктор с ключевым словом explicit допускает только обычную семантику конструирования и не допускает неявные преобразования. Рассмотрим пример.

class vector {
  // ...
  explicit vector(int);
  // ...
};

vector v = 10;  // ошибка: преобразования int в vector нет
v = 20;         // ошибка: преобразования int в vector нет
vector v0(10);  // OK

void f(const vector&);
f(10);          // ошибка: преобразования int в vector нет
f(vector(10)); // OK

Для того чтобы избежать неожиданных преобразований, мы — и стандарт языка — потребовали, чтобы конструктор класса vector с одним аргументом имел спецификатор explicit. Очень жаль, что все конструкторы не имеют спецификатора explicit по умолчанию; если сомневаетесь, объявляйте конструктор, который может быть вызван с одним аргументом, используя ключевое слово explicit. 

118.3.2. Отладка конструкторов и деструкторов

 Конструкторы и деструкторы вызываются в точно определенных и предсказуемых местах программы. Однако мы не всегда пишем явные вызовы, например vector(2); иногда мы пишем объявление объекта класса vector, передаем его как аргумент функции по значению или создаем в свободной памяти с помощью оператора new. Это может вызвать замешательство у людей, думающих в терминах синтаксиса. Не существует синтаксической конструкции, которая осуществляла бы диспетчеризацию вызовов конструкторов. О конструкторах и деструкторах проще думать следующим образом.

• Когда создается объект класса X, вызывается один из его конструкторов.

• Когда уничтожается объект типа X, вызывается его деструктор.

Деструктор вызывается всегда, когда уничтожается объект класса; это происходит, когда объект выходит из области видимости, программа прекращает работу или к указателю на объект применяется оператор delete. Подходящий конструктор вызывается каждый раз, когда создается объект класса; это происходит при инициализации переменной, при создании объекта с помощью оператора new (за исключением встроенных типов), а также при копировании объекта.

Что же при этом происходит? Для того чтобы понять это, добавим в конструкторы, операторы копирующего присваивания и деструкторы операторы вывода. Рассмотрим пример.

struct X { // простой тестовый класс
  int val;
  void out(const string& s)
    { cerr << this << "–>" << s << ": " << val << "\n"; }
  X(){ out("X()"); val=0; }      // конструктор по умолчанию
  X(int v) { out( "X(int)"); val=v; }
  X(const X& x){ out("X(X&) "); val=x.val; } // копирующий
                                             // конструктор
  X& operator=(const X& a)       // копирующее присваивание
    { out("X::operator=()"); val=a.val; return *this; }
  ~X() { out("~X()"); }          // деструктор
};

Проследим, что происходит при выполнении операций над объектом класса X. Рассмотрим пример.

X glob(2);   // глобальная переменная
X copy(X a) { return a; }
X copy2(X a) { X aa = a; return aa; }
X& ref_to(X& a) { return a; }
X* make(int i) { X a(i); return new X(a); }
struct XX { X a; X b; };

int main()
{
  X loc(4);         // локальная переменная
  X loc2 = loc;
  loc = X(5);
  loc2 = copy(loc);
  loc2 = copy2(loc);
  X loc3(6);
  X& r = ref_to(loc);
  delete make(7);
  delete make(8);
  vector v(4);
  XX loc4;
  X* p = new X(9);  // объект класса Х в свободной памяти
  delete p;
  X* pp = new X[5]; // массив объектов класса X
                    // в свободной памяти
  delete[]pp;
}

Попробуйте выполнить эту программу.

ПОПРОБУЙТЕ

Мы имеем в виду следующее: выполните эту программу и убедитесь, что понимаете результаты ее работы. Если понимаете, то вы знаете почти все, что требуется знать о создании и уничтожении объектов.

 В зависимости от качества вашего компилятора вы можете заметить пропущенные копии, связанные с вызовами функций copy() и copy2(). Мы (люди) видим, что эти функции ничего не делают; они просто копируют значение из потока ввода в поток вывода без каких-либо изменений. Если компилятор настолько хорош, что заметит это, то сможет удалить эти вызовы конструктора копирования. Иначе говоря, компилятор может предполагать, что конструктор копирования только копирует и ничего больше не делает. Некоторые компиляторы настолько “умны”, что могут исключить фиктивные копии.

Так зачем же возиться с этим “глупым классом X”? Это напоминает упражнения для пальцев, которые выполняют музыканты. После этих упражнений многие вещи, которые обладают намного большим смыслом, становятся понятнее и легче. Кроме того, если у вас возникнут проблемы с конструкторами и деструкторами, рекомендуем вставить в них операторы вывода и посмотреть, как они работают. Для более крупных программ такая отладка становится утомительной, но для них изобретены аналогичные технологии отладки. Например, мы можем выявить, происходит ли утечка памяти, определив, равна ли нулю разность между количеством вызовов конструктора и деструктора. Программисты часто забывают определить копирующие конструкторы и копирующее присваивание для классов, выделяющих память или содержащих указатели на объекты. Это порождает проблемы (которые, впрочем, легко устранить).

Если ваши проблемы слишком велики, чтобы решить их с помощью таких простых средств, освойте профессиональные средства отладки; они называются детекторами утечек (leak detectors). В идеале, разумеется, следует не устранять утечки, а программировать так, чтобы они вообще не возникали. 

18.4. Доступ к элементам вектора

До сих пор (см. раздел 17.6) для доступа к элементам вектора мы использовали функции-члены set() и get(). Но этот способ слишком громоздок и некрасив. Мы хотим использовать обычную индексацию: v[i]. Для этого следует определить функцию-член с именем operator[]. Вот ее первая (наивная) версия.

class vector {
  int sz;         // размер
  double* elem;   // указатель на элементы
public:
  // ...
  double operator[](int n) { return elem[n]; } // возвращаем
                                               // элемент
};

Все выглядит хорошо и просто, но, к сожалению, слишком просто. Разрешив оператору индексирования (operator[]()) возвращать значение, мы разрешили чтение, но не запись элементов.

vector v(10);
int x = v[2]; // хорошо
v[3] = x;     // ошибка: v[3] не может стоять в левой
              // части оператора =

Здесь выражение v[i] интерпретируется как вызов оператора v.operator[](i), который возвращает значение элемента вектора v с номером i. Для такого слишком наивного варианта класса vector значение v[3] является числом с плавающей точкой, а не переменной, содержащей число с плавающей точкой.

ПОПРОБУЙТЕ

Создайте вариант класса vector, скомпилируйте его и посмотрите на сообщение об ошибке, которое ваш компилятор выдаст для инструкции v[3]=x;.

В следующей версии мы разрешим оператору operator[] возвращать указатель на соответствующий элемент:

class vector {
  int sz;        // размер
  double* elem;  // указатель на элемент
public:
  // ...
  double* operator[](int n) { return &elem[n]; } // возвращаем
                                                 // указатель
};

При таком определении мы можем записывать элементы.

vector v(10);
for (int i=0; i
                                 // некрасиво
  *v[i] = i;
cout << *v[i];
}

Здесь выражение v[i] интерпретируется как вызов оператора v.operator[](i) и возвращает указатель на элемент вектора v с номером i. Проблема в том, что теперь мы должны написать оператор *, чтобы разыменовать указатель, ссылающийся на этот элемент. Это так же некрасиво, как и функции set() и get(). Проблему можно устранить, если вернуть из оператора индексирования ссылку.

class vector {
  // ...
  double& operator[ ](int n) { return elem[n]; } // возвращаем
                                                 // ссылку
};

Теперь можем написать следующий вариант.

vector v(10);
for (int i=0; i
  v[i] = i;        // v[i] возвращает ссылку на элемент с номером i
 cout << v[i];
}

Мы обеспечили традиционные обозначения: выражение v[i] интерпретируется как вызов оператора v.operator[](i) и возвращает ссылку на элемент вектора v с номером i.

18.4.1. Перегрузка ключевого слова const

Функция operator[](), определенная выше, имеет один недостаток: ее нельзя вызвать для константного вектора. Рассмотрим пример.

void f(const vector& cv)
{
  double d = cv[1]; // неожиданная ошибка
  cv[1] = 2.0;      // ожидаемая ошибка
}

Причина заключается в том, что наша функция vector::operator[]() потенциально может изменять объект класса vector. На самом деле она этого не делает, но компилятор об этом не знает, потому что мы забыли сообщить ему об этом. Для того чтобы решить эту проблему, необходимо предусмотреть функцию-член со спецификатором const (см раздел 9.7.4). Это легко сделать.

class vector {
  // ...
  double& operator[](int n);      // для неконстантных векторов
  double operator[](int n) const; // для константных векторов
};

Очевидно, что мы не могли бы вернуть ссылку типа double& из версии со спецификатором const, поэтому возвращаем значение типа double. С таким же успехом мы могли бы вернуть ссылку типа const double &, но, поскольку объект типа double невелик, не имеет смысла возвращать ссылку (см. раздел 8.5.6), и мы решили вернуть значение. Теперь можно написать следующий код:

void ff(const vector& cv, vector& v)
{
  double d = cv[1]; // отлично (использует константный вариант [ ])
  cv[1] = 2.0;      // ошибка (использует константный вариант [ ])
  double d = v[1];  // отлично (использует неконстантный вариант [ ])
  v[1] = 2.0;       // отлично (использует неконстантный вариант [ ])
}

Поскольку объекты класса vector часто передаются по константной ссылке, эта версия оператора operator[]() с ключевым словом const является существенным дополнением. 

18.5. Массивы

 До сих пор мы использовали слово массив (array) для названия последовательности объектов, расположенных в свободной памяти. Тем не менее массивы можно размещать где угодно как именованные переменные. На самом деле это распространенная ситуация. Они могут использоваться следующим образом.

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

• Как локальные переменные (однако массивы накладывают на них серьезные ограничения).

• Как аргументы функции (но массив не знает своего размера).

• Как член класса (хотя массивы, являющиеся членами класса, трудно инициализировать).

 Возможно, вы заметили, что мы отдаем заметное предпочтение классу vector по сравнению с массивами. Класс std::vector следует использовать при любой возможности. Однако массивы существовали задолго до появления векторов и являлись их приблизительным прототипом во многих языках (особенно в языке C), поэтому их следует знать хорошо, чтобы иметь возможность работать со старыми программами или с программами, написанными людьми, не признающими преимущества класса vector.

 Итак, что такое массив? Как его определить и как использовать? Массив — это однородная последовательность объектов, расположенных в смежных ячейках памяти; иначе говоря, все элементы массива имеют один и тот же тип, и между ними нет пробелов. Элементы массива нумеруются, начиная с нуля в возрастающем порядке. В объявлении массив выделяется квадратными скобками.

const int max = 100;
int gai[max];   // глобальный массив (из 100 чисел типа int);
                // "живет всегда"

void f(int n)
{
  char lac[20]; // локальный массив; "живет" до конца области
                // видимости
  int lai[60];
  double lad[n]; // ошибка: размер массива не является константой
  // ...
}

Обратите внимание на ограничение: количество элементов именованного массива должно быть известно на этапе компиляции. Если мы хотим, чтобы количество элементов массива было переменным, то должны разместить его в свободной памяти и обращаться к нему через указатель. Именно так поступает класс vector с массивами элементов.

Как и к элементам массивов, размещенных в свободной области, доступ к элементам именованных массивов осуществляется с помощью операторов индексирования и разыменования ([ ] и *). Рассмотрим пример.

void f2()
{
  char lac[20];   // локальный массив; "живет" до конца области
                  // видимости
  lac[7] = 'a';
  *lac = 'b';     // эквивалент инструкции lac[0]='b'
  lac[–2] = 'b';  // ??
  lac[200] = 'c'; // ??
}

 Эта функция компилируется, но, как мы знаем, не все скомпилированные функции работают правильно. Использование оператора [ ] очевидно, но проверка выхода за пределы допустимого диапазона отсутствует, поэтому функция f2() компилируется, а результат записи lac[–2] и lac[200] приводит к катастрофе (как всегда, при выходе за пределы допустимого диапазона). Не делайте этого. Массивы не проверяют выход за пределы допустимого диапазона. И снова здесь нам приходится непосредственно работать с физической памятью, так как на системную поддержку рассчитывать не приходится.

 А не мог ли компилятор как-то увидеть, что массив lac содержит только двадцать элементов, так что выражение lac[200] — это ошибка? В принципе мог бы, но, как нам известно, в настоящее время не существует ни одного такого компилятора. Дело в том, что отследить границы массива на этапе компиляции невозможно в принципе, а перехват простейших ошибок (таких как приведены выше) не решает всех проблем. 

18.5.1. Указатели на элементы массива

Указатель может ссылаться на элемент массива. Рассмотрим пример.

double ad[10];
double* p = &ad[5]; // ссылается на элемент ad[5]

Указатель p ссылается на переменную типа double, известную как ad[5].

Этот указатель можно индексировать и разыменовывать.

*p =7;
p[2] = 6;
p[–3] = 9;

Теперь ситуация выглядит следующим образом.

Иначе говоря, мы можем индексировать указатель с помощью как положительных, так и отрицательных чисел. Поскольку результаты не выходят за пределы допустимого диапазона, эти выражения являются правильными. Однако выход на пределы допустимого диапазона является незаконным (аналогично массивам, размещенным в свободной памяти; см. раздел 17.4.3). Как правило, выход за пределы массива компилятором не распознается и (рано или поздно) приводит к катастрофе.

Если указатель ссылается на элемент внутри массива, то для его переноса на другой элемент можно использовать операции сложения и вычитания. Рассмотрим пример.

p += 2; // переносим указатель p на два элемента вправо

Итак, приходим к следующей ситуации.

Аналогично,

p –= 5; // переносим указатель p на пять элементов вправо

В итоге получим следующее.

 Использование операций +, –, += и –= для переноса указателей называется арифметикой указателей (pointer arithmetic). Очевидно, поступая так, мы должны проявлять большую осторожность, чтобы не выйти за пределы массива.

p += 1000;     // абсурд: p ссылается на массив, содержащий
               // только 10 чисел
double d = *p; // незаконно: возможно неправильное значение
               // (совершенно непредсказуемое)
*p = 12.34;    // незаконно: можно задеть неизвестные данные

К сожалению, не все серьезные ошибки, связанные с арифметикой указателей, легко обнаружить. Лучше всего просто избегать использования арифметики указателей.

Наиболее распространенным использованием арифметик указателей является инкрементация указателя (с помощью оператора ++) для ссылки на следующий элемент и декрементация указателя (с помощью оператора ––) для ссылки на предыдущий элемент. Например, мы могли вы вывести элементы массива ad следующим образом:

for (double* p = &ad[0]; p<&ad[10]; ++p) cout << *p << '\n';

И в обратном порядке:

for (double* p = &ad[9]; p>=&ad[0]; ––p) cout << *p << '\n';

Это использование арифметики указателей не слишком широко распространено. Однако, по нашему мнению, последний (“обратный”) пример небезопасен. Почему &ad[9], а не &ad[10]? Почему >=, а не >? Эти примеры были бы одинаково хороши (и одинаково эффективны), если бы мы использовали индексацию. Кроме того, они были бы совершенно эквивалентны в классе vector, в котором проверка выхода за пределы допустимого диапазона осуществляется проще.

Отметим, что в большинстве реальных программ арифметика указателей связана с передачей указателя в качестве аргумента функции. В этом случае компилятор не знает, на сколько элементов ссылается указатель, и вы должны следить за этим сами. Этой ситуации необходимо избегать всеми силами.

Почему в языке C++ вообще разрешена арифметика указателей? Ведь это так хлопотно и не дает ничего нового по сравнению с тем, что можно сделать с помощью индексирования. Рассмотрим пример.

double* p1 = &ad[0];
double* p2 = p1+7;
double* p3 = &p1[7];
if (p2 != p3) cout << "impossible!\n";

 В основном это произошло по историческим причинам. Эти правила были разработаны для языка C несколько десяткой лет назад, и отменить их невозможно, не выбросив в мусорную корзину огромное количество программ. Частично это объясняется тем, что арифметика указателей обеспечивает определенное удобство в некоторых низкоуровневых приложениях, например в механизме управления памятью.

18.5.2. Указатели и массивы

 Имя массива относится ко всем элементам массива. Рассмотрим пример.

char ch[100];

Размер массива ch, т.е. sizeof(ch), равен 100. Однако имя массива без видимых причин превращается в указатель.

char* p = ch;

Здесь указатель p инициализируется адресом &ch[0], а размер sizeof(p) равен 4 (а не 100). Это свойство может быть полезным. Например, рассмотрим функцию strlen(), подсчитывающую количество символов в массиве символов, завершающимся нулем.

int strlen(const char* p) // аналогична стандартной
                          // функции strlen()
{
  int count = 0;
  while (*p) { ++count; ++p; }
  return count;
}

Теперь можем вызвать ее как с аргументом strlen(ch), так и с аргументом strlen(&ch[0]). Возможно, вы заметили, что такое обозначение дает очень небольшое преимущество, и мы с вами согласны. Одна из причин, по которым имена массивов могут превращаться в указатели, состоит в желании избежать передачи большого объема данных по значению. Рассмотрим пример.

int strlen(const char a[]) // аналогична стандартной
                           // функции strlen()
{
  int count = 0;
  while (a[count]) { ++count; }
  return count;
}

char lots [100000];

void f()
{
 int nchar = strlen(lots);
 // ... 

Наивно (но частично обоснованно) мы могли бы ожидать, что при выполнении этого вызова будут скопированы 100 тыс. символов, заданных как аргумент функции strlen(), но этого не происходит. Вместо этого объявление аргумента char p[] рассматривается как эквивалент объявления char* p, а вызов strlen(lots) — как эквивалент вызова strlen(&lots[0]). Это предотвращает затратное копирование, но должно вас удивить. Почему вы должны удивиться? Да потому, что в любой другой ситуации при передаче объекта, если вы не потребуете явно, чтобы он передавался по ссылке (см. разделы 8.5.3–8.5.6), этот объект будет скопирован.

Обратите внимание на то, что указатель, образованный из имени массива, установлен на его первый элемент и не является переменной, т.е. ему ничего нельзя присвоить.

char ac[10];
ac = new char [20];     // ошибка: имени массива ничего присвоить нельзя
&ac[0] = new char [20]; // ошибка: значению указателя ничего
                        // присвоить нельзя

И на десерт — проблема, которую компилятор может перехватить!

Вследствие неявного превращения имени массива в указатель мы не можем даже скопировать массивы с помощью оператора присваивания.

int x[100];
int y[100];
// ...
x = y;          // ошибка
int z[100] = y; // ошибка

Это логично, но неудобно. Если необходимо скопировать массив, вы должны написать более сложный код. Рассмотрим пример.

for (int i=0; i<100; ++i) x[i]=y[i]; // копируем 100 чисел типа int
memcpy(x,y,100*sizeof(int)); // копируем 100*sizeof(int) байт
copy(y,y+100, x); // копируем 100 чисел типа int

Поскольку в языке C нет векторов, в нем интенсивно используются массивы. Вследствие этого в огромном количестве программ, написанных на языке C++, используются массивы (подробнее об этом — в разделе 27.1.2). В частности, строки в стиле C (массивы символов, завершаемые нулем; эта тема рассматривается в разделе 27.5) распространены очень широко.

Если хотите копировать, то используйте класс, аналогичный классу vector. Код копирования объектов класса vector, эквивалентный приведенному выше, можно записать следующим образом:

vector x(100);
vector y(100);
// ...
x = y;    // копируем 100 чисел типа int

18.5.3. Инициализация массива

 Массивы имеют одно значительное преимущество над векторами и другими контейнерами, определенными пользователями: язык С++ предоставляет поддержку для инициализации массивов. Рассмотрим пример.

char ac[] = "Beorn"; // массив из шести символов

Подсчитайте эти символы. Их пять, но ac становится массивом из шести символов, потому что компилятор добавляет завершающий нуль в конце строкового литерала.

Строка, завершающаяся нулем, является обычным явлением в языке С и многих системах. Такие массивы символов, завершающиеся нулем, мы называем строками в стиле языка С (C-style string). Все строковые литералы являются строками в стиле языка C. Рассмотрим пример.

char* pc = "Howdy"; // указатель pc ссылается на массив из шести
                    // символов

Графически это можно изобразить следующим образом.

Переменная типа char, имеющая числовое значение 0, — это не символ '0', не буква и не цифра. Цель этого завершающего нуля — помочь функции найти конец строки. Помните: массив не знает своего размера. Полагаясь на использование завершающего нуля, мы можем написать следующий код:

int strlen(const char* p) // похоже на стандартную функцию strlen()
{
  int n = 0;
  while (p[n]) ++n;
  return n;
}

На самом деле мы не обязаны определять функцию strlen(), поскольку это уже стандартная библиотечная функция, определенная в заголовочном файле (разделы 27.5 и Б.10.3). Обратите внимание на то, что функция strlen() подсчитывает символы, но игнорирует завершающий нуль; иначе говоря, для хранения n символов в строке в стиле языка С необходимо иметь память для хранения n+1 переменной типа char.

Только символьные массивы можно инициализировать с помощью литеральных констант, но любой массив можно инициализировать списком значений его элементов соответствующего типа. Рассмотрим пример.

int ai[] = { 1, 2, 3, 4, 5, 6 };        // массив из шести чисел
                                        // типа int
int ai2[100] = { 0,1,2,3,4,5,6,7,8,9 }; // остальные 90 элементов
                                        // инициализируются нулем
double ad[100] = { };             // все элементы инициализируются нулем
char chars[] = { 'a', 'b', 'c' }; // нет завершающего нуля!

Обратите внимание на то, что количество элементов в массиве ai равно шести (а не семи), а количество элементов в массиве chars равно трем (а не четырем), — правило “добавить нуль в конце” относится только к строковым литералам. Если размер массива не задан явно, то он определяется по списку инициализации. Это довольно полезное правило. Если количество элементов в списке инициализации окажется меньше, чем количество элементов массива (как в определениях массивов ai2 и ad), остальные элементы инициализируются значениями, предусмотренными для данного типа элементов по умолчанию.

18.5.4. Проблемы с указателями

Как и массивами, указателями часто злоупотребляют. Люди часто сами создают себе проблемы, используя указатели и массивы. В частности, все серьезные проблемы, связанные с указателями, вызваны обращением к области памяти, которая не является объектом ожидаемого типа, причем многие из этих проблем, в свою очередь, вызваны выходом за пределы массива. Перечислим эти проблемы.

• Обращение по нулевому указателю.

• Обращение по неинициализированному указателю.

• Выход за пределы массива.

• Обращение к удаленному объекту.

• Обращение к объекту, вышедшему из области видимости.

На практике во всех перечисленных ситуациях главная проблема, стоящая перед программистом, заключается в том, что внешне фактический доступ выглядит вполне невинно; просто указатель ссылается на неправильное значение. Что еще хуже (при записи с помощью указателя), проблема может проявиться намного позднее, когда окажется, что некий объект, не связанный с программой, был поврежден. Рассмотрим следующий пример.

Не обращайтесь к памяти с помощью нулевого указателя.

int* p = 0;
*p = 7;   // Ой!

Очевидно, что в реальной программе это может произойти, если между инициализацией и использованием указателя размещен какой-то код. Чаще всего эта ошибка возникает при передаче указателя p функции или при получении его в результате работы функции. Мы рекомендуем никуда не передавать нулевой указатель, но, уж если вы это сделали, проверьте указатель перед его использованием. Например,

int* p = fct_that_can_return_a_0();
if (p == 0) {
  // что-то делаем
}
else {
  // используем р
  *p = 7;
}

и

void fct_that_can_receive_a_0(int* p)
{
  if (p == 0) {
    // что-то делаем
  }
  else {
    // используем р
    *p = 7;
  }
}

Основными средствами, позволяющими избежать ошибок, связанных с нулевыми указателями, являются ссылки (см. раздел 17.9.1) и исключения (см. разделы 5.6 и 19.5).

Инициализируйте указатели.

int* p;
*p = 9; // Ой!

В частности, не забывайте инициализировать указатели, являющиеся членами класса.

Не обращайтесь к несуществующим элементам массива.

int a[10];
int* p = &a[10];
*p = 11;     // Ой!
a[10] = 12;  // Ой!

Будьте осторожны, обращаясь к первому и последнему элементам цикла, и постарайтесь не передавать массивы с помощью указателей на их первые элементы. Вместо этого используйте класс vector. Если вам действительно необходимо использовать массив в нескольких функциях (передавая его как аргумент), будьте особенно осторожны и не забудьте передать размер массива.

Не обращайтесь к памяти с помощью удаленного указателя.

int* p = new int(7);
// ...
delete p;
// ...
*p = 13;  // Ой!

Инструкция delete p или код, размещенный после нее, может неосторожно обратиться к значению *p или использовать его косвенно. Все эти ситуации совершенно недопустимы. Наиболее эффективной защитой против этого является запрет на использование “голых” операторов new, требующих выполнения “голых” операторов delete: выполняйте операторы new и delete в конструкторах и деструкторах или используйте контейнеры, такие как Vector_ref (раздел Д.4).

Не возвращайте указатель на локальную переменную.

int* f()
{
  int x = 7;
  // .. .
  return &x;
}

// ...
int* p = f();
// ...
*p = 15;   // Ой!

Возврат из функции f() или код, размещенный после него, может неосторожно обратиться к значению *p или использовать его косвенно. Причина заключается в том, что локальные переменные, объявленные в функции, размещаются в стеке перед вызовом функции и удаляются из него при выходе. В частности, если локальной переменной является объект класса, то вызывается его деструктор (см. раздел 17.5.1). Компиляторы не способны распознать большинство проблем, связанных с возвращением указателей на локальные переменные, но некоторые из них они все же выявляют.

Рассмотрим эквивалентный пример.

vector& ff()
{
  vector x(7);
  // ...
  return x;
}   // здесь вектор х был уничтожен

// ...
vector& p = ff();
// ...
p[4] = 15;   // Ой!

Только некоторые компиляторы распознают такую разновидность проблемы, связанной с возвращением указателя на локальную переменную. Обычно программисты недооценивают эти проблемы. Однако многие опытные программисты терпели неудачи, сталкиваясь с бесчисленными вариациями и комбинациями проблем, порожденных использованием простых массивов и указателей. Решение очевидно — не замусоривайте свою программу указателями, массивами, операторами new и delete. Если же вы поступаете так, то просто быть осторожным в реальной жизни недостаточно. Полагайтесь на векторы, концепцию RAII (“Resource Acquisition Is Initialization” — “Получение ресурса — это инициализация”; см. раздел 19.5), а также на другие систематические подходы к управлению памятью и другими ресурсами.

18.6. Примеры: палиндром

Довольно технических примеров! Попробуем решить маленькую головоломку. Палиндром (palindrome) — это слово, которое одинаково читается как слева направо так и справа налево. Например, слова anna, petep и malayalam являются палиндромами, а слова ida и homesick — нет. Есть два основных способа определить, является ли слово палиндромом.

• Создать копию букв, расположенных в противоположном порядке, и сравнить ее с оригиналом.

• Проверить, совпадает ли первая буква с последней, вторая — с предпоследней, и так далее до середины.

Мы выбираем второй подход. Существует много способов выразить эту идею в коде. Они зависят от представления слова и от способа отслеживания букв в слове. Мы напишем небольшую программу, которая будет по-разному проверять, является ли слово палиндромом. Это просто позволит нам выяснить, как разные особенности языка программирования влияют на внешний вид и работу программы. 

18.6.1. Палиндромы, созданные с помощью класса string

Прежде всего напишем вариант программы, используя стандартный класс string, в котором индексы сравниваемых букв задаются переменной типа int.

bool is_palindrome(const string& s)
{
  int first = 0;           // индекс первой буквы
  int last = s.length()–1; // индекс последней буквы
  while (first < last) {   // мы еще не достигли середины слова
    if (s[first]!=s[last]) return false;
    ++first;  // вперед
    ––last;   // назад
  }
  return true;
}

Мы возвращаем значение true, если достигли середины слова, не обнаружив разницы между буквами. Предлагаем вам просмотреть этот код и самим убедиться, что он работает правильно, когда в строке вообще нет букв, когда строка состоит только из одной буквы, когда в строке содержится четное количество букв и когда в строке содержится нечетное количество букв. Разумеется, мы не должны полагаться только на логику, стараясь убедиться, что программа работает правильно. Попробуем выполнить функцию is_palindrome().

int main()
{
  string s;
  while (cin>>s) {
    cout << s << " is";
    if (!is_palindrome(s)) cout << " not";
    cout << " a palindrome\n";
  }
}

По существу, причина, по которой мы используем класс string, заключается в том, что объекты класса string хорошо работают со словами. Они достаточно просто считывают слова, разделенные пробелами, и знают свой размер. Если бы мы хотели применить функцию is_palindrome() к строкам, содержащим пробелы, то просто считывали бы их с помощью функции getline() (см. раздел 11.5). Это можно было бы продемонстрировать на примере строк ah ha и as df fd sa.

18.6.2. Палиндромы, созданные с помощью массива

А если бы у нас не было класса string (или vector) и нам пришлось бы хранить символы в массиве? Посмотрим.

bool is_palindrome(const char s[], int n)
 // указатель s ссылается на первый символ массива из n символов
{
  int first = 0;         // индекс первой буквы
  int last = n–1;        // индекс последней буквы
  while (first < last) { // мы еще не достигли середины слова
  if (s[first]!=s[last]) return false;
  ++first;   // вперед
  ––last;    // назад
  }
  return true;
}

Для того чтобы выполнить функцию is_palindrome(), сначала необходимо записать символы в массив. Один из безопасных способов (без риска переполнения массива) выглядит так:

istream& read_word(istream& is, char* buffer, int max)
 // считывает не более max–1 символов в массив buffer
{
  is.width(max); // при выполнении следующего оператора >>
                 // будет считано не более max–1 символов
  is >> buffer;  // читаем слово, разделенное пробелами,
                 // добавляем нуль после последнего символа
  return is;
}

Правильная установка ширины потока istream предотвращает переполнение массива при выполнении следующего оператора >>. К сожалению, это также означает, что нам неизвестно, завершается ли чтение пробелом или буфер полон (поэтому нам придется продолжить чтение). Кроме того, кто помнит особенности поведения функции width() при вводе? Стандартные классы string и vector на самом деле лучше, чем буферный ввод, поскольку они могут регулировать размер буфера при вводе. Завершающий символ 0 необходим, так как большинство операций над массивами символов (строка в стиле языка C) предполагают, что массив завершается нулем. Используя функцию read_word(), можно написать следующий код:

int main()
{
  const int max = 128;
  char s[max];
  while (read_word(cin,s,max)) {
    cout << s << " is";
    if (!is_palindrome(s,strlen(s))) cout << " not";
    cout << " a palindrome\n";
  }
}

Вызов strlen(s) возвращает количество символов в массиве после выполнения вызова read_word(), а инструкция cout< выводит символы из массива, завершающегося нулем.

 Решение задачи с помощью класса string намного аккуратнее, чем с помощью массивов. Это проявляется намного ярче, когда приходится работать с длинными строками (см. упр. 10).

18.6.3. Палиндромы, созданные с помощью указателей

Вместо использования индексов для идентификации символов можно было бы применить указатели.

bool is_palindrome(const char* first, const char* last)
 // указатель first ссылается на первую букву
 // указатель last ссылается на последнюю букву
{
  while (first < last) {   // мы еще не достигли середины
    if (*first!=*last) return false;
    ++first;  // вперед
    ––last;   // назад
  }
  return true;
}

 Отметим, что указатели можно инкрементировать и декрементировать. Инкрементация устанавливает указатель на следующий элемент массива, а декрементация — на предыдущий. Если в массиве нет следующего или предыдущего элемента, возникнет серьезная ошибка, связанная с выходом за пределы допустимого диапазона. Это еще одна проблема, порожденная указателями.

Функция is_palindrome() вызывается следующим образом:

int main()
{
  const int max = 128;
  char s[max];
  while (read_word(cin,s,max)) {
    cout << s << " is";
    if (!is_palindrome(&s[0],&s[strlen(s)–1])) cout << " not";
    cout << " a palindrome\n";
  }
}

Просто забавы ради мы переписали функцию is_palindrome() следующим образом:

bool is_palindrome(const char* first, const char* last)
 // указатель first ссылается на первую букву
 // указатель last ссылается на последнюю букву
{
  if (first
    if (*first!=*last) return false;
    return is_palindrome(first+1,last-1);
  }
  return true;
}

Этот код становится очевидным, если перефразировать определение палиндрома: слово является палиндромом, если его первый и последний символы совпадают и если подстрока, возникающая после отбрасывания первого и последнего символов, также является палиндромом.

Задание

В этой главе мы ставим два задания: одно необходимо выполнить с помощью массивов, а второе — с помощью векторов. Выполните оба задания и сравните количество усилий, которые вы при этом затратили.

Задание с массивами

1. Определите глобальный массив ga типа int, состоящий из десяти целых чисел и инициализированный числами 1, 2, 4, 8, 16 и т.д.

2. Определите функцию f(), принимающую в качестве аргументов массив типа int и переменную типа int, задающую количество элементов в массиве.

3. В функции f() выполните следующее.

3.1. Определите локальный массив la типа int, состоящий из десяти элементов.

3.2. Скопируйте значения из массива ga в массив la.

3.3. Выведите на печать элементы массива la.

3.4. Определите указатель p, ссылающийся на переменную типа int, и инициализируйте его адресом массива, расположенного в свободной памяти и хранящего такое же количество элементов, как и массив, являющийся аргументов функции.

3.5. Скопируйте значения из массива, являющегося аргументом функции, в массив, расположенный в свободной памяти.

3.6. Выведите на печать элементы массива, расположенного в свободной памяти.

3.7. Удалите массив из свободной памяти.

4. В функции main() сделайте следующее.

4.1. Вызовите функцию f() с аргументом ga.

4.2. Определите массив aa, содержащий десять элементов, и инициализируйте его первыми десятью значениями факториала (т.е. 1, 2*1, 3*2*1, 4*3*2*1 и т.д.).

4.3. Вызовите функцию f() с аргументом aa.

Задание со стандартным вектором

1. Определите глобальный вектор vector gv; инициализируйте его десятью целыми числами 1, 2, 4, 8, 16 и т.д.

2. Определите функцию f(), принимающую аргумент типа vector.

3. В функции f() сделайте следующее.

3.1. Определите локальный вектор vector lv с тем же количеством элементов, что и вектор, являющийся аргументом функции.

3.2. Скопируйте значения из вектора gv в вектор lv.

3.3. Выведите на печать элементы вектора lv.

3.4. Определите локальный вектор vector lv2; инициализируйте его копией вектора, являющегося аргументом функции.

3.5. Выведите на печать элементы вектора lv2.

4. В функции main() сделайте следующее.

4.1. Вызовите функцию f() с аргументом gv.

4.2. Определите вектор vector vv и инициализируйте его первыми десятью значениями факториала (1, 2*1, 3*2*1, 4*3*2*1 и т.д.).

4.3. Вызовите функцию f() с аргументом vv.

Контрольные вопросы

1. Что означает выражение “Покупатель, будь бдителен!”?

2. Какое копирование объектов класса используется по умолчанию?

3. Когда копирование объектов класса, используемое по умолчанию, является приемлемым, а когда нет?

4. Что такое конструктор копирования?

5. Что такое копирующее присваивание?

6. В чем разница между копирующим присваиванием и копирующей инициализацией?

7. Что такое поверхностное копирование? Что такое глубокое копирование?

8. Как копия объекта класса vector сравнивается со своим прототипом?

9. Перечислите пять основных операций над классом.

10. Что собой представляет конструктор с ключевым словом explicit? Когда его следует предпочесть конструктору по умолчанию?

11. Какие операции могут применяться к объекту класса неявно?

12. Что такое массив?

13. Как скопировать массив?

14. Как инициализировать массив?

15. Когда передача указателя на аргумент предпочтительнее передачи его по ссылке и почему?

16. Что такое строка в стиле С, или С-строка?

17. Что такое палиндром?

Термины

Упражнения

1. Напишите функцию char* strdup(const char*), копирующую строку в стиле языка C в свободную память, одновременно выделяя для нее место. Не используйте никаких стандартных функций. Не используйте индексирование, вместо него применяйте оператор разыменования *.

2. Напишите функцию char* findx(const char* s, const char* x), находящую первое вхождение строки x в стиле языка С в строку s. Не используйте никаких стандартных функций. Не используйте индексирование, вместо него применяйте оператор разыменования *.

3. Напишите функцию int strcmp(const char* s1, const char* s2), сравнивающую две строки в стиле языка С. Если строка s1 меньше строки s2 в лексикографическом смысле, функция должна возвращать отрицательное число, если строки совпадают — нуль, а если строка s1 больше строки s2 в лексикографическом стиле — положительное число. Не используйте никаких стандартных функций. Не используйте индексирование, вместо него применяйте оператор разыменования *.

4. Что случится, если передать функциям strdup(), findx() и strcmp() в качестве аргумента не строку в стиле С? Попробуйте! Сначала необходимо выяснить, как получить указатель char*, который не ссылается на массив символов, завершающийся нулем, а затем применить его (никогда не делайте этого в реальном — не экспериментальном — коде; это может вызвать катастрофу). Поэкспериментируйте с неправильными строками в стиле С, расположенными в свободной памяти или стеке. Если результаты покажутся разумными, отключите режим отладки. Переделайте и заново выполните все три функции так, чтобы они получали еще один аргумент — максимально допустимое количество символов в строке. Затем протестируйте функции с правильными и неправильными строками в стиле языка С.

5. Напишите функцию string cat_dot(const string& s1, const string& s2), выполняющую конкатенацию двух строк с точкой между ними. Например, cat_dot("Нильс", "Бор") вернет строку Нильс.Бор.

6. Модифицируйте функцию cat_dot() из предыдущего упражнения так, чтобы в качестве третьего аргумента она получала строку, используемую как разделитель (а не точку).

7. Напишите варианты функции cat_dot() из предыдущих упражнений, получающие в качестве аргументов строки в стиле языка C и возвращающие строку в стиле языка С, размещенную в свободной памяти. Не используйте никаких стандартных функций или типов. Протестируйте эти функции на нескольких строках. Убедитесь, что вся память, занятая вами с помощью оператора new, освобождается с помощью оператора delete. Сравните усилия, затраченные вами на выполнение упр. 5 и 6.

8. Перепишите все функции, приведенные в разделе 18.6, используя для сравнения обратную копию строки; например, введите строку "home", сгенерируйте строку "emoh" и сравните эти две строки, чтобы убедиться, что слово home — не палиндром.

9. Проанализируйте схему распределения памяти, описанную в разделе 17.4. Напишите программу, сообщающую, в каком порядке выделяется статическая память, стек и свободная память. В каком направлении растет стек: в сторону старших или младших адресов? Допустим, массив расположен в свободной памяти. Какой элемент будет иметь больший адрес — с большим индексом или с меньшим?

10. Проанализируйте решение задачи о палиндроме из раздела 18.6.2 на основе массива 10. Исправьте его так, чтобы можно было работать с длинными строками: 1) выдавайте сообщение, если введенная строка оказалась слишком длинной; 2) разрешите произвольно длинные строки. Прокомментируйте сложность обеих версий.

11. Разберитесь, что собой представляет список с пропусками (skip list), и реализуйте эту разновидность списка. Это не простое упражнение.

12. Реализуйте версию игры “Охота на Вампуса” (или просто “Вамп”). Это простая компьютерная (не графическая) игра, изобретенная Грегори Йобом (Gregory Yob). Цель этой игры — найти довольно смышленого монстра, прячущегося в темном пещерном лабиринте. Ваша задача — убить вампуса с помощью лука и стрел. Кроме вампуса, пещера таит еще две опасности: бездонные ямы и гигантские летучие мыши. Если вы входите в комнату с бездонной ямой, то игра для вас закончена. Если вы входите в комнату с летучей мышью, то она вас хватает и перебрасывает в другую комнату. Если же вы входите в комнату с вампусом или он входит в комнату, где находитесь вы, он вас съедает. Входя в комнату, вы должны получить предупреждение о грозящей опасности.

“Я чувствую запах вампуса” — значит, он в соседней комнате.

“Я чувствую ветерок” — значит, в соседней комнате яма.

“Я слышу летучую мышь” — значит, в соседней комнате живет летучая мышь.

Для вашего удобства комнаты пронумерованы. Каждая комната соединена туннелями с тремя другими. Когда вы входите в комнату, то получаете сообщение, например: “Вы в комнате номер 12; отсюда идут туннели в комнаты 1, 13 и 4; идти или стрелять?” Возможные ответы: m13 (“Переход в комнату номер 13”) и s13–4–3 (“Стрелять через комнаты с номерами 13, 4 и 3”). Стрела может пролететь через три комнаты. В начале игры у вас есть пять стрел. Загвоздка со стрельбой заключается в том, что вы можете разбудить вампуса и он войдет в комнату, соседнюю с той, где он спал, — она может оказаться вашей комнатой.

Вероятно, самой сложной частью этого упражнения является программирование пещеры и выбор комнат, связанных с другими комнатами. Возможно, вы захотите использовать датчик случайных чисел (например, функцию randint() из библиотеки std_lib_facilities.h), чтобы при разных запусках программы использовались разные пещеры и разное расположение летучих мышей и вампуса. Подсказка: используйте режим отладки для проверки состояния лабиринта.

Послесловие

Стандартный класс vector основан на средствах низкоуровневого управления памятью, таких как указатели и массивы. Его главное предназначение — помочь программисту избежать сложностей, сопряженных с этими средствами управления памятью. Разрабатывая любой класс, вы должны предусмотреть инициализацию, копирование и уничтожение его объектов.

Глава 19