. Это не просто контейнер, а стандартный контейнер, поэтому заранее известно, что класс будет широко использоваться. Естественно, реализация должна быть как можно более эффективной. Операция определения количества элементов в списке будет часто использоваться клиентами, поэтому вам хотелось бы, чтобы операция
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
.
Совет 5. Используйте интервальные функции вместо одноэлементных
Есть два вектора,
v1
и
v2
. Как проще всего заполнить
v1
содержимым второй половины
v2
? Только не надо мучительно размышлять над тем, что считать «половиной» при нечетном количестве элементов в
v2
. Просто постарайтесь быстро дать разумный ответ.
Время истекло! Если вы предложили
v1.assign(v2.begin+v2.size/2, v2.end)
или
нечто похожее — поздравляю, пять баллов. Если в вашем ответе присутствуют вызовы более чем одной функции, но при этом он обходится без циклов, вы получаете «четверку». Если в ответе задействован цикл, вам есть над чем поработать, а если несколько циклов — значит, вы узнаете из этой книги много нового.
Кстати говоря, если при чтении ответа вы произнесли «Чего-чего?» или что-нибудь в этом роде, читайте внимательно, потому что речь пойдет об очень полезных вещах.
Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции
assign
, о которой многие программисты попросту забывают. Функция
assign
поддерживается всеми стандартными последовательными контейнерами (
vector, string, deque
и
list
). Каждый раз, когда вам требуется полностью заменить содержимое контейнера, подумайте, нельзя ли добиться желаемой цели присваиванием. Если вы просто копируете один контейнер в другой контейнер того же типа, задача решается функцией
operator=
. Но, как показывает приведенный пример, существует также функция
assign
, которая позволяет заполнить контейнер новыми данными в тех случаях, когда
operator=
не подходит.
Во-вторых, эта задача показывает, почему интервальные функции лучше своих одноэлементных аналогов. Интервальной называется функция контейнера, которая, подобно алгоритмам STL, определяет интервал элементов для выполняемой операции при помощи двух параметров-итераторов. Без интервальной функции нам пришлось бы создавать специальный цикл:
vector<Widget> v1,v2; // Предполагается, что v1 и v2 -
// векторы объектов Widget
…
v1.clear:
for (vector<Widget>::const_iterator ci=v2.begin+v2.size/2; ci != v2.end; ++ci)
v1.push_back(*ci);
В совете 43 подробно объясняется, почему использовать явные циклы не рекомендуется, но и без этого ясно, что написание этого фрагмента потребует больше усилий, чем простой вызов
assign
. Цикл также отрицательно влияет на быстродействие, но к этой теме мы вернемся позже.
Одно из возможных решений заключается в том, чтобы последовать совету 43 и воспользоваться алгоритмом:
Но и этот вариант требует больших усилий, чем простой вызов
assign
. Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова
copy
(см. совет 43). В результате потенциальное снижение быстродействия не исчезает (вскоре мы поговорим об этом). А сейчас я хочу ненадолго отвлечься от темы и заметить, что практически все случаи использования
copy
, когда приемный интервал задается итератором вставки (
inserter, back_inserter
или
front_inserter
), могут — и должны — заменяться вызовами интервальных функций. Например, вызов