Эффективное использование STL

задаваться дважды — сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель prev узла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются numValues узлов, будет выполнено numValues - 1 лишних присваиваний указателю next вставленных узлов и numValues-1 лишних присваиваний указателю prev узла А, то есть в общей сложности 2*(numValues-l) лишних операций присваивания. Конечно, присваивание указателю обходится недорого, но зачем вообще платить, если можно обойтись без этого?

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

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

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

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

•Интервальные конструкторы. У всех стандартных контейнеров существуют конструкторы следующего вида:

контейнер::контейнер( InputIterator begin, // Начало интервала 	InputIterator end);	// Конец интервала

При передаче этому конструктору итераторов istream_iterator и isreambuf_ iterator (совет 29) иногда встречается одна из самых удивительных ошибок С++, вследствие которой компилятор интерпретирует эту конструкцию как объявление функции, а не как определение нового объекта контейнера. В совете 6 рассказано все, что необходимо знать об этой ошибке, в том числе и способы ее преодоления.

•Интервальная вставка. Во всех стандартных последовательных контейнерах присутствует следующая форма insert:

void контейнер::insert(iterator position. // Позиция вставки
	InputIterator  begin, // Начало интервала
	InputIterator end); // Конец интервала

Ассоциативные контейнеры определяют позицию вставки при помощи собственных функций сравнения, поэтому в них предусмотрена сигнатура без параметра position:

void контейнер::insert(InputIterator begin, InputIterator end);

Рассматривая возможности замены одноэлементных вызовов insert интервальными версиями, не забывайте, что некоторые одноэлементные варианты маскируются под другими именами. Например, push_front и push_back заносят в контейнер отдельный элемент, хотя в их названии отсутствует слово insert. Если в программе встречается циклический вызов push_front/push_back или алгоритм (например, сору), которому в качестве параметра передается front_inserter или back_inserter, перед вами потенциальный кандидат для применения интервальной формы insert.

•Интервальное удаление. Интервальная форма erase существует в каждом стандартном контейнере, но типы возвращаемого значения отличаются для последовательных и ассоциативных контейнеров. В последовательных контейнерах используется следующий вариант сигнатуры:

iterator контейнер::erase(iterator begin, iterator end);

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

void контейнер::erase(iterator begin, iterator end);

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

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

Но erase не присущ такой недостаток insert контейнеров vector и string, как многократные выделения памяти (конечно, для erase речь пойдет о многократном освобождении). Дело в том, что память, занимаемая vector и string, автоматически увеличивается для новых элементов, но при уменьшении количества элементов память не освобождается (в совете 17 рассказано о том, как уменьшить затраты освободившейся памяти в vector и string).

К числу особенно важных аспектов интервального удаления относится идиома erase-remove, описанная в совете 29.

•Интервальное присваивание. Как упоминалось в самом начале совета, во всех последовательных контейнерах предусмотрена интервальная форма assign:

void контейнер::assign(InputIterator begin, InputIterator end);

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

Совет 6. Остерегайтесь странностей лексического разбора С++

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

ifstream dataFile('ints.dat');
list<int> data(istream_iterator<int>(dataFile), // Внимание! Эта строка
	istream_iterator<int>()); // работает не так, как
	// вы предполагали

Идея проста: передать пару istream_iterator интервальному конструктору list (совет 5), после чего скопировать числа из файла в список.

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

Начнем с азов. Следующая команда объявляет функцию f, которая получает double и возвращает int:

int f(double d);

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

int f(double(d));// То же,- круглые скобки вокруг d игнорируются

Рассмотрим третий вариант объявления той же функции. В нем просто не указано имя параметра:

int f(double);// То же; имя параметра не указано

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

Теперь рассмотрим еще три объявления функции. В первом объявляется функция g с параметром — указателем на функцию, которая вызывается без параметров и возвращает double:

int g(double (*pf)()); // Функции g передается указатель на функцию

То же самое можно сформулировать и иначе. Единственное различие заключается в том, что pf объявляется в синтаксисе без указателей (допустимом как в С, так и в С ++):

int g(double pf()); // То же; pf неявно интерпретируется как указатель

Как обычно, имена параметров могут опускаться, поэтому возможен и третий вариант объявления g без указания имени pf:

int g(double());// То же: имя параметра не указано

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

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

list<int> data(istream_iterator<int>(dataFile),
istream_iterator<int>());

Держитесь и постарайтесь не упасть. Перед вами объявление функции data, возвращающей тип list<int>. Функция data получает два параметра:

•Первый параметр, dataFile, относится к типу istream_iterator<int>. Лишние круглые скобки вокруг dataFile игнорируются.

•Второй параметр не имеет имени. Он относится к типу указателя на функцию, которая вызывается без параметров и возвращает istream_iterator<int>.

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

class Widget{...};// Предполагается, что у Widget