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

Мейерс Скотт

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

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

.

Совет 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 и воспользоваться алгоритмом:

v1.clear;

copy(v2.begin+v2.size/2, v2.end, back_inserter(v1));

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

assign

. Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова

copy

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

copy

, когда приемный интервал задается итератором вставки (

inserter, back_inserter

или

front_inserter

), могут — и должны — заменяться вызовами интервальных функций. Например, вызов

copy

заменяется интервальной версией

insert

: