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

vector<Widget> vw; Создать вектор, не содержащий ни одного объекта Widget и увеличивающийся по мере необходимости

Можно также создать пустой вектор, в котором зарезервировано место для maxNumWidgets объектов Widget, но не сконструирован ни один из этих объектов:

vector<Widget> vw:

vw.reserve(maxNumWidgets): Функция reserve описана в совете 14

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

Совет 4. Вызывайте empty вместо сравнения size() с нулем

Для произвольного контейнера с следующие две команды фактически эквивалентны:

if (c.size()==0)...

if (c.emptyO)...

Возникает вопрос - почему же предпочтение отдается одной конструкции, особенно если заесть, что empty обычно реализуется в виде подставляемой (inline) функции, которая просто сравнивает sizeO с нулем и возвращает результат?

Причина проста: функция empty для всех стандартных контейнеров выполняется с постоянной сложностью, а в некоторых реализациях 1 ist вызов size требует линейных затрат времени.

Но почему списки так себя ведут? Почему они не обеспечивают выполнения size с постоянной сложностью? Это объясняется в основном уникальными свойствами функций врезки (splicing). Рассмотрим следующий фрагмент:

list<int> listl; list<int> 1ist2:

listl.spliceC Переместить все узлы list2

listl.endO.list2. от первого вхождения 5

find(list2.begin(),list2.end(), 5), до последнего вхождения 10

find(list2.rbegin().list2.rend().10).base() в конец listl

); Вызов baseO рассматривается

в совете 28

Приведенный фрагмент не работает, если только значение 10 не входит в 1 ist2 после 5, но пока не будем обращать на это внимания. Вместо этого зададимся вопросом: сколько элементов окажется в списке 1 i stl после врезки? Разумеется, столько, сколько было до врезки, в сумме с количеством новых элементов. Последняя величина равна количеству элементов в интервале, определяемом вызовами find(list2.begin(),list2.end(), 5) и find(list2.rbegin().list2.rend(),10).baseO. Сколько именно? Чтобы ответить на этот вопрос, нужно перебрать и подсчитать элементы интервала. В этом и заключается проблема.

Допустим, вам поручено реализовать 1 i st. Это не просто контейнер, а стандартный контейнер, поэтому заранее известно, что класс будет широко использоваться. Естественно, реализация должна быть как можно более эффективной. Операция определения количества элементов в списке будет часто использоваться клиентами, поэтому вам хотелось бы, чтобы операция size работала с постоянной сложностью. Класс 1 i st нужно спроектировать так, чтобы он всегда знал количество содержащихся в нем элементов.

В то же время известно, что из всех стандартных контейнеров только list позволяет осуществлять врезку элементов без копирования данных. Можно предположить, что многие клиенты выбирают 1 i st именно из-за эффективности операции врезки. Они знают, что интервальная врезка из одного списка в другой выполняется за постоянное время; вы знаете, что они это знают, и постараетесь не обмануть их надежды на то, что функция splice работает с постоянными затратами времени.

Возникает дилемма. Чтобы операция size выполнялась с постоянной сложностью, каждая функция класса 1 i st должна обновлять размеры списков, с которыми она работает. К числу таких функций относится и splice. Но сделать это можно только одним способом - функция должна подсчитать количество вставляемых элементов, а это не позволит обеспечить постоянное время выполнения splice... чего мы, собственно, и пытались добиться. Если отказаться от обновления размеров списков функцией splice, добиться постоянного времени выполнения для spl ice можно, но тогда с линейной сложностью будет выполняться size - ей придется перебирать всю структуру данных и подсчитывать количество элементов. Как ни старайся, чем-то - size или splice - придется пожертвовать. Одна из этих операций может выполняться с постоянной сложностью, но не обе сразу.

В разных реализациях списков эта проблема решается разными способами в зависимости от того, какую из операций - size или splice - авторы хотят оптимизировать по скорости. При работе с реализацией 1 ist, в которой было выбрано постоянное время выполнения splice, лучше вызывать empty вместо size, поскольку empty всегда работает с постоянной скоростью. Впрочем, даже если вы не используете такую реализацию, не исключено, что это произойдет в будущем. Возможно, программа будет адаптирована для другой платформы с другой реализацией STL, или вы перейдете на новую реализацию STL для текущей платформы.

В любом случае вы ничем не рискуете, вызывая empty вместо проверки условия size()=0. Мораль: если вам потребовалось узнать, содержит ли контейнер ноль элементов - вызывайте empty. .

Совет 5. Используйте интервальные функции вместо одноэлементных

Есть два вектора, vl и v2. Как проще всего заполнить vl содержимым второй половины v2? Только не надо мучительно размышлять над тем, что считать половиной при нечетном количестве элементов в v2. Просто постарайтесь быстро дать разумный ответ.

Время истекло! Если вы предложили

vl.assign(v2.begin()+v2.size()/2,v2.end()):

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

Кстати говоря, если при чтении ответа вы произнесли Чего-чего? или что-нибудь в этом роде, читайте внимательно, потому что речь пойдет об очень полезных вещах.

Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции assign, о которой многие программисты попросту забывают. Функция assign поддерживается всеми стандартными последовательными контейнерами (vector, string, deque и 1 ist). Каждый раз, когда вам требуется полностью заменить содержимое контейнера, подумайте, нельзя ли добиться желаемой цели присваиванием. Если вы просто копируете один контейнер в другой контейнер того же типа, задача решается функцией operator=. Но, как показывает приведенный пример, существует также функция assign, которая позволяет заполнить контейнер новыми данными в тех случаях, когда operator= не подходит.

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

vector<Widget> vl,v2; ПреАПОлагается. что vl и v2 -

векторы объектов Widget

vl.clearO;

for (vector<Widget>::constjterator ci=v2.begin()+v2.size()/2; ci != v2.end(); ++ci) vl.push back(*ci):

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

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

vl.clearO:

copy(v2.begin()+v2.size()/2.v2.end().back inserter(vl)):