Книга: Эффективное использование STL

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

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

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

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

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

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

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

list<int> list1;
list<int> 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.

Оглавление книги