Чтение онлайн

Допустим, вам поручено реализовать

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

В то же время известно, что из всех стандартных контейнеров только

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

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

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

В разных реализациях списков эта проблема решается разными способами в зависимости от того, какую из операций —

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

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

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

Есть два вектора,

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

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

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

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

Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции

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

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

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

. Цикл также отрицательно влияет на быстродействие, но к этой теме мы вернемся позже.

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

Но и этот вариант требует больших усилий, чем простой вызов

. Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова (см. совет 43). В результате потенциальное снижение быстродействия не исчезает (вскоре мы поговорим об этом). А сейчас я хочу ненадолго отвлечься от темы и заметить, что практически все случаи использования , когда приемный интервал задается итератором вставки ( или ), могут — и должны — заменяться вызовами интервальных функций. Например, вызов заменяется интервальной версией :