Скотт Мейерс - Эффективное использование STL

list list1;

list list2;

list1.splice( // Переместить все узлы list2

list1.end(),list2, // от первого вхождения 5

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

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

); // Вызов base() рассматривается

// в совете 28

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

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

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

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

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

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

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

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

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

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

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