Стандарты программирования на С++. 101 правило и рекомендация

• Передача неверной позиции итератора. Вызов функции-члена контейнера, которая получает позицию итератора (как, например, позиция, передаваемая функции insert), но с передачей итератора, который указывает в другой контейнер.

• Использование неверного упорядочения. Предоставление неверного правила для упорядочения ассоциативного контейнера или в качестве критерия сравнения в алгоритме сортировки (см. примеры в [Meyers01]). Если не использовать отладочной версии STL, такие ошибки обычно проявляются в процессе выполнения программы как неверное поведение или бесконечные циклы, но не как аварийный останов.

Большинство отладочных реализаций STL автоматически обнаруживают такие ошибки, при помощи дополнительной отладочной и системной информации, хранящейся в контейнерах и итераторах. Например, итератор может запомнить контейнер, к которому он обращается, а контейнер — запомнить все итераторы, ссылающиеся на него, так что можно отследить использование ставшего недействительным итератора. Конечно, это увеличивает размер итераторов и контейнеров, а также требует выполнения дополнительных действий при каждом изменении контейнера. Но возможность отслеживания ошибок стоит того — по крайней мере, в процессе отладки, а возможно, и в окончательной версии программы (вспомните рекомендацию 8; не отключайте полезные проверки для повышения производительности до тех пор, пока не убедитесь в необходимости такого шага непосредственными измерениями).

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

Примеры

Пример 1. Использование недействительного итератора. Очень просто забыть, что итераторы стали недействительны, и воспользоваться таким недействительным итератором (см. рекомендацию 99). Рассмотрим подобный пример, адаптированный из [Meyers01], где происходит вставка элементов в начало deque:

deque<double>::iterator current = d.begin;
for (size_t i =0; i < max; ++i )
 d.insert(current++, data[i] + 41); // Видите ли вы ошибку?

Быстро ответьте — увидели ли вы ошибку в приведенном фрагменте или нет? У вас только три секунды!

Время вышло! Если вы не заметили ошибку за отпущенное время, не волнуйтесь — это достаточно тонкая и понятная ошибка. Отладочная версия STL обнаружит данную ошибку на второй итерации цикла, так что вам не придется полагаться на свой невооруженный взгляд. (Исправленная версия данного кода и альтернативные варианты вы найдете в рекомендации 84.)

Пример 2. Использование диапазона итераторов, на самом деле не являющегося диапазоном. Диапазон итераторов представляет собой пару итераторов first и last, которые указывают на первый элемент диапазона, и элемент, следующий за последним элементом диапазона. Диапазон требует, чтобы итератор last был достижим из first путем некоторого количества повторных увеличений при помощи оператора инкремента итератора first. Известны два распространенных вида ошибки, когда происходит попытка использовать диапазон, который на самом деле диапазоном не является. Первая ошибка возникает, когда два итератора ограничивают диапазон в пределах одного контейнера, но итератор first на самом деле не предшествует итератору second:

for_each(c.end,с.begin,Something); // не всегда очевидно

На каждой итерации своего внутреннего цикла алгоритм for_each будет проверять итератор first на равенство итератору second, и до тех пор, пока они не равны, он будет увеличивать итератор first. Конечно, сколько бы раз не был увеличен итератор first, ему никогда не стать равным итератору second, так что цикл по сути оказывается бесконечным. На практике в лучшем случае цикл завершится выходом за пределы контейнера с и немедленным аварийным завершением программы из-за нарушения защиты памяти. В худшем случае, выйдя за пределы контейнера, итератор будет считывать или даже менять данные, не являющиеся частью контейнера. Этот результат в принципе не слишком отличается от знакомых нам последствий переполнения буфера…

Вторая распространенная ошибка возникает, когда итераторы указывают в разные контейнеры:

for_each(c.begin,d.end,Something); // не всегда очевидно

Результат такой ошибки аналогичен результату предыдущей. Однако поскольку итераторы отладочной версии STL помнят контейнер, с которым работают, такую ошибку можно выявить во время выполнения программы.

Ссылки

[Dinkumware-Safe] • [Horstmann95] • [Josuttis99] §5.11.1 • [Metrowerks] • [Meyers01] §21, §50 • [STLport-Debug] • [Stroustrup00] §18.3.1, §19.3.1

84. Предпочитайте вызовы алгоритмов самостоятельно разрабатываемым циклам

Резюме

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

При вызове алгоритма подумайте о написании собственного функционального объекта, который инкапсулирует всю необходимую логику. Избегайте объединения связывателей параметров и простых функциональных объектов (например, bind2nd, plus), что обычно снижает ясность кода. Подумайте об использовании лямбда-библиотеки [Boost], которая автоматизирует задачу написания функциональных объектов.

Обсуждение

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

Главное преимущество алгоритмов и шаблонов проектирования в общем случае заключается в том, что они позволяют нам говорить на более высоком уровне абстракции. В современном программировании мы не говорим "пусть несколько объектов следят за одним объектом и получают автоматические уведомления при изменении его состояния". Вместо этого мы говорим просто о "шаблоне проектирования Observer". Аналогично, мы говорим "Bridge", "Factory" и "Visitor". Использование словаря шаблонов проектирования позволяет повысить уровень, эффективность и корректность нашего обсуждения. Точно так же при использовании алгоритмов мы не говорим "выполняем действие над каждым элементом диапазона и записываем результат в некоторое место"; вместо этого мы говорим просто — transform. Аналогично, мы можем сказать for_each, replace_if и partition. Алгоритмы, подобно шаблонам проектирования, самодокументируемы. "Голые" циклы for и while ничего не говорят о том, для чего они предназначены, и читателю приходится изучать тела циклов, чтобы расшифровать их семантику.

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

И наконец, алгоритмы зачастую также более эффективны, чем простые циклы (см. [Sutter00] и [Meyers01]). В них устранены небольшие неэффективности, такие как повторные вычисления container.end). Не менее важно, что стандартные алгоритмы, используемые вами, были реализованы теми же программистами, кто реализовывал и используемые вами стандартные контейнеры, и понятно, что их знание конкретных реализаций позволяет им написать алгоритмы более эффективно, чем это сможете сделать вы. Важнее всего, однако, то, что многие алгоритмы имеют высокоинтеллектуальные реализации, которые мы никогда не сможем реализовать в собственноручно разработанном коде (не считая случаев, когда нам не нужна та степень обобщенности, которую предоставляют алгоритмы). Вообще говоря, более используемая библиотека всегда оказывается лучше отлаженной и более эффективной просто потому, что у нее больше пользователей. Вряд ли вы найдете и сможете использовать в своей программе библиотеку, настолько же широко применяемую, как и реализация вашей стандартной библиотеки. Воспользуйтесь ею. Алгоритмы STL уже написаны — так почему бы не воспользоваться ими?

Подумайте об использовании лямбда-функций [Boost]. Лямбда-функции представляют собой важный инструмент, который позволяет справиться с основным недостатком алгоритмов, а именно с удобочитаемостью. Без их применения вы должны использовать либо функциональные объекты (но тогда тела даже простых циклов находятся в отдельном месте, далеко от точки вызова), либо стандартные связыватели и функциональные объекты наподобие bind2nd и plus (достаточно запутанные, сложные и утомительные в использовании).