Как работает оператор switch в Си/Си++

Запись от Evg размещена 15.02.2012 в 20:36
Обновил(-а) Evg 08.04.2018 в 11:36

Метки c++

ВНИМАНИЕ! Вопросы по существу обсуждаемого вопроса просьба задавать здесь или создать тему на форуме и кинуть на неё ссылку в блог или мне в личку.

Объясняю почему

Причин для этого несколько.

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

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

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

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

1. Как обычно поясняется работа switch'а в учебниках

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

Начну с простого примера

switch (x)
{
  case 10:
    y = 1;
    break;
  case 11:
  case 12:
    y = 2;
    break;
  default:
    y = 3;
    break;
}

в учебниках обычно поясняется, что данный пример является эквивалентом примера

if (x == 10)
  {
    y = 1;
  }
else if (x == 11 || x == 12)
  {
    y = 2;
  }
else
  {
    y = 3;
  }

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

Те, кто перешёл с Паскаля на Си, очень часто спотыкаются о необходимость расставлять break'и. В паскале конструкция case (а точнее, её альтернатива, ибо я не помню, как правильно в паскале писать) означает автоматическое завершение кода предыдущей альтернативы и уход на конец switch'а. В учебниках сей факт как правило поясняют тем, что break можно не ставить, и в этом случае произойдёт провал (fall) на следующую альтернативу. Ну и как частный случай - два подряд идущих case'а являются вырожденным случаем провала. Необходимость построения настоящих (невырожденных) провалов на практике является статистически редким явлением, и потому многих необходимость написания break'а сильно раздражает.

2. Как на самом деле работает switch

Оператор switch на самом деле является коммутируем переходом. Т.е. в зависимости от значения ключа (то, что стоит в скобках после слова switch) происходит переход на ту или иную метку, а операторы case определяют эти самые метки. Продемонстрирую это на примере, содержащем в том числе провалы (отсутствие break'ов).

switch (x)
{                 <--- скобка 1
  case 10:
    y = 1;
    break;
  case 11:
  case 12:
    y = 2;
    /* break; */  <--- тут уберём break и устроим провал
  default:
    y = 3;
    break;
}                 <--- скобка 2

Семантическим эквивалентом данному коду будет

/* Данный набор операторов if и goto есть семантический эквивалент
 * оператора switch (x) */
if (x == 10)
  goto L10;
else if (x == 11)
  goto L11;
else if (x == 12)
  goto L12;
else
  goto Ldefault;
{                        <--- скобка 1
L10:                     <--- метка "case 10"
  y = 1;
  goto Finish;           <--- break
L11:                     <--- метка "case 11"
L12:                     <--- метка "case 12"
  y = 2;
  /* goto Finish; */     <--- закомментированный break
Ldefault:                <--- метка "default"
  y = 3;
  goto Finish;           <--- break
}                        <--- скобка 2
Finish:                  <--- метка за пределами switch'а, куда ведут все break'и
                              эта метка полностью эквивалентна тому, что есть
                              в циклах for и while

Вот так на самом деле работает оператор switch. Если посмотреть на пример пояснения из учебника (раздел 1) и данный пример, то с виду кажется, что принципиальных отличий одного от другого нет и второе элементарно сводится к первому. Конкретно в данном случае это действительно так. Но в данном примере я пояснил лишь принцип действия оператора switch, но не заострял внимания на его синтаксисе, о чём будет сделано в следующем разделе

3. То, о чём редко пишут в учебниках

Поискав через google описание работы switch'а, я много раз натыкался на описание синтаксиса. Этот синтаксис сводится к следующему (здесь привожу вариант с MSDN):

Код:

switch (expression)  {
  case constant_expression_1 : statement_1;
  ...
  case constant_expression_n : statement_n;
[default: statement_n+1]
}

Такое описание является НЕ верным, потому что синтаксис оператора switch в языках Си/Си++ определяется НЕ так. Но чтобы проще было понять, вернёмся к тому, с чем все хорошо знакомы - к оператору if. Синтаксис оператора if в самом простейшей случае (без else) неформальным образом можно выразить так:

Код:

if (expression)
  body

Где "body" - это либо одиночный statement, либо группа statement'ов, заключённых в фигурные скобки. Если мы рассмотрим синтаксис оператора while, то выглядит он аналогичным образом:

Код:

while (expression)
  body

но при этом отличие от варианта if'а заключается в том, что "body" может содержать в себе операторы break и continue (которые на самом деле являются операторами goto на неявные метки). Синтаксис switch'а определяется абсолютно таким же образом:

Код:

switch (expression)
  body

при этом "body" может содержать внутри себя метки case и переходы break

Теперь рассмотрим синтетический (т.е. не из реальной жизни) пример, который на первый взгляд многим может показаться диким, потому что идёт в разрез с имеющимся представлением о работе switch'а:

switch (x)
  if (z == 5)
    {
    case 10:
      y = 1;
    }
  else
    {
    case 11:
      if (z > 10)
        y = 2;
      else
        {
      default:
          y = 3;
        }
    }

С точки зрения языка Си данный пример является абсолютно корректным. Классическое пояснение из учебников (см. раздел 1) не в состоянии объяснить работу этого примера. Пример описания синтаксиса, данный в начале данного раздела, вообще будет считать этот пример некорректным с точки зрения языка (как минимум потому, что после switch'а отсутствует открывающая фигурная скобка). И только правильное пояснение (см. раздел 2) в состоянии описать, как же будет работать этот пример.

if (x == 10)        <--- начало оператора switch
  goto L10;
else if (x == 11)
  goto L11;
else
  goto Ldefault;    <--- конец оператора switch
  if (z == 5)       <--- начало "body"
    {
    L10:            <--- метка "case 10"
      y = 1;
    }
  else
    {
    L11:            <--- метка "case 11"
      if (z > 10)
        y = 2;
      else
        {
      Ldefault:     <--- метка "Ldefault"
          y = 3;
        }
    }

При таком раскладе можно понять, что операторы if, написанный в самом начале switch'а, является мёртвым кодом (т.е. туда управление никогда не передастся). Однако перед ним мы можем поставить метку (обычную или case) и тогда мёртвых кодов не останется. Если "body" switch'а реализовано через фигурные скобки (как это делается в обычной жизни), то эти фигурные скобки стандартным образом задают лексический блок, в котором можно описывать переменные (критично для Си):

switch (x)
{
  int a, b;   <--- переменные a и b доступны только внутри фигурных скобок
 
  case 10:
    a = x + 1;
    b = x - 1;
    y = a * b;
    break;
  ...
}

Напоследок хочется сказать, что на практике такими "дебильными" конструкциями пользуются очень и очень редко. На практике я пока только однажды встречал конструкцию, являющуюся вариацией алгоритма под названием Duff's device

void send (int *to, const int *from, int count)
{
  int n = (count + 7) / 8;
  switch (count % 8)
  {
    case 0: do { *to++ = *from++;
    case 7:      *to++ = *from++;
    case 6:      *to++ = *from++;
    case 5:      *to++ = *from++;
    case 4:      *to++ = *from++;
    case 3:      *to++ = *from++;
    case 2:      *to++ = *from++;
    case 1:      *to++ = *from++;
            } while (--n > 0);
  }
}

Данный пример обсуждался в теме Что делает данный код и зачем такое кому-нибудь может понадобиться?. Предполагаемый ответ на вопрос был озвучен в 10-м посте указанной темы.

4. Для чего придумали оператор switch

С виду кажется, что switch в "нормальном" случае принципиально ничем не отличается от цепочки конструкций if - else if - ... По принципу действия действительно не отличается. Однако с точки зрения генерации кода switch принципиально строится по другому. Проще всего это опять пояснить на коротком примере.

switch (x)
{
  case 5:
    y = 10;
  case 6:
    y = 25;
  case 7:
    y = 38;
  ...
  case 20:
    y = 125;
  default:
    y = 1000;
}

В данном примере я не стал ставить break'и, чтобы они не путались под ногами. В нижеидущем примере-аналоге используется конструкция "&&" - операция взятия адреса на метку. В языках Си и Си++ такой операции нет, однако с точки зрения генерируемого кода ничто не мешает тому, чтобы такая операция была, потому как в любом процессоре есть соответствующая аппаратная операция. Именно так рассуждали разработчики компилятора gcc и в своё расширение языка эту операцию внесли (ptr = &&L). А так же операцию перехода по указателю на метку (goto *ptr). Поэтому в примере-аналоге я буду использовать именно эту операцию. Таким образом наш switch аналогичен примеру:

/* Массив меток перехода на 16 альтернатив switch'а (от 5 до 20) */
static void *arr[16] = { &&L5, &&L6, &&L7, ..., &&L20 };
 
/* При таких значениях x мы попадаем в один из case'ов switch'а,
 * адрес для перехода загрузим из таблицы arr. При этом надо понимать, что
 * нулевой элемент таблицы соответствует значению x = 5. */
if (x >= 5 && x <= 20)
  goto *arr[x-5];
else
  goto L_default;
 
L5:
  y = 10;
L6:
  y = 25;
L7:
  y = 38;
  ...
L20:
  y = 125;
L_default:
  y = 1000;

Мы видим, что вместо длинной цепочки из 16-и if'ов мы имеем очень коротенький код по динамическому переходу (переходу на заранее неизвестный адрес). Важно понимать, что скорость исполнения этого кода НЕ зависит от размеров таблицы: т.е. switch из 1000 элементов работает с такой же скоростью, как switch из 5 элементов (чего не скажешь о цепочке if'ов). В то время как массив с метками переходов является статически инициализированным (т.е. в бинарном файле лежит уже заполненная таблица, которую в run-time не надо перевычислять).

Есть некоторые тонкие моменты, остающихся на усмотрение компилятора. Например, если в switch'е мы имеем всего две альтернативы 1 и 1000000, то таблица, построенная по такому принципу, занимала бы миллион слов (4 мегабайта в 32-битном режиме). Компилятор в таком случае вместо динамического перехода построит цепочку из двух if'ов. Есть ещё куча аналогичных моментов, которые я не стану описывать, потому что для общего понимания предназначения switch'а эти моменты не являются критичными

5. Ссылки на темы, где обсуждался данный вопрос

Размещено в Статьи по программированию, Неочевидные ответы на простые вопросы

Показов 252571 Комментарии 24

« Представление вещественных чисел "на пальцах" Главная страница Для чего нужен спецификатор inline »

Всего комментариев 24

Комментарии

2 из 2

	[B]Pure[/B], дали же грамотный совет: [QUOTE]можешь писать так для себя так, как хочешь. Главное, другим не показывай — засмеют ведь.[/QUOTE] просто придерживайся его и всё у тебя будет хорошо
	Запись от LosAngeles размещена 04.05.2012 в 06:56

	Nameless One Ну а на самом деле, спасибо за диалог. Последний пост порадовал. И тебе всего хорошего.
	Запись от Pure размещена 04.05.2012 в 21:49

	Я гребу,я і не знав що з свічом можна так ізвращатись)
	Запись от vitaliy2034 размещена 27.05.2017 в 12:41

	Ещё один интересный пример поместил в https://www.cyberforum.ru/cpp-... st12288952
	Запись от Evg размещена 08.04.2018 в 11:34

2 из 2

Сообщение форума

Отменить изменения