Но почему списки так себя ведут? Почему они не обеспечивают выполнения

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

Приведенный фрагмент не работает, если только значение 10 не входит в

после 5, но пока не будем обращать на это внимания. Вместо этого зададимся вопросом: сколько элементов окажется в списке после врезки? Разумеется, столько, сколько было до врезки, в сумме с количеством новых элементов. Последняя величина равна количеству элементов в интервале, определяемом вызовами и . Сколько именно? Чтобы ответить на этот вопрос, нужно перебрать и подсчитать элементы интервала. В этом и заключается проблема.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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