С++ для начинающих - Учебное пособие

5. инструкции

Мельчайшей независимой частью С++ программы является инструкция. Она соответствует предложению естественного языка, но завершается точкой с запятой (;),  а  не  точкой.  Выражение  С++  (например,  ival + 5)  становится  простой инструкцией, если после него поставить точку с запятой. Составная инструкция – это последовательность простых, заключенная в фигурные скобки. По умолчанию инструкции выполняются в порядке записи. Как правило, последовательного выполнения  недостаточно  для  решения  реальных  задач.  Специальные управляющие конструкции позволяют менять порядок действий в зависимости от некоторых  условий  и повторять составную инструкцию определенное количество раз.  Инструкции   if,  if-else и  switch обеспечивают  условное  выполнение. Повторение обеспечивается инструкциями цикла  while, do-while и for.

5.1. Простые и составные инструкции

Простейшей формой является пустая инструкция. Вот как она выглядит:

; // пустая инструкция

Пустая  инструкция  используется  там,  где синтаксис  С++  требует  употребления инструкции,   а   логика   программы –   нет.   Например,   в   следующем   цикле   while, копирующем одну строку в другую, все необходимые действия производятся внутри круглых скобок (условной части инструкции). Однако согласно правилам синтаксиса С++ после while должна идти инструкция. Поскольку нам нечего поместить сюда (вся работа

while ( *string++ = inBuf++ )

уже выполнена), приходится оставить это место пустым:

; // пустая инструкция

Случайное  появление  лишней  пустой  инструкции  не  вызывает  ошибки  компиляции.

Например, такая строка

ival = dval + sval;; // правильно: лишняя пустая инструкция

состоит  из  двух  инструкций –  сложения  двух  величин  с  присваиванием  результата переменной ival и пустой.

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

// простые инструкции

int ival = 1024; // инструкция определения переменной

ival;     // выражение

ival + 5;           // еще одно выражение

Например:

 

ival = ival +5; // присваивание

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

if ( ival0 > ival1 ) {

// составная инструкция, состоящая

// из объявления и двух присваиваний

int temp = ivalO; ivalO = ival1; ival1 = temp;

заключенная в фигурные скобки:

}

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

Пустая составная инструкция эквивалентна пустой простой. Приведенный выше пример

while ( *string++ = *inBuf++ )

с пустой инструкцией можно переписать так:

{} // пустая инструкция

Составную инструкцию, содержащую определения переменных, часто называют блоком. Блок задает локальную область видимости в программе – идентификаторы, объявленные внутри блока (как temp в предыдущем примере), видны только в нем. (Блоки, области видимости и время жизни объектов рассматриваются в главе 8.)

5.2. Инструкции объявления

В С++ определение объекта,  например

int ival;

рассматривается как инструкция объявления (хотя в данном случае более правильно было бы  сказать  определения).   Ее  можно  использовать  в  любом  месте  программы,  где разрешено употреблять инструкции. В следующем примере объявления помечены комментарием //#n, где n – порядковый номер.

 

#include <fstream>

#include <string>

#include <vector>

int main()

{

string fileName; // #1

cout << "Введите имя файла: ";

cin >> fileName;

if ( fileName.empty() ) {

// странный случай

cerr << "Пустое имя файла. Завершение работы. ";

return -1;

}

ifstream inFile( fileName.c_str() ); // #2 if ( ! inFile ) {

cerr << "Невозможно открыть файл. ";

return -2;

}

string inBuf;        // #3 vector< string > text; // #4 while ( inFile >> inBuf ) {

for ( int ix = 0; ix < inBuf .size(); ++ix ) // #5

// можно обойтись без ch,

// но мы использовали его для иллюстрации

if (( char ch = inBuf[ix] )=='.'){ // #6

ch = '_';

inBuf[ix] = ch;

}

text.push_back( inBuf );

}

if ( text.empty() )

return 0;

// одна инструкция объявления,

// определяющая сразу два объекта

vector<string>::iterator iter = text.begin(), // #7 iend = text.end();

while ( iter != -iend ) {

cout << *iter << ' ';

++iter;

}

return 0;

}

Программа содержит семь инструкций объявления и восемь определений объектов. Объявления действуют локально; переменная объявляется непосредственно перед первым использованием объекта.

В 70-е годы философия программирования уделяла особое внимание тому, чтобы определения всех объектов находились в начале программы или блока, перед исполняемыми инструкциями. (В С, например, определение переменной не является инструкцией и обязано располагаться в начале блока.) В некотором смысле это была реакция   на   идиому   использования   переменных   без   предварительного   объявления, чреватую ошибками. Такую идиому поддерживал, например, FORTRAN.

 

Поскольку в С++ объявление является обычной инструкцией, ему разрешено появляться в любом месте программы, где допустимо употребление инструкции, что дает возможность использовать локальные объявления.

Необходимо ли это? Для встроенных типов данных применение локальных объявлений является скорее вопросом вкуса. Язык их поощряет , разрешая объявлять переменные внутри условных частей инструкций if, if-else, switch, while, for. Те программисты, которые любят этот стиль, верят, что таким образом делают свои программы более понятными.

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

конструкторы  всех  объектов  вызываются  перед  исполнением  первой инструкции блока. Применение локальных объявлений позволяет “размазать” расходы на инициализацию по всему блоку;

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

Инструкция объявления может состоять из одного или более определений. Например, в

// одна инструкция объявления,

// определяющая сразу два объекта

vector<string>::iterator iter = text.begin(),

нашей программе мы определяем два итератора вектора в одной инструкции:

lend = text.end();

vector<string>::iterator iter = text.begin();

Эквивалентная пара, определяющая по одному объекту, выглядит так:

vector<string>::iterator lend = text.end();

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

// то ли хотел определить программист?

идентификатором (используемые имена переменных наводят на второе предположение):

string *ptrl, ptr2;

 

string *ptr1;

Эквивалентная пара инструкций не позволит допустить такую ошибку:

string *ptr2;

В  наших  примерах  мы  обычно  группируем  определения  объектов  в  инструкции  по

int aCnt=0, eCnt=0, iCnt=0, oCnt=0, uCnt=0;

сходству употребления. Например, в следующей паре

int charCnt=0, wordCnt=0;

первая инструкция объявляет пять очень похожих по назначению объектов – счетчиков пяти  гласных  латинского  алфавита.  Счетчики  для  подсчета  символов  и  слов определяются во второй инструкции. Хотя такой подход нам кажется естественным и удобным, нет никаких причин считать его хоть чем-то лучше других.

Упражнение 5.1

Представьте себе, что вы являетесь руководителем программного проекта и хотите, чтобы применение инструкций объявления было унифицировано. Сформулируйте правила использования объявлений объектов для вашего проекта.

Упражнение 5.2

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

5.3. Инструкция if

Инструкция   if обеспечивает   выполнение   или   пропуск   инструкции   или   блока   в

if ( условие )

зависимости от условия. Ее синтаксис таков:

инструкция

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

if(a+b>c) { ... }

или инструкцией объявления с инициализацией:

if ( int ival = compute_value() ){...}

 

Область    видимости    объекта,    объявленного    в    условной    части,    ограничивается ассоциированной с if инструкцией или блоком. Например, такой код вызывает ошибку

if ( int ival = compute_value() ) {

// область видимости ival

// ограничена этим блоком

}

// ошибка: ival невидим

компиляции:

if ( ! ival ) ...

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

1.   Сравнить элемент с текущим значением минимума.

2.   Если элемент меньше, присвоить текущему минимуму значение элемента и сбросить счетчик в 1.

3.   Если элемент равен текущему минимуму, увеличить счетчик на 1.

4.   В противном случае ничего не делать.

5.   После проверки последнего элемента вернуть значение минимума и счетчика.

if ( minVal > ivec[ i ] )...// новое значение minVal

Необходимо использовать две инструкции if:

if ( minVal == ivec[ i ] )...// одинаковые значения

Довольно  часто  программист  забывает  использовать  фигурные  скобки,  если  нужно

if ( minVal > ivec[ i ] )

minVal = ivec[ i ];

выполнить несколько инструкций в зависимости от условия:

occurs = 1; // не относится к if!

Такую ошибку трудно увидеть, поскольку отступы в записи подразумевают, что и minVal=ivec[i],   и  occurs=1 входят  в  одну  инструкцию   if.  На  самом  же  деле инструкция

occurs = 1;

не является частью if и выполняется безусловно, всегда сбрасывая occurs в 1. Вот как должна быть составлена правильная if-инструкция (точное положение открывающей фигурной скобки является поводом для бесконечных споров):

 

if ( minVal > ivec[ i ] )

{

minVal = ivec[ i ];

occurs = 1;

}

if ( minVal == ivec [ i ] )

Вторая инструкция if выглядит так:

++occurs;

Заметим, что порядок следования инструкций  в этом примере крайне важен. Если мы будем  сравнивать  minVal именно  в  такой  последовательности,  наша  функция  всегда

if ( minVal > ivec[ i ] ) { minVal = ivec[ i ]; occurs = 1;

}

//          если minVal только что получила новое значение,

//          то occurs будет на единицу больше, чем нужно

if          ( minVal == ivec[ i ] )

будет ошибаться на 1:

++occurs;

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

if ( условие )

инструкция1

else

if-else, второй формой if-инструкции. Ее синтаксис выглядит таким образом:

инструкция2

инструкция1 выполняется,  если  условие  истинно,  иначе  переходим  к  инструкция2.

if ( minVal == ivec[ i ] )

++occurs;

else

if ( minVal > ivec[ i ] ) { minVal = ivec[ i ]; occurs = 1;

Например:

}

 

Здесь  инструкция2 сама  является  if-инструкцией.   Если  minVal меньше  ivec[i],

никаких действий не производится.

if ( minVal < ivec[ i ] )

{} // пустая инструкция

else

if ( minVal > ivec[ i ] ) {

minVal = ivec[ i ];

occurs = 1;

}

else // minVal == ivec[ i ]

В следующем примере выполняется одна из трех инструкций:

++occurs;

Составные инструкции if-else могут служить источником неоднозначного толкования,

если частей else больше, чем частей if. К какому из if отнести данную часть else?

if ( minVal <= ivec[ i ] )

if ( minVal == ivec[ i ] )

++occurs;

else {

minVal= ivec[ i ];

occurs= 1;

(Эту проблему иногда называют проблемой висячего else). Например:

}

Судя  по отступам,  программист  предполагает,  что else относится  к самому первому, внешнему if. Однако в С++ неоднозначность висячих else разрешается соотнесением их с  последним   встретившимся   if.  Таким  образом,   в  действительности   предыдущий

if ( minVal <= ivec[ i ] ) {

if ( minVal == ivec[ i ] )

++occurs;

else {

minVal            = ivec[ i ];

occurs = 1;

}

фрагмент означает следующее:

}

Одним из способов разрешения данной проблемы является заключение внутреннего if в фигурные скобки:

 

if ( minVal <= ivec[ i ] ) {

if ( minVal == ivec[ i ] )

++occurs;

}

else {

minVal= ivec[ i ];

occurs= 1;

}

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

Вот первый вариант функции min(). Второй аргумент функции будет возвращать количество   вхождений   минимального   значения   в   вектор.   Для  перебора   элементов массива используется цикл for. Но мы допустили ошибку в логике программы. Сможете

#include <vector>

int min( const vector<int> &ivec, int &occurs )

{

int minVal = 0;

occurs = 0;

int size = ivec.size();

for ( int ix = 0; ix < size; ++ix ) {

if ( minVal == ivec[ ix ] )

++occurs;

else

if ( minVal > ivec[ ix ] ) {

minVal = ivec[ ix ];

occurs = 1;

}

}

return minVal;

ли вы заметить ее?

}

Обычно  функция  возвращает  только  одно  значение.  Однако  согласно  нашей спецификации  в  точке  вызова  должно  быть  известно  не  только  само  минимальное значение, но и количество его вхождений в вектор. Для возврата второго значения мы использовали параметр типа ссылка. (Параметры-ссылки рассматриваются в разделе 7.3.) Любое   присваивание   значения   ссылке   occurs изменяет   значение   переменной,   на которую она ссылается:

 

int main()

{

int occur_cnt = 0;

vector< int > ivec;

// occur_cnt получает значение occurs

// из функции min()

int minval = min( ivec, occur_cnt );

// ...

}

Альтернативой  использованию  параметра-ссылки  является  применение  объекта  класса

pair, представленного в разделе 3.14. Функция min() могла бы возвращать два значения

// альтернативная реализация

// с помощью пары

#include <uti1ity>

#include <vector>

typedef pair<int,int> min_va1_pair;

min_va1_pair

min( const vector<int> &ivec )

{

int minVal = 0;

int occurs = 0;

// то же самое ...

return make_pair( minVal, occurs );

в одной паре:

}

К сожалению, и эта реализация содержит ошибку. Где же она? Правильно: мы инициализировали  minVal нулем, поэтому, если минимальный элемент вектора больше нуля,   наша   реализация   вернет   нулевое   значение   минимума   и   нулевое   значение количества вхождений.

Программу можно изменить, инициализировав minVal первым элементом вектора:

int minVal = ivec[0];

Теперь функция работает правильно. Однако в ней выполняются некоторые лишние действия, снижающие ее эффективность.

 

// исправленная версия min()

// оставляющая возможность для оптимизации ...

int minVal = ivec[0];

occurs = 0;

int        size = ivec.size();

for       ( int ix = 0; ix < size; ++ix )

{

if ( minVal == ivec[ ix ] )

++occurs;

// ...

Поскольку  ix инициализируется  нулем,  на  первой  итерации  цикла  значение  первого элемента сравнивается с самим собой. Можно инициализировать ix единицей и избежать ненужного выполнения первой итерации. Однако при оптимизации кода мы допустили другую   ошибку   (наверное,   стоило   все   оставить   как   было!).   Сможете   ли   вы   ее

// оптимизированная версия min(),

// к сожалению, содержащая ошибку...

int minVal = ivec[0];

occurs = 0;

int        size = ivec.size();

for       ( int ix = 1; ix < size; ++ix )

{

if ( minVal == ivec[ ix ] )

++occurs;

обнаружить?

// ...

Если   ivec[0] окажется  минимальным   элементом,   переменная   occurs не  получит

int minVal = ivec[0];

значения 1. Конечно, исправить это очень просто, но сначала надо найти ошибку:

occurs = 1;

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

Вот окончательная версия функции min() и программа main(), проверяющая ее работу:

 

#include <iostream>

#include <vector>

int min( const vector< int > &ivec, int &occurs )

{

int minVal = ivec[ 0 ];

occurs = 1;

int size = ivec.size();

for ( int ix = 1; ix < size; ++ix )

{

if ( minVal == ivec[ ix ] )

++occurs;

else

if ( minVal > ivec[ ix ] ){

minVal = ivec[ ix ];

occurs = 1;

}

}

return minVal;

}

int main()

{

int ia[] = { 9,1,7,1,4,8,1,3,7,2,6,1,5,1 };

vector<int> ivec( ia, ia+14 );

int occurs = 0;

int minVal = min( ivec, occurs );

cout << "Минимальное значение: " << minVal

<< " встречается: " << occurs << " раз. ";

return 0;

}

Результат работы программы:

Минимальное значение: 1 встречается: 5 раз.

В некоторых случаях вместо инструкции if-else можно использовать более краткое и

template <class valueType>

inline const valueType&

min( valueType &vall, valueType &va12 )

{

if ( vall < va12 )

return vall;

return va12;

выразительное условное выражение. Например, следующую реализацию функции min():

}

можно переписать так:

 

template <class valueType>

inline const valueType&

min( valueType &vall, valueType &va12 )

{

return ( vall < va12 ) ? vall : va12;

}

Длинные  цепочки   инструкций   if-else,   подобные  приведенной   ниже,  трудны  для

if ( ch == 'a' ||

ch == 'A' )

++aCnt;

else

if ( ch == 'e' ||

ch == 'E' )

++eCnt;

else

if ( ch == 'i' ||

ch == 'I' )

++iCnt;

else

if ( ch == 'o' ||

ch == '0' )

++oCnt;

else

if ( ch == 'u' ||

ch == 'U' )

восприятия и, таким образом, являются потенциальным источником ошибок.

++uCnt;

В качестве альтернативы  таким цепочкам С++ предоставляет инструкцию switch. Это тема следующего раздела.

Упражнение 5.3

Исправьте ошибки в примерах:

 

(a) if ( ivall != iva12 )

ivall = iva12

else

ivall = iva12 = 0;

(b) if ( ivat < minval ) minvat = ival; occurs = 1;

(c) if ( int ival = get_value())

cout << "ival = "

<< ival << endl;

if ( ! ival )

cout << "ival = 0 ";

(d) if ( ival = 0 )

ival = get_value();

(e) if ( iva1 == 0 )

else ival = 0;

Упражнение 5.4

Преобразуйте тип параметра occurs функции min(), сделав его не ссылкой, а простым объектом. Запустите программу. Как изменилось ее поведение?

5.4. Инструкция switch

Длинные цепочки инструкций if-else, наподобие приведенной в конце предыдущего раздела, трудны для восприятия и потому являются потенциальным источником ошибок. Модифицируя   такой  код,  легко  сопоставить,  например,  разные  else и  if. Альтернативный метод выбора одного их взаимоисключающих условий предлагает инструкция switch.

Для   иллюстрации   инструкции   switch рассмотрим   следующую   задачу.   Нам   надо подсчитать, сколько раз встречается каждая из гласных букв в указанном отрывке текста. (Общеизвестно,  что  буква  e –  наиболее  часто  встречающаяся  гласная  в  английском языке.) Вот алгоритм программы:

1.   Считывать по одному символу из входного потока, пока они не кончатся.

2.   Сравнить каждый символ с набором гласных.

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

4.   Напечатать результат.

Написанная программа была запущена, в качестве контрольного текста использовался раздел из оригинала данной книги. Результаты подтвердили, что буква e действительно самая частая:

aCnt: 394 eCnt: 721 iCnt: 461 oCnt: 349 uCnt: 186

 

Инструкция switch состоит из следующих частей:

ключевого  слова  switch,  за  которым  в  круглых  скобках  идет  выражение,

char ch;

while ( cm >> ch )

являющееся условием:

switch( ch )

набора  меток  case,  состоящих  из  ключевого  слова  case и  константного выражения,  с  которым  сравнивается  условие.  В  данном  случае  каждая  метка

case 'a': case 'e': case 'i': case 'o':

представляет одну из гласных латинского алфавита:

case 'u':

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

необязательной метки default, которая является аналогом части else инструкции  if-else.  Инструкции,  соответствующие  этой  метке,  выполняются, если   условие   не  отвечает   ни  одной   из  меток  case.   Например,   мы  можем подсчитать   суммарное   количество   встретившихся   символов,   не   являющихся

default: // любой символ, не являющийся гласной

гласными буквами:

++non_vowe1_cnt;

Константное  выражение  в  метке  case должно  принадлежать  к целому  типу,  поэтому

// неверные значения меток

case 3.14: // не целое

следующие строки ошибочны:

case ival: // не константа

Кроме того, две разные метки не могут иметь одинаковое значение.

Выражение  условия  в  инструкции  switch может  быть  сколь  угодно  сложным,  в  том числе включать вызовы функций. Результат вычисления условия сравнивается с метками case, пока не будет найдено равное значение или не выяснится, что такого значения нет. Если метка обнаружена, выполнение будет продолжено с первой инструкции после нее, если же нет, то с первой инструкции после метки default (при ее наличии) или после всей составной инструкции switch.

 

В отличие от if-else инструкции, следующие за найденной меткой, выполняются друг за  другом,  проходя  все  нижестоящие  метки  case и  метку  default.  Об  этом  часто забывают. Например, данная реализация нашей программы выполняется совершенно не

#include <iostream>

int main()

{

char ch;

int aCnt=0, eCnt=0, iCnt=0, oCnt=0, uCnt=0;

while ( cin >> ch )

// Внимание! неверная реализация!

switch ( ch ) {

case 'a':

++aCnt;

case 'e':

++eCnt;

case 'i':

++iCnt;

case 'o':

++oCnt;

case 'u':

++uCnt;

}

cout << "Встретилась a: " << aCnt << ' '

<< "Встретилась e: " << eCnt << ' '

<< "Встретилась i: " << iCnt << ' '

<< "Встретилась o: " << oCnt << ' '

<< "Встретилась u: " << uCnt << ' ';

так, как хотелось бы:

}

Если значение ch равно i, выполнение начинается с инструкции после case 'i' и iCnt возрастет   на   1.   Однако   следующие   ниже   инструкции,   ++oCnt и   ++uCnt,   также выполняются, увеличивая значения и этих переменных. Если же переменная ch равна a, изменятся все пять счетчиков.

Программист должен явно дать указание компьютеру прервать последовательное выполнение инструкций в определенном месте switch, вставив break. В абсолютном большинстве случаев за каждой метке case должен следовать соответствующий break.

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

 

switch ( ch ) {

case 'a':

++aCnt;

break;

case 'e':

++eCnt;

break;

case 'i':

++iCnt;

break;

case 'o':

++oCnt;

break;

case 'u':

++uCnt;

break;

}

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

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

int vowelCnt = 0;

// ...

switch ( ch )

{

// любой из символов a,e,1,o,u

// увеличит значение vowelCnt case 'a':

case 'e': case 'i': case 'o': case 'u':

++vowe1Cnt;

break;

сделать так:

}

Некоторые   программисты    подчеркивают    осознанность   своих   действий   тем,   что предпочитают в таком случае писать метки на одной строке:

 

switch ( ch )

{

// допустимый синтаксис

case 'a': case 'e':

case 'i': case 'o': case 'u':

++vowe1Cnt;

break;

}

В данной реализации все еще осталась одна проблема: как будут восприняты слова типа

UNIX

Наша  программа  не  понимает  заглавных  букв,  поэтому  заглавные  U и  I не  будут

switch ( ch ) {

case 'a': case 'A':

++aCnt;

break;

case 'e': case 'E':

++eCnt;

break;

case 'i': case 'I':

++iCnt;

break;

case 'o': case 'O':

++oCnt;

break;

case 'u': case 'U':

++uCnt;

break;

отнесены к гласным. Исправить ситуацию можно следующим образом:

}

Метка   default является   аналогом   части   else инструкции   if-else.   Инструкции, соответствующие  default,  выполняются,  если условие не отвечает  ни одной из меток case. Например, добавим к нашей программе подсчет суммарного количества согласных:

 

#include <iostream>

#include <ctype.h>

int main()

{

char ch;

int aCnt=0, eCnt=0, iCnt=0, oCnt=0, uCnt=0,

consonantCount=0;

while ( cin >> ch )

switch ( ch ) {

case 'a': case 'A':

++aCnt;

break;

case 'e': case 'E':

++eCnt;

break;

case 'i': case 'I':

++iCnt;

break;

case 'o': case 'O':

++oCnt;

break;

case 'u': case 'U':

++uCnt;

break;

default:

if ( isa1pha( ch ) )

++consonantCnt;

break;

}

cout << "Встретилась a: " << aCnt << ' '

<< "Встретилась e: " << eCnt << ' '

<< "Встретилась i: " << iCnt << ' '

<< "Встретилась o: " << oCnt << ' '

<< "Встретилась u: " << uCnt << ' '

<< "Встретилось согласных: " << consonantCnt

<< ' ';

}

isalpha() – функция стандартной библиотеки С; она возвращает true, если ее аргумент является  буквой.  isalpha() объявлена  в  заголовочном  файле  ctype.h.  (Функции  из ctype.h мы будем рассматривать в главе 6.)

Хотя  оператор  break функционально  не  нужен  после последней  метки  в инструкции switch, лучше его все-таки ставить. Причина проста: если мы впоследствии захотим добавить еще одну метку после case, то с большой вероятностью забудем вписать недостающий break.

Условная  часть  инструкции  switch может  содержать  объявление,  как  в  следующем примере:

switch( int ival = get_response() )

ival инициализируется  значением,  получаемым  от  get_response(),  и  это  значение сравнивается со значениями меток case. Переменная ival видна внутри блока switch, но не вне его.

 

Помещать же инструкцию объявления внутри тела блока switch не разрешается. Данный

case illegal_definition:

// ошибка: объявление не может

// употребляться в этом месте

string file_name = get_file_name();

// ...

фрагмент кода не будет пропущен компилятором:

break;

Если бы разрешалось объявлять переменную таким образом, то ее было бы видно во всем блоке  switch,  однако  инициализируется  она  только  в  том  случае,  если  выполнение прошло через данную метку case.

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

case ok:

{

// ок

string file_name = get_file_name();

// ...

она заведомо инициализирована. Вот как выглядит правильный текст:

break;

}

Упражнение 5.5

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

Упражнение 5.6

Модифицируйте  программу  из  данного  раздела  так,  чтобы  она  подсчитывала  также количество встретившихся двухсимвольных последовательностей ff, fl и fi.

Упражнение 5.7

Найдите и исправьте ошибки в следующих примерах:

switch ( ival ) { case 'a': aCnt++; case 'e': eCnt++; default: iouCnt++;

(a)

}

(b)

 

switch ( ival ) {

case 1:

int ix = get_value(); ivec[ ix ] = ival; break;

default:

ix = ivec.sizeQ-1;

ivec[ ix ] = ival;

}

switch ( ival ) {

case 1, 3, 5, 7, 9:

oddcnt++;

break;

case 2, 4, 6, 8, 10:

evencnt++;

break;

(c)

}

int iva1=512 jva1=1024, kva1=4096;

int bufsize;

// ...

switch( swt ) {

case ival:

bufsize = ival * sizeof( int );

break;

case jval:

bufsize = jval * sizeof( int );

break;

case kval:

bufsize = kval * sizeof( int );

break;

(d)

}

enum { illustrator = 1, photoshop, photostyler = 2 };

switch ( ival ) {

case illustrator:

--i11us_1icense;

break;

case photoshop:

--pshop_1icense;

break;

case photostyler:

--psty1er_license;

 

(e)

break;

 

}

5.5. Инструкция цикла for

Как мы видели, выполнение программы часто состоит в повторении последовательности инструкций  –  до тех  пор,  пока  некоторое условие  остается  истинным.  Например,  мы читаем и обрабатываем записи файла, пока не дойдем до его конца, перебираем элементы массива, пока индекс не станет равным размерности массива минус 1, и т.д. В С++ предусмотрено  три  инструкции  для  организации  циклов,  в  частности   for и  while, которые начинаются проверкой условия. Такая проверка означает, что цикл может закончиться без выполнения связанной с ним простой или составной инструкции. Третий тип  цикла, do while, гарантирует, что тело будет выполнено  как минимум один раз: условие цикла проверяется по его завершении. (В этом разделе мы детально рассмотрим цикл for; в разделе 5.6 разберем while, а в разделе 5.7 – do while.)

Цикл    for обычно    используется    для    обработки    структур    данных,    имеющих

#include <vector>

int main() {

int ia[ 10 ];

for ( int ix = 0; ix < 10; ++-ix )

ia[ ix ] = ix;

vector<int> ivec( ia, ia+10 );

vector<int>::iterator iter = ivec.begin() ;

for ( ; iter != ivec.end(); ++iter )

*iter *= 2;

return 0;

фиксированную длину, таких, как массив или вектор:

}

for (инструкция-инициализации; условие; выражение )

Синтаксис цикла for следующий:

инструкция

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

// index и iter определены в другом месте

for ( index =0; ...

for ( ; /* пустая инструкция */ ...

for ( iter = ivec.begin(); ... for ( int 1o = 0,hi = max; ...

инструкции-инициализации:

 

for ( char *ptr = getStr(); ...

условие служит  для  управления  циклом.  Пока  условие при  вычислении  дает  true, инструкция продолжает выполняться. Выполняемая в цикле инструкция может быть как простой,  так  и  составной.  Если  же  самое  первое  вычисление  условия  дает  false,

(... index < arraySize; ... ) (... iter != ivec.end(); ... ) (... *stl++ = *st2++; ... )

инструкция не выполняется ни разу. Правильные условия можно записать так:

(... char ch = getNextChar(); ... )

Выражение  вычисляется  после  выполнения  инструкции  на  каждой  итерации  цикла. Обычно  его  используют  для  модификации  переменной,  инициализированной  в инструкции-инициализации.   Если   самое   первое   вычисление   условия   дает   false,

( ... ...; ++-index )

( ... ...; ptr = ptr->next )

( ... ...; ++i, --j, ++cnt )

выражение не выполняется ни разу. Правильные выражения выглядят таким образом:

( ... ...; ) // пустое выражение

const int sz = 24; int ia[ sz ]; vector<int> ivec( sz );

for ( int ix = 0; ix < sz; ++ix ) {

ivec[ ix ] = ix;

ia[ ix ]= ix;

Для приведенного ниже цикла for

}

порядок вычислений будет следующим:

1.   инструкция-инициализации выполняется один раз перед началом цикла. В данном примере объявляется переменная ix, которая инициализируется значением 0.

2.   Вычисляется условие. Если оно равно true, выполняется составная инструкция тела цикла. В нашем примере, пока ix меньше sz, значение ix присваивается элементам ivec[ix] и  ia[ix].  Когда  значением  условия станет  false,  выполнение  цикла прекратится.   Если   самое   первое   вычисление   условия даст   false,   составная инструкция выполняться не будет.

3.  Вычисляется  выражение.  Как  правило,  его  используют  для  модификации переменной,  фигурирующей  в  инструкции-инициализации и  проверяемой  в условии. В нашем примере ix увеличивается на 1.

 

Эти три шага представляют собой полную итерацию цикла for. Теперь шаги 2 и 3 будут повторяться до тех пор, пока условие не станет равным false, т.е. ix окажется равным или большим sz.

В инструкции-инициализации можно определить несколько объектов, однако все они

for ( int ival = 0, *pi = &ia, &ri = val;

ival < size;

++iva1, ++pi, ++ri )

должны быть одного типа, так как инструкция объявления допускается только одна:

// ...

Объявление   объекта   в   условии   гораздо   труднее   правильно   использовать:   такое объявление должно хотя бы раз дать значение false, иначе выполнение цикла никогда

#include <iostream>

int main()

{

for ( int ix = 0;

bool done = ix == 10;

++ix )

cout << "ix: " << ix << endl;

не прекратится. Вот пример, хотя и несколько надуманный:

}

Видимость   всех   объектов,   определенных   внутри   круглых   скобок  инструкции   for,

ограничена   телом   цикла.   Например,   проверка   iter после  цикла  вызовет   ошибку

int main()

{

string word;

vector< string > text;

// ...

for ( vector< string >::iterator

iter = text.begin(),

iter_end = text.end();

iter != text.end(); ++iter )

{

if ( *iter == word )

break;

// ...

}

 

 

// ошибка: iter и iter_end невидимы

if ( iter != iter_end )

компиляции8:

Примечание [O.A.2]: Нумера ция сносок сбита, как и вся остальная. Необходима проверка.

 

 

8 До принятия  стандарта  языка С++ видимость  объектов,  определенных  внутри  круглых скобок for, простиралась на весь блок или функцию, содержащую данную инструкцию. Например, употребление двух циклов for внутри одного блока

 

// ...

Упражнение 5.8

(a)

for ( int *ptr = &ia, ix = 0;

ix < size && ptr != ia+size;

++ix, ++ptr )

// ...

Допущены ли ошибки в нижеследующих циклах for? Если да, то какие?

(b)

for ( ; ; ) {

if ( some_condition )

break;

// ...

}

{

// верно для стандарта С++

// в предыдущих версиях C++ - ошибка: ival определена дважды

for (int ival = 0; ival < size; ++iva1 ) // ... for (int ival = size-1; ival > 0; ival ) // ...

}

в ранних версиях языка вызывало ошибку: ival определена дважды. В стандарте С++ данный  текст  синтаксически  правилен,  так  как  каждый  экземпляр  ival является локальным  для своего блока.

 

(c)

for ( int ix = 0; ix < sz; ++ix )

// ...

if ( ix != sz )

// ...

(d)

int ix;

for ( ix < sz; ++ix )

// ...

(e)

for ( int ix = 0; ix < sz; ++ix, ++ sz )

// ...

Упражнение 5.9

Представьте,  что  вам  поручено  придумать  общий  стиль  использования  цикла  for в вашем  проекте.  Объясните  и  проиллюстрируйте  примерами  правила  использования каждой из трех частей цикла.

Упражнение 5.10

bool is_equa1( const vector<int> &vl,

Дано объявление функции:

const vector<int> &v2 );

Напишите тело функции, определяющей равенство двух векторов. Для векторов разной длины сравнивайте только то количество элементов, которое соответствует меньшему из двух. Например, векторы (0,1,1,2) и (0,1,1,2,3,5,8) считаются равными. Длину векторов можно узнать с помощью функций v1.size() и v2.size().

5.6. Инструкция while

while ( условие )

Синтаксис инструкции while следующий:

инструкция

Пока   значением      условия является       true,    инструкция выполняется    в            такой последовательности:

1.   Вычислить условие.

2.   Выполнить инструкцию, если условие истинно.

 

3.   Если самое первое вычисление условия дает false, инструкция не выполняется.

bool quit = false;

// ...

while ( ! quit ) {

// ...

quit = do_something();

}

string word;

Условием может быть любое выражение:

while ( cin >> word ){ ... }

while ( symbol *ptr = search( name )) {

// что-то сделать

или объявление с инициализацией:

}

В последнем случае ptr видим только в блоке, соответствующем инструкции while, как это было и для инструкций for и switch.

Вот   пример   цикла   while,   обходящего   множество   элементов,   адресуемых   двумя

int sumit( int *parray_begin, int *parray_end )

{

int sum = 0;

if ( ! parray_begin || ! parray_end )

return sum;

while ( parray_begin != parray_end )

// прибавить к sum

// и увеличить указатель

sum += *parray_begin++;

return sum;

}

int        ia[6] = { 0, 1, 2, 3, 4, 5 };

int        main()

{

int sum = sumit( &ia[0], &ia[ 6 ] );

// ...

указателями:

}

Для  того  чтобы  функция  sumit() выполнялась  правильно,  оба  указателя  должны адресовать  элементы  одного  и  того  же  массива  (parray_end может  указывать  на элемент,  следующий  за  последним).  В  противном  случае  sumit() будет  возвращать бессмысленную величину. Увы, С++ не гарантирует, что два указателя адресуют один и

 

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

Упражнение 5.11

(a)

string bufString, word;

while ( cin >> bufString >> word )

Какие ошибки допущены в следующих циклах while:

(b)

while ( vector<int>::iterator iter != ivec.end() )

// ...

(c)

while ( ptr = 0 )

ptr = find_a_value();

(d)

while ( bool status = find( word )) {

word = get_next_word();

if ( word.empty() )

break;

// ...

}

if ( ! status )

// ...

cout << "Слов не найдено ";

Упражнение 5.12

while обычно   применяется   для  циклов,   выполняющихся,   пока   некоторое  условие истинно, например, читать следующее значение, пока не будет достигнут конец файла. for обычно рассматривается  как пошаговый цикл: индекс пробегает по определенному диапазону  значений.  Напишите по одному  типичному  примеру  for и  while,  а  затем измените их, используя цикл другого типа. Если бы вам нужно было выбрать для постоянной работы только один из этих типов, какой бы вы выбрали? Почему?

Упражнение 5.13

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

 

5.8. Инструкция do while

Представим,   что  нам  надо  написать  программу,  переводящую  мили  в  километры.

int val;

bool more = true; // фиктивное значение, нужное для

// начала цикла

while ( more ) {

val = getValue();

val = convertValue(val);

printValue(val);

more = doMore();

Структура программы выглядит так:

}

Проблема  заключается  в  том,  что  условие  вычисляется  в  теле  цикла.  for и  while требуют, чтобы значение условия равнялось true до первого вхождения в цикл, иначе тело не выполнится ни разу. Это означает, что мы должны обеспечить такое условие до начала  работы цикла. Альтернативой  может служить  использование do while, гарантирующего выполнение тела цикла хотя бы один раз. Синтаксис цикла do while

do

инструкция

таков:

while ( условие );

инструкция выполняется до первой проверки условия. Если вычисление условия дает

false, цикл останавливается. Вот как выглядит предыдущий пример с использованием

do {

val = getValue();

val = convertValue(val);

printValue(val);

цикла do while:

} while doMore();

В отличие от остальных инструкций циклов, do while не разрешает объявлять объекты в

// ошибка: объявление переменной

// в условии не разрешается

do {

// ...

mumble( foo );

своей части условия. Мы не можем написать:

} while ( int foo = get_foo() ) // ошибка

 

потому что до условной части инструкции do while мы дойдем только после первого выполнения тела цикла.

Упражнение 5.14

Какие ошибки допущены в следующих циклах do while:

do

string rsp;

int vail, va12;

cout << "Введите два числа: ";

c-in >> vail >> va12;

cout << "Сумма " << vail

<< " и " << va12

<< " = " << vail + va12 << " "

<< "Продолжить? [да][нет] ";

cin >> rsp;

while ( rsp[0] != 'n' );

(b)

do {

// ...

} while ( int iva1 = get_response() );

(c)

 

do {

 

int ival = get_response();

if ( iva1 == some_value() )

break;

 

} while ( iva1 );

if ( !iva1 )

 

(a)

 

// ...

 

 

Упражнение 5.15

Напишите небольшую программу, которая запрашивает у пользователя две строки и печатает  результат  лексикографического  сравнения  этих строк (строка  считается меньшей, если идет раньше при сортировке по алфавиту). Пусть она повторяет эти действия, пока пользователь не даст команду закончить. Используйте тип string, сравнение строк и цикл do while.

5.8. Инструкция break

Инструкция   break останавливает   циклы   for,   while,  do while и  блока  switch. Выполнение   программы   продолжается   с   инструкции,   следующей   за   закрывающей фигурной скобкой цикла или блока. Например, данная функция ищет в массиве целых чисел определенное значение. Если это значение найдено, функция сообщает его индекс, в противном случае она возвращает -1. Вот как выглядит реализация функции:

 

// возвращается индекс элемента или  -1

int search( int *ia, int size, int value )

{

// проверка что ia != 0 и size > 0 ...

int loc = -1;

for ( int ix = 0; ix < size; ++ix ) {

if ( value == ia[ ix ] ) {

// нашли!

// запомним индекс и выйдем из цикла

1oc = ix;

break;

}

} // конец цикла

// сюда попадаем по break ... return 1oc;

}

В  этом  примере  break прекращает  выполнение  цикла  for и  передает  управление инструкции, следующей за этим циклом, – в нашем случае return. Заметим, что break выводит  из  блока,  относящегося  к  инструкции  for,  а  не  if,  хотя  является  частью составной инструкции, соответствующей if. Использование break внутри блока if, не

// ошибка: неверное использование break if ( ptr ) {

if ( *ptr == "quit" )

break;

// ...

входящего в цикл или в switch, является синтаксической ошибкой:

}

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

white ( cin >> inBuf )

{

switch( inBuf[ 0 ] ) {

case '-':

for ( int ix = 1; ix < inBuf.size(); ++ix ) {

if ( inBuf[ ix ] == ' ' )

break; // #1

// ...

// ...

}

break; // #2

case '+':

// ...

}

продолжает выполняться. Например:

}

 

Инструкция break, помеченная // #1, завершает выполнение цикла for внутри ветви case '-' блока  switch,  но  не  сам  switch.  Аналогично  break // #2 завершает выполнение блока switch, но не цикла while, в который тот входит.

5.9. Инструкция continue

Инструкция  continue завершает  текущую  итерацию  цикла  и  передает  управление  на вычисление условия, после чего цикл может продолжиться. В отличие от инструкции break,   завершающей   выполнение   всего   цикла,   инструкция   continue завершает выполнение  только  текущей  итерации.  Например,  следующий  фрагмент  программы читает из входного потока по одному слову. Если слово начинается с символа подчеркивания, оно обрабатывается, в противном случае программа переходит к новому

while ( cin >> inBuf ) {

if ( inBuf[0] '= '_' )

continue; // завершение итерации

// обработка слова ...

слову.

}

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

5.10. Инструкция goto

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

Синтаксис goto следующий:

goto метка;

где   метка –   определенный   пользователем   идентификатор.   Метка   ставится   перед инструкцией, на которую можно перейти с помощью goto, и должна заканчиваться двоеточием.   Нельзя   ставить   метку   непосредственно   перед   закрывающей   фигурной

end: ; // пустая инструкция

скобкой. Если же это необходимо, их следует разделить пустой инструкцией:

}

Переход  через  инструкцию  объявления  в  том  же блоке с помощью  goto невозможен.

Например, данная функция вызывает ошибку компиляции:

 

int oops_in_error() {

// mumble ...

goto end;

// ошибка: переход через объявление

int ix = 10;

// ... код, использующий ix end: ;

}

Правильная   реализация   функции   помещает   объявление   ix и   использующие   его

int oops_in_error() {

// mumble ...

goto end;

 

 

{

}

end: ;

// правильно: объявление во вложенном блоке

int ix = 10;

// ... код, использующий ix

 

 

инструкции во вложенный блок:

}

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

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

 

// переход назад через объявление не считается ошибкой. void

mumble ( int max_size )

{

begin:

int sz = get_size();

if ( sz <= 0 ) {

// выдать предупреждение ... goto end;

}

else

if ( sz > max_size )

// получить новое значение sz

goto begin;

{ // правильно: переход через целый блок

int ia = new int[ sz ];

doit( ia, sz ) ;

delete [] ia;

}

end:

;

}

Использование   инструкции   goto резко   критикуется   во   всех   современных   языках программирования. Ее применение приводит к тому, что ход выполнения программы становится трудно понять и,  следовательно, такую программу трудно модифицировать. В большинстве случаев goto можно заменить на инструкции if или циклы. Если вы все- таки решили использовать goto, не перескакивайте через большой фрагмент кода, чтобы можно было легко найти начало и конец вашего перехода.

5.11. Пример связанного списка

Мы завершали главы 3 и 4 примерами для введения читателя в механизм классов С++. В конце этого раздела мы покажем, как разработать класс, представляющий собой односвязный список. (В главе 6 мы рассмотрим двусвязный список, являющийся частью стандартной библиотеки.) Если вы в первый раз читаете эту книгу, то можете пропустить данный раздел и вернуться к нему после чтения главы 13. (Для усвоения этого материала нужно представлять себе механизм классов С++, конструкторы, деструкторы и т.д. Если вы плохо знаете классы, но все же хотите продолжить чтение данного раздела, мы рекомендуем прочесть пункты 2.3 и 3.15.

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

Какие операции должен поддерживать список? Добавление (insert), удаление (remove) и поиск  (find)  определенных  элементов.  Кроме того,  можно запрашивать  размер  списка (size), распечатывать его содержимое (display), проверять равенство двух списков. Мы покажем также, как инвертировать (reverse) и сцеплять (concatenate) списки.

Простейшая  реализация  операции  size() перебирает  все  элементы,  подсчитывая  их количество. Более сложная реализация сохраняет размер как член данных; она намного

 

эффективнее, однако требует некоторого усложнения операций insert() и remove() для поддержки размера в актуальном состоянии.

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

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

Операция  insert() в  общем  случае принимает  два  параметра:  указатель  на  один  из элементов списка и новое значение, которое вставляется после указанного элемента. Например, для списка

1 1 2 3 8

вызов

mylist.insert (pointer_to_3, 5);

изменит наш список так:

1 1 2 3 5 8

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

pointer_to_3 = mylist.find( 3 );

find() принимает  в  качестве  параметра  значение  из  списка.  Если  элемент  с  таким значением найден, то возвращается его адрес, иначе find() возвращает 0.

Может быть два специальных случая вставки элемента: в начало и в конец списка. Для

insert_front( value );

этого требуется только задание значения:

1nsert_end( value );

Предусмотрим следующие операции удаления элемента с заданным значением, первого

remove( value );

remove_front();

элемента и всех элементов списка:

remove_all();

 

Функция  display() распечатывает  размер  списка  и все его элементы.  Пустой список можно представить в виде:

(0)( )

а список из семи элементов как:

(7) ( 0 1 1 2 3 5 8 )

reverse() меняет порядок элементов на противоположный. После вызова

mylist.reverse();

предыдущий список выглядит таким образом:

(7) ( 8 5 3 2 1 1 0 )

Конкатенация добавляет элементы второго списка в конец первого. Например, для двух списков:

(4)( 0 1 1 2 ) // listl

(4)( 2 3 5 8 ) // list2

операция

listl.concat( list2 );

превращает list1 в

(8) ( 0 1 1 2 2 3 5 8 )

Чтобы   сделать   из   этого  списка   последовательность   чисел  Фибоначчи,   мы  можем воспользоваться функцией remove():

listl.remove( 2 );

Мы определили поведение нашего списка, теперь можно приступать к реализации. Пусть список   (list)   и  элемент  списка  (list_item)  будут  представлены   двумя  разными классами. (Ограничимся теми элементами, которые способны хранить только целые значения. Отсюда названия наших классов – ilist и ilist_item.)

Наш список содержит следующие члены: _at_front – адрес первого элемента, _at_end – адрес последнего  элемента и _size – количество элементов. При определении объекта типа  ilist все  три  члена  должны  быть  инициализированы  0.  Это  обеспечивается конструктором по умолчанию:

 

class ilist_item;

class ilist {

public:

// конструктор по умолчанию

ilist() : _at_front( 0 ),

_at_end( 0 ), _size( 0 ) {}

// ... private:

ilist_item *_at_front; ilist_item *_at_end; int _size;

};

Теперь мы можем определять объекты типа ilist, например:

ilist mylist;

но пока ничего больше. Добавим возможность запрашивать размер списка. Включим объявление функции size() в открытый  интерфейс  списка и определим эту функцию так:

inline int ilist::size() { return _size; }

Теперь мы можем использовать:

int size = mylist.size();

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

class ilist {

public:

// определения не показаны

ilist();

int size();

// ... private:

// запрещаем инициализацию

// и присваивание одного списка другому

ilist( const ilist& );

ilist& operator=( const ilist& );

// данные-члены без изменения

реализации. Теперь определение класса ilist выглядит таким образом:

};

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

main() не может обращаться к закрытым членам класса ilist:

 

int main()

{

ilist yourlist( mylist ); // ошибка

mylist = mylist;           // ошибка

}

Следующий шаг – вставка элемента, для представления которого мы выбрали отдельный

class ilist_item {

public:

// ...

private:

int        _value;

ilist_item *_next;

класс:

};

Член _value хранит значение, а _next – адрес следующего элемента или 0.

Конструктор   ilist_item требует  задания   значения  и  необязательного  параметра – адреса  существующего  объекта  ilist_item.  Если  этот  адрес  задан,  то  создаваемый объект ilist_item будет помещен в список после указанного. Например, для списка

0 1 1 2 5

вызов конструктора

ilist_item ( 3, pointer_to_2 );

модифицирует последовательность так:

0 1 1 2 3 5

Вот реализация ilist_item. (Напомним, что второй параметр конструктора является необязательным. Если пользователь не задал второй аргумент при вызове конструктора, по умолчанию употребляется 0. Значение по умолчанию указывается в объявлении функции, а не в ее определении; это поясняется в главе 7.)

 

class ilist_item {

public:

ilist_item( int value, ilist_-item *item_to_link_to = 0 );

// ...

};

inline ilist_item::

ilist_item( int value, ilist_item *item )

: _value( value )

{

if ( item )

_next = 0;

else {

_next = item->_next;

item->_next = this;

}

Операция  insert() в  общем  случае  работает  с  двумя  параметрами –  значением  и адресом   элемента,   после   которого   производится   вставка.   Наш   первый   вариант

inline void ilist::

insert( ilist_item *ptr, int value )

{

new ilist_item( value, ptr );

++_size;

реализации имеет два недочета. Сможете ли вы их найти?

}

Одна из проблем заключается в том, что указатель не проверяется на нулевое значение. Мы обязаны распознать и обработать такую ситуацию, иначе это приведет к краху программы   во  время  исполнения.   Как  реагировать   на  нулевой  указатель?  Можно аварийно закончить выполнение, вызвав стандартную функцию abort(), объявленную в

#include <cstdlib>

// ...

if ( ! ptr )

заголовочном файле cstdlib:

abort();

Кроме того, можно использовать  макрос assert().  Это также приведет к аварийному

#include <cassert>

// ...

завершению, но с выводом диагностического сообщения:

assert( ptr != 0 );

Третья возможность – возбудить исключение:

 

if ( ! ptr )

throw "Panic: ilist::insert(): ptr == O";

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

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

Мы же поступим совсем другим способом: рассмотрим передачу нулевого указателя как

if ( ! ptr )

запрос на вставку элемента перед первым в списке:

insert_front( value );

Второй изъян в нашей версии можно назвать философским. Мы реализовали size() и

_size как  пробный   вариант,   который   может   впоследствии   измениться.   Если   мы преобразуем  функции  size() таким  образом,  что  она  будет  просто  пересчитывать элементы списка, член _size перестанет быть нужным. Написав:

++_size;

мы тесно связали  реализацию  insert() с текущей конструкцией  алгоритма пересчета элементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию, как и insert_front(), insert_end() и все операции удаления из списка. Вместо того чтобы  распространять  детали  текущей  реализации  на  разные  функции  класса,  лучше

inline void ilist::bump_up_size()         { ++_size; }

инкапсулировать их в паре:

inline void ilist::bump_down_size() { --_size; }

Поскольку мы объявили эти функции встроенными, эффективность не пострадала. Вот

inline void ilist::

insert( ilist_item *ptr, int value )

if (       !ptr )

insert_front( value );

else      {

bump_up_size();

new ilist_item( value, ptr );

}

окончательный вариант insert():

}

 

Реализация функций insert_front() и insert_end() достаточно очевидна. В каждой

inline void ilist::

insert_front( int value )

{

ilist_item *ptr = new ilist_item( value );

if ( !_at_front )

_at_front = _at_end = ptr;

else {

ptr->next( _at_front );

_at_front = ptr;

}

bump_up_size();

}

inl-ine void ilist::

insert_end( int value )

{

if ( !_at_end )

_at_end = _at_front = new ilist_item( value );

else _at_end = new ilist_item(            value, _at_end );

bump_up_s-ize();

из них мы должны предусмотреть случай, когда список пуст.

}

find() ищет   значение  в   списке.   Если   элемент   с  указанным   значением   найден,

ilist_item*

ilist::

find( int value )

{

ilist_item *ptr = _at_front;

while ( ptr )

{

if ( ptr->value() == value )

break;

ptr = ptr->next();

}

return ptr;

возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так:

}

ilist_item *ptr = mylist.find( 8 );

Функцию find() можно использовать следующим образом:

mylist.insert( ptr, some_value );

или в более компактной записи:

 

mylist.insert( mylist.find( 8 ), some_value );

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

// не работает правильно!

for ( ilist_item *iter = _at_front; // начнем с первого

iter != _at_end;           // пока не последний

++iter )            // возьмем следующий

cout << iter->value() << ' ';

// теперь напечатаем последний

реализации ошибка?

cout << iter->value();

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

Инкремент итератора

++iter;

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

iter = iter->_next;

Мы  инкапсулировали  доступ  к  членам  ilist_item набором  встраиваемых  функций.

class ilist_item {

public:

ilist_item( int value, ilist_item *item_to_link_to = 0 );

int        value() { return _value; }

iilst_item* next() { return _next; }

void next( ilist_item *link ) { _next = link; }

void value( int new_value ) { _value = new_value; }

private:

int _value;

ilist_item *_next;

Определение класса ilist_item теперь выглядит так:

};

Вот  определение  функции  display(),  использующее  последнюю  реализацию  класса

ilist_item:

 

#include <iostream>

class ilist {

public:

void display( ostream &os = cout );

// ...

};

void ilist::

display( ostream &os )

{

os << " ( " << _size << " )(    ";

ilist_item *ptr = _at_front;

while ( ptr ) {

os << ptr->value() << " ";

ptr = ptr->next();

}

os << ") ";

}

Тестовую   программу  для  нашего  класса   ilist в  его  текущей  реализации   можно представить таким образом:

 

#include <iostream>

#include "ilist.h"

int main()

{

ilist mylist;

for ( int ix = 0; ix < 10; ++ix ) { mylist.insert_front( ix ); mylist.insert_end( ix );

}

cout <<

"Ok: после insert_front() и insert_end() ";

mylist.display();

ilist_item *it = mylist.find( 8 );

cout << " "

<< "Ищем значение 8: нашли?"

<< ( it ? " да! " : " нет! " );

mylist.insert( it, 1024 );

cout << " " <<

"Вставка элемента 1024 после 8 ";

mylist.display();

int elem_cnt = mylist.remove( 8 );

cout << " "

<< "Удалено " << elem_cnt

<< " элемент(ов) со значением 8 ";

mylist.display();

cout << " " << "Удален первый элемент ";

mylist.remove_front(); mylist.display();

cout << " " << "Удалены все элементы ";

mylist.remove_all(); mylist.display();

}

Результат работы программы:

Ok: после insert_front() и insert_end()

(20)( 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )

Ищем значение 8: нашли? да!

Вставка элемента 1024 после 8

( 21 )( 9 8 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )

Удалено 2 элемент(ов) со значением 8

( 19 )( 9 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )

Удален первый элемент

( 18 )( 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )

Удалены все элементы

( 0 )( )

 

Помимо вставки  элементов,  необходима  возможность  их удаления. Мы реализуем три

void remove_front();

void remove_all ();

таких операции:

int remove( int value );

inline void i1ist:: remove_front()

{

if ( _at_front ) {

ilist_item *ptr = _at_front;

_at_front = _at_front->next();

bump_down_size() ;

delete ptr;

}

Вот как выглядит реализация remove_front():

}

remove_all() вызывает  remove_front() до  тех  пор,  пока  все  элементы  не  будут

void ilist::

remove_all()

{

while ( _at_front )

remove_front();

_size = 0;

_at_front = _at_end = 0;

удалены:

}

Общая  функция  remove() также  использует  remove_front() для  обработки специального случая, когда удаляемый элемент (элементы) находится в начале списка. Для удаления из середины списка используется итерация. У элемента, предшествующего удаляемому, необходимо модифицировать указатель _next. Вот реализация функции:

 

int ilist::

remove( int value )

{

ilist_item *plist = _at_front;

int elem_cnt = 0;

while ( plist && plist->value() == value )

{

plist = plist->next();

remove_front();

++elem_cnt;

}

if ( ! plist )

return elem_cnt;

ilist_item *prev = plist;

plist = plist->next();

while ( plist ) {

if ( plist->value() == value ) {

prev->next( plist->next() );

delete plist;

++elem_cnt;

bump_down_size();

plist = prev->next();

if ( ! plist ) {

_at_end = prev;

return elem_cnt;

}

}

else {

prev = plist;

plist = plist->next();

}

return elem_cnt;

}

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

#include <iostream>

#include "ilist.h"

int main()

С++{ для начинающих         230

ilist mylist;

cout << " ----------------------------------------------- "

<< "тест #1: - элементы в конце "

<< "----------------------------------------------- ";

mylist.insert_front( 1 ); mylist.insert_front( 1 );

mylist.insert_front( 1 );

my1ist.insert_front( 2 ); mylist.insert_front( 3 );

my1ist.insert_front( 4 );

mylist.display();

int elem_cnt = mylist.remove( 1 );

cout << " " << "Удалено " << elem_cnt

<< " элемент(ов) со значением 1 ";

mylist.display();

mylist.remove_all();

cout << " ----------------------------------------------- "

<< "тест #2: - элементы в начале "

<< "----------------------------------------------- ";

mylist.insert_front( 1 ); mylist.insert_front( 1 );

mylist.insert_front( 1 );

mylist.display();

elem_cnt = mylist.remove( 1 );

cout << " " << "Удалено " << elem_cnt

<< " элемент(ов) со значением 1 ";

mylist.display();

mylist.remove_all () ;

cout << " ----------------------------------------------- "

<< "тест #3: - элементов нет в списке "

<< "----------------------------------------------- ";

mylist.insert_front( 0 ); mylist.insert_front( 2 );

mylist.insert_front( 4 );

mylist.display();

elem_cnt = mylist.remove( 1 );

cout << " " << "Удалено " << elem_cnt

<< " элемент(ов) со значением 1 ";

mylist.display();

mylist.remove_all () ;

cout << " ----------------------------------------------- "

<< "тест #4: - элементы в конце и в начале "

<< "----------------------------------------------- ";

my1ist.insert_front( 1 ); mylist.insert_front( 1 );

my1ist.insert_front( 1 );

my1ist.insert_front( 0 ); mylist.insert_front( 2 );

my1ist.insert_front( 4 );

mylist.insert_front( 1 ); my1ist.insert_front( 1 );

mylist.insert_front( 1 );

mylist.display() ;

elem_cnt = mylist.remove( 1 );

cout << " " << "Удалено " << elem_cnt

<< " элемент(ов) со значением 1 ";

 

}

Результат работы программы:

-----------------------------------------------

тест #1: - элементы в конце

-----------------------------------------------

( 6 )( 4 3 2 1 1 1 )

Удалено 3 элемент(ов) со значением 1 ( 3 )( 4 3 2 )

-----------------------------------------------

тест #2: - элементы в начале

-----------------------------------------------

( 3 )( 1 1 1 )

Удалено 3 элемент(ов) со значением 1 ( 0 )( )

-----------------------------------------------

тест #3: - элементов нет в списке

----------------------------------------------- ( 3 )( 4 2 0 )

Удалено 0 элемент(ов) со значением 1 ( 3 )( 4 2 0 )

-----------------------------------------------

тест #4: - элементы в конце и в начале

-----------------------------------------------

(9 )( 1 1 1 4 2 0 1 1 1 )

Удалено 6 элемент(ов) со значением 1 ( 3 )( 4 2 0 )

Последние две операции, которые мы хотим реализовать, – конкатенация двух списков (добавление одного списка в конец другого) и инверсия (изменение порядка элементов на противоположный).  Первый  вариант  concat() содержит  ошибку.  Сможете  ли  вы  ее

void ilist::concat( const ilist &i1 ) {

if ( ! _at_end )

_at_front = i1._at_front;

else _at_end->next( i1._at_front );

_at_end = i1._at_end;

найти?

}

Проблема  состоит  в  том,  что теперь  два  объекта  ilist содержат  последовательность одних и тех же элементов. Изменение одного из списков, например вызов операций insert() и remove(), отражается на другом, приводя его в рассогласованное состояние. Простейший способ обойти эту проблему – скопировать каждый элемент второго списка. Сделаем это при помощи функции insert_end():

 

void ilist::

concat( const ilist &i1 )

{

i1ist_item *ptr = i1._at_front;

while ( ptr ) {

insert_end( ptr->value() );

ptr = ptr->next();

}

}

void ilist:: reverse()

{

ilist_item *ptr = _at_front;

ilist_item *prev = 0;

_at_front = _at_end;

_at_end = ptr;

while ( ptr != _at_front )

{

ilist_item *tmp = ptr->next();

ptr->next( prev );

prev = ptr;

ptr = tmp;

}

_at_front->next( prev );

Вот реализация функции reverse():

}

Тестовая программа для проверки этих операций выглядит так:

 

#include <iostream>

#include "ilist.h"

int main()

{

ilist mylist;

for ( int ix = 0; ix < 10; ++ix )

{ mylist.insert_front( ix ); }

mylist.display();

cout << " " << "инвертирование списка ";

mylist.reverse(); mylist.display();

ilist mylist_too;

mylist_too.insert_end(0); mylist_too.insert_end(1);

mylist_too.insert_end(1); mylist_too.insert_end(2);

mylist_too.insert_end(3); mylist_too.insert_end(5);

cout << " " << "mylist_too: ";

mylist_too.display();

mylist.concat( mylist_too );

cout << " "

<< "mylist после concat с mylist_too: ";

mylist.disp1ay();

}

Результат работы программы:

( 10 ) ( 9 8 7 6 5 4 3 2 1 0 )

инвертирование списка

( 10 ) ( 0 1 2 3 4 5 6 7 8 9 )

mylist_too:

( 6 )( 0 1 1 2 3 5 )

mylist после concat с mylist_too:

( 16 ) ( 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 )

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

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

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

 

запретили его использование. Лучше уж полностью лишить пользователя какой-либо операции,  чем  допустить  возможные  ошибки.  (В  разделе  14.5  объясняется,  почему действия копирующего конструктора по умолчанию в подобных случаях неверны.) Вот

ilist::ilist( const ilist &rhs )

{

ilist_item *pt = rhs._at_front;

while ( pt ) {

insert_end( pt->value() );

pt = pt->next();

}

реализация конструктора, использующая функцию insert_end():

}

Оператор  присваивания  должен  сначала  вызвать  remove_all(),  а  затем  с  помощью

insert_end() вставить   все   элементы   второго   списка.   Поскольку   эта   операция

void ilist::insert_all ( const ilist &rhs )

{

ilist_item *pt = rhs._at_front;

while ( pt ) {

insert_end( pt->value() );

pt = pt->next();

}

повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all():

}

inline ilist::ilist( const ilist &rhs )

: _at_front( 0 ), _at_end( 0 )

{ insert_all ( rhs ); }

inline ilist&

ilist::operator=( const ilist &rhs ) {

remove_all(); insert_all( rhs ); return *this;

после чего копирующий конструктор и оператор присваивания можно реализовать так:

}

Теперь  осталось  обеспечить  пользователя  возможностью  путешествовать  по  списку,

например с помощью доступа к члену _at_front:

ilist_item *ilist::front() { return _at_front(); }

После этого можно применить ilist_item::next(), как мы делали в функциях-членах:

 

ilist_item *pt = mylist.front();

while ( pt ) {

do_something( pt->value() );

pt = pt->next();

}

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

for ( ilist_item *iter = mylist.init_iter();

iter;

iter = mylist.next_iter() )

цикла такого вида:

do_something( iter->value() );

(В разделе 2.8 мы уже касались понятия итератора. В главах 6 и 12 будут рассмотрены итераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенных алгоритмов.)

Наш итератор представляет собой несколько больше, чем просто указатель. Он должен уметь запоминать текущий элемент, возвращать следующий и определять, когда все элементы кончились. По умолчанию итератор инициализируется значением _at_front, однако пользователь может задать в качестве начального любой элемент списка. next_iter() возвращает  следующий  элемент  или 0,  если элементов  больше нет.  Для

class ilist {

public:

// ...

init_iter( ilist_item *it = 0 );

private:

//...

ilist_item *_current;

реализации пришлось ввести дополнительный член класса:

};

inline ilist_item*

ilist::init_iter( i1ist_item *it )

{

return _current = it ? it : _at_front;

init_iter() выглядит так:

}

next_iter() перемещает указатель _current на следующий элемент и возвращает его адрес, если элементы не кончились. В противном случае он возвращает 0 и устанавливает

_current в 0. Его реализацию можно представить следующим образом:

 

inline ilist_item*

ilist::

next_iter()

{

ilist_item *next = _current

? _current = _current->next()

: _current;

return next;

}

Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Их преодолевают модификацией кода функций remove() и remove_front(): они должны проверять  значение  _current.  Если  он  указывает  на  удаляемый  элемент,  функции изменят  его  так,  чтобы  он  адресовал  следующий  элемент  либо  был  равен  0,  когда удаляемый элемент – последний в списке или список стал пустым. Модифицированная

inline void ilist::remove_front()

{

if ( _at_front ) {

ilist_item *ptr = _at_front;

_at_front = _at_front->next();

// _current не должен указывать на удаленный элемент

if ( _current == ptr )

_current = _at_front;

bump_down_size();

delete ptr;

}

remove_front() выглядит так:

}

while ( plist ) {

if ( plist->value() == value )

{

prev->next( plist->next() );

if ( _current == plist )

Вот модифицированный фрагмент кода remove():

_current = prev->next();

Что произойдет, если элемент будет вставлен перед тем, на который указывает _current? Значение  _current не изменяется.  Пользователь  должен  начать  проход  по списку  с помощью вызова init_iter(), чтобы новый элемент попал в число перебираемых. При инициализации списка другим и при присваивании значение _current не копируется, а сбрасывается в 0.

Тестовая программа для проверки работы копирующего конструктора и оператора присваивания выглядит так::

 

#include <iostream>

#include "ilist.h"

int main()

{

ilist mylist;

for ( int ix = 0; ix < 10; ++ix ) { mylist.insert_front( ix ); mylist.insert_end( ix );

}

cout << " " << "Применение init_iter() и next_iter() "

<< "для обхода всех элементов списка: ";

ilist_item *iter;

for ( iter = mylist.init_iter();

iter; iter = mylist.next_iter() )

cout << iter->value() << " ";

cout << " " << "Применение копирующего конструктора ";

ilist mylist2( mylist );

mylist.remove_all();

for ( iter = mylist2.init_iter();

iter; iter = mylist2.next_iter() )

cout << iter->value() << " ";

cout << " " << "Применение копирующего оператора присваивания ";

mylist = mylist2;

for ( iter = mylist.init_iter();

iter; iter = mylist.next_iter() )

cout << iter->value() << " ";

cout << " ";

}

Результат  работы программы:

Применение init_iter() и next_iter() для обхода всех элементов списка:

9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

Применение копирующего конструктора

9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

Применение копирующего оператора присваивания

9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

5.11.1. Обобщенный список

Наш класс ilist имеет серьезный недостаток: он может хранить элементы только целого типа.  Если  бы  он  мог  содержать  элементы  любого  типа –  как  встроенного,  так  и определенного  пользователем, –  то  его  область  применения  была  бы  гораздо  шире. Модифицировать ilist для поддержки произвольных типов данных позволяет механизм шаблонов (см. главу 16).

 

При  использовании  шаблона  вместо  параметра  подставляется  реальный  тип  данных.

Например:

list< string > slist;

создает экземпляр списка, способного содержать объекты типа string, а

list< int > ilist;

создает список, в точности повторяющий наш ilist. С помощью шаблона класса можно обеспечить  поддержку  произвольных  типов  данных  одним  экземпляром  кода. Рассмотрим последовательность действий, уделив особое внимание классу list_item.

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

template <class elemType>

перед которым стоит ключевое слово class или typename.  Например:

class list_item;

Эта  инструкция  объявляет  list_item шаблоном  класса  с  единственным  параметром-

template <typename elemType>

типом. Следующее объявление эквивалентно предыдущему:

class list_item;

Ключевые  слова  class и  typename имеют  одинаковое  значение,  можно использовать любое из них.  Более удобное для запоминания typename появилось  в стандарте С++ сравнительно недавно и поддерживается еще не всеми компиляторами. Поскольку наши тексты были написаны до появления этого ключевого слова, в них употребляется class. Шаблон класса list_item выглядит так:

 

template <class elemType>

class list_item {

public:

list_item( elemType value, list_item *item = 0 )

: _value( value ) {

if ( !item )

_next = 0;

else {

_next = item->_next;

item->_next = this;

}

}

elemType value() { return _value; }

list_item* next() { return _next; }

void next( list_item *link ) { _next = link; }

void value( elemType new_value ) { _value = new_value; }

private:

elemType         _value;

list_item *_next;

};

Все  упоминания  типа  int в  определении  класса  ilist_item заменены  на  параметр

elemType. Когда мы пишем:

list_item<doub1e> *ptr = new list_item<doub1e>( 3.14 );

компилятор  подставляет  double вместо  elemType и  создает  экземпляр  list_item,

поддерживающий данный тип.

Аналогичным образом модифицируем класс ilist в шаблон класса list:

 

template <class elemType>

class list {

public:

list()

: _at_front( 0 ), _at_end( 0 ), _current( 0 ),

_size( 0 ) {}

1ist( const list& );

list& operator=( const list& );

~list() { remove_all(); }

void insert ( list_item<elemType> *ptr, elemType value );

void insert_end( elemType value );

void insert_front( elemType value );

void insert_all( const list &rhs );

int remove( elemType value );

void remove_front();

void remove_all();

list_item<elemType> *find( elemType value );

list_item<elemType> *next_iter();

list_item<elemType>* init_iter( list_item<elemType> *it );

void disp1ay( ostream &os = cout );

void concat( const list& );

void reverse ();

int size() { return _size; }

private:

void bump_up_size()  { ++_size; }

void bump_down_size() { --_size; }

list_item<elemType> *_at_front;

1ist_item<elemType> *_at_end; list_item<elemType> *_current; int _size;

};

Объекты шаблона класса list используются точно так же, как и объекты класса ilist. Основное преимущество шаблона в том, что он обеспечивает поддержку произвольных типов данных с помощью единственного определения.

(Шаблоны являются важной составной частью концепции программирования на С++. В главе  6  мы  рассмотрим  набор  классов  контейнерных  типов,  предоставляемых стандартной библиотекой С++. Неудивительно, что она содержит шаблон класса, реализующего операции со списками, равно как и шаблон класса, поддерживающего векторы; мы рассматривали их в главах 2 и 3.)

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

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

 

употреблять эти имена в программах. Стандартная библиотека С++ помещает свои имена

namespace Primer_Third_Edition

{

template <typename elemType>

class list_item{ ... };

template <typename elemType>

class list{ ... };

// ...

в пространство std. Мы тоже поместим наш код в собственное пространство:

}

Для использования  такого класса в пользовательской  программе необходимо  написать

// наш заголовочный файл

#include "list.h"

// сделаем наши определения видимыми в программе

using namespace Primer_Third_Edition;

// теперь можно использовать наш класс list list< int > ilist;

следующее:

// ...

(Пространства имен описываются в разделах 8.5 и 8.6.)

Упражнение 5.16

Мы не определили деструктор для ilist_item, хотя класс содержит указатель на динамическую  область  памяти.  Причина  заключается  в  том,  что  класс  не  выделяет память для объекта, адресуемого указателем _next, и, следовательно, не несет ответственности   за  ее  освобождение.  Начинающий  программист  мог  бы  допустить

ilist_item::~ilist_item()

{

delete _next;

ошибку, вызвав деструктор для ilist_item:

}

Посмотрите на функции remove_all() и remove_front() и объясните, почему наличие такого деструктора является ошибочным.

Упражнение 5.17

void ilist::remove_end();

Наш класс ilist не поддерживает следующие операции:

 

void ilist::remove( ilist_item* );

Как вы думаете, почему мы их не включили? Реализуйте их.

Упражнение 5.18

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

class ilist {

public:

// ...

ilist_item* find( int value, ilist_item *start_at = 0 );

// ...

использующие предыдущую версию find(), будут работать без модификации.)

};

Упражнение 5.19

Используя новую версию find(), напишите функцию count(), которая подсчитывает количество  вхождений  элементов  с  заданным  значением.  Подготовьте  тестовую программу.

Упражнение 5.20

Модифицируйте   insert(int value) так,   чтобы   она   возвращала   указатель   на вставленный объект ilist_item.

Упражнение 5.21

void ilist::

insert( ilist_item *begin,

int *array_of_value,

Используя модифицированную версию insert(), напишите функцию:

int elem_cnt );

где array_of_value указывает на массив значений, который нужно вставить в ilist, elem_cnt – на размер этого массива, а begin – на элемент, после которого производится вставка. Например, если есть ilist:

(3)( 0 1 21 )

и массив:

int ia[] = { 1, 2, 3, 5, 8, 13 };

вызов этой новой функции

 

ilist_item *it = mylist.find( 1 );

mylist.insert( it, ia, 6 );

изменит список таким образом:

(9) ( 0 1 1 2 3 5 8 13 21 )

Упражнение 5.22

Функции  concat() и  reverse() модифицируют оригинальный  список. Это не всегда желательно.  Напишите  аналогичную  пару  функций,  которые  создают  новый  объект

ilist ilist::reverse_copy();

ilist:

ilist ilist::concat_copy( const ilist &rhs );