- •Герб Саттер
- •Как пользоваться этой книгой
- •Стандарты кодирования и вы
- •Об этой книге
- •Благодарности
- •Вопросы организации и стратегии
- •0. Не мелочитесь, или Что не следует стандартизировать Резюме
- •Обсуждение
- •Примеры
- •1. Компилируйте без замечаний при максимальном уровне предупреждений Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •2. Используйте автоматические системы сборки программ Резюме
- •Обсуждение
- •3. Используйте систему контроля версий Резюме
- •Обсуждение
- •Исключения
- •Стиль проектирования
- •5. Один объект — одна задача Резюме
- •Обсуждение
- •Примеры
- •6. Главное — корректность, простота и ясность Резюме
- •Обсуждение
- •Примеры
- •7. Кодирование с учетом масштабируемости Резюме
- •Обсуждение
- •8. Не оптимизируйте преждевременно Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •10. Минимизируйте глобальные и совместно используемые данные Резюме
- •Обсуждение
- •Исключения
- •11. Сокрытие информации Резюме
- •Обсуждение
- •Исключения
- •13. Ресурсы должны быть во владении объектов Резюме
- •Обсуждение
- •Исключения
- •Стиль кодирования
- •14. Предпочитайте ошибки компиляции и компоновки ошибкам времени выполнения Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •Примеры
- •16. Избегайте макросов Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •17. Избегайте магических чисел Резюме
- •Обсуждение
- •Примеры
- •18. Объявляйте переменные как можно локальнее Резюме
- •Обсуждение
- •Исключения
- •Примеры
- •Исключения
- •Исключения
- •22. Минимизируйте зависимости определений и избегайте циклических зависимостей Резюме
- •Обсуждение
- •Исключения
- •Примеры
- •24. Используйте только внутреннюю, но не внешнюю защиту директивы #include Резюме
- •Обсуждение
- •Исключения
- •Функции и операторы
- •25. Передача параметров по значению, (интеллектуальному) указателю или ссылке Резюме
- •Обсуждение
- •26. Сохраняйте естественную семантику перегруженных операторов Резюме
- •Обсуждение
- •Исключения
- •27. Отдавайте предпочтение каноническим формам арифметических операторов и операторов присваивания Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •30. Избегайте перегрузки &&, || и , (запятой) Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •Проектирование классов и наследование
- •32. Ясно представляйте, какой вид класса вы создаете Резюме
- •Обсуждение
- •33. Предпочитайте минимальные классы монолитным Резюме
- •Обсуждение
- •34. Предпочитайте композицию наследованию Резюме
- •Обсуждение
- •Исключения
- •35. Избегайте наследования от классов, которые не спроектированы для этой цели Резюме
- •Обсуждение
- •36. Предпочитайте предоставление абстрактных интерфейсов Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •Исключения
- •Примеры
- •39. Виртуальные функции стоит делать неоткрытыми, а открытые — невиртуальными Резюме
- •Обсуждение
- •Исключения
- •Примеры
- •Исключения
- •41. Делайте данные-члены закрытыми (кроме случая агрегатов в стиле структур с) Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •42. Не допускайте вмешательства во внутренние дела Резюме
- •Обсуждение
- •Исключения
- •43. Разумно пользуйтесь идиомой Pimpl Резюме
- •Обсуждение
- •Исключения
- •Примеры
- •Исключения
- •Конструкторы, деструкторы и копирование
- •47. Определяйте и инициализируйте переменные-члены в одном порядке Резюме
- •Обсуждение
- •48. В конструкторах предпочитайте инициализацию присваиванию Резюме
- •Обсуждение
- •Исключения
- •Примеры
- •50. Делайте деструкторы базовых классов открытыми и виртуальными либо защищенными и невиртуальными Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •51. Деструкторы, функции освобождения ресурсов и обмена не ошибаются Резюме
- •Обсуждение
- •52. Копируйте и ликвидируйте согласованно Резюме
- •Обсуждение
- •Исключения
- •53. Явно разрешайте или запрещайте копирование Резюме
- •Обсуждение
- •54. Избегайте срезки. Подумайте об использовании в базовом классе клонирования вместо копирования Резюме
- •Обсуждение
- •Исключения
- •56. Обеспечьте бессбойную функцию обмена Резюме
- •Обсуждение
- •Исключения
- •Пространства имен и модули
- •57. Храните типы и их свободный интерфейс в одном пространстве имен Резюме
- •Обсуждение
- •Примеры
- •58. Храните типы и функции в разных пространствах имен, если только они не предназначены для совместной работы Резюме
- •Обсуждение
- •59. Не используйте using для пространств имен в заголовочных файлах или перед директивой #include Резюме
- •Обсуждение
- •Исключения
- •60. Избегайте выделения и освобождения памяти в разных модулях Резюме
- •Обсуждение
- •61. Не определяйте в заголовочном файле объекты со связыванием Резюме
- •Обсуждение
- •Исключения
- •62. Не позволяйте исключениям пересекать границы модулей Резюме
- •Обсуждение
- •63. Используйте достаточно переносимые типы в интерфейсах модулей Резюме
- •Обсуждение
- •Примеры
- •65. Выполняйте настройку явно и преднамеренно Резюме
- •Обсуждение
- •66. Не специализируйте шаблоны функций Резюме
- •Обсуждение
- •67. Пишите максимально обобщенный код Резюме
- •Обсуждение
- •Исключения
- •Обработка ошибок и исключения
- •68. Широко применяйте assert для документирования внутренних допущений и инвариантов Резюме
- •Обсуждение
- •Примеры
- •69. Определите разумную стратегию обработки ошибок и строго ей следуйте Резюме
- •Обсуждение
- •70. Отличайте ошибки от ситуаций, не являющихся ошибками Резюме
- •Обсуждение
- •Примеры
- •71. Проектируйте и пишите безопасный в отношении ошибок код Резюме
- •Обсуждение
- •Примеры
- •72. Для уведомления об ошибках следует использовать исключения Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •73. Генерируйте исключения по значению, перехватывайте — по ссылке Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •Исключения
- •Stl: контейнеры
- •76. По умолчанию используйте vector. В противном случае выбирайте контейнер, соответствующий задаче Резюме
- •Обсуждение
- •Примеры
- •77. Вместо массивов используйте vector и string Резюме
- •Обсуждение
- •78. Используйте vector (и string::c_str) для обмена данными с api на других языках Резюме
- •Обсуждение
- •79. Храните в контейнерах только значения или интеллектуальные указатели Резюме
- •Обсуждение
- •Примеры
- •80. Предпочитайте push_back другим способам расширения последовательности Резюме
- •Обсуждение
- •Исключения
- •81. Предпочитайте операции с диапазонами операциям с отдельными элементами Резюме
- •Обсуждение
- •Примеры
- •82. Используйте подходящие идиомы для реального уменьшения емкости контейнера и удаления элементов Резюме
- •Обсуждение
- •Исключения
- •Stl: алгоритмы
- •83. Используйте отладочную реализацию stl Резюме
- •Обсуждение
- •Примеры
- •84. Предпочитайте вызовы алгоритмов самостоятельно разрабатываемым циклам Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •85. Пользуйтесь правильным алгоритмом поиска Резюме
- •Обсуждение
- •86. Пользуйтесь правильным алгоритмом сортировки Резюме
- •Обсуждение
- •Примеры
- •Исключения
- •87. Делайте предикаты чистыми функциями Резюме
- •Обсуждение
- •Примеры
- •88. В качестве аргументов алгоритмов и компараторов лучше использовать функциональные объекты, а не функции Резюме
- •Обсуждение
- •89. Корректно пишите функциональные объекты Резюме
- •Обсуждение
- •Безопасность типов
- •90. Избегайте явного выбора типов — используйте полиморфизм Резюме
- •Обсуждение
- •Примеры
- •91. Работайте с типами, а не с представлениями Резюме
- •Обсуждение
- •92. Избегайте reinterpret_cast Резюме
- •Обсуждение
- •Исключения
- •93. Избегайте применения static_cast к указателям Резюме
- •Обсуждение
- •94. Избегайте преобразований, отменяющих const Резюме
- •Обсуждение
- •Исключения
- •95. Не используйте преобразование типов в стиле с Резюме
- •Обсуждение
- •96. Не применяйте memcpy или memcmp к не-pod типам Резюме
- •Обсуждение
- •97. Не используйте объединения для преобразований Резюме
- •Обсуждение
- •Исключения
- •99. Не используйте недействительные объекты и небезопасные функции Резюме
- •Обсуждение
- •100. Не рассматривайте массивы полиморфно Резюме
- •Обсуждение
- •Список литературы
- •Резюме из резюме
- •8. Не оптимизируйте преждевременно
- •15. Активно используйте const
- •23. Делайте заголовочные файлы самодостаточными
- •36. Предпочитайте предоставление абстрактных интерфейсов
- •61. Не определяйте в заголовочном файле объекты со связыванием
- •62. Не позволяйте исключениям пересекать границы модулей
- •63. Используйте достаточно переносимые типы в интерфейсах модулей
- •70. Отличайте ошибки от ситуаций, не являющихся ошибками
- •71. Проектируйте и пишите безопасный в отношении ошибок код
- •72. Для уведомления об ошибках следует использовать исключения
- •73. Генерируйте исключения по значению, перехватывайте — по ссылке
- •85. Пользуйтесь правильным алгоритмом поиска
- •86. Пользуйтесь правильным алгоритмом сортировки
- •87. Делайте предикаты чистыми функциями
- •88. В качестве аргументов алгоритмов и компараторов лучше использовать функциональные объекты, а не функции
85. Пользуйтесь правильным алгоритмом поиска Резюме
Данная рекомендация применима к поиску определенного значения в диапазоне. При поиске в неотсортированном диапазоне используйте алгоритмы find/find_if или count/count_if. Для поиска в отсортированном диапазоне выберите lower_bound, upper_bound, equal_range или (реже) binary_search. (Вопреки своему имени, binary_search обычно — неверный выбор.)
Обсуждение
В случае неотсортированных диапазонов, find/find_if и count/count_if могут за линейное время определить, находится ли данный элемент в диапазоне, и если да, то где именно. Заметим, что алгоритмы find/find_if обычно более эффективны, поскольку могут завершить поиск, как только искомый элемент оказывается найден.
В случае сортированных диапазонов лучше использовать алгоритмы бинарного поиска — binary_search, lower_bound, upper_bound и equal_range, которые имеют логарифмическое время работы. Увы, несмотря на свое красивое имя, binary_search практически всегда бесполезен, поскольку возвращает всего лишь значение типа bool, указывающее, найден искомый элемент или нет. Обычно вам требуется алгоритм lower_bound или upper_bound, или equal_range, который выдает результаты обоих алгоритмов — и lower_bound, и upper_bound (и требует в два раза больше времени).
Алгоритм lower_bound возвращает итератор, указывающий на первый подходящий элемент (если таковой имеется) или на позицию, где он мог бы быть (если такого элемента нет); последнее полезно для поиска верного места для вставки новых значений в отсортированную последовательность. Алгоритм upper_bound возвращает итератор, указывающий на элемент, следующий за последним найденным элементом (если таковой имеется), т.е. на позицию, куда можно добавить следующий эквивалентный элемент; это полезно при поиске правильного места для вставки новых значений в отсортированную последовательность, чтобы поддерживать упорядоченность, при которой равные элементы располагаются в последовательности в порядке их вставки.
Для сортированных диапазонов в качестве быстрой версии count(first, last, value); лучше использовать пару вызовов:
p = equal_range(first, last, value);
distance(p.first, p.second);
При поиске в ассоциативном контейнере лучше использовать вместо алгоритмов-не членов функции-члены с тем же именем. Функции-члены обычно более эффективны; например, функция-член count выполняется за логарифмическое время (так что, кстати, нет никаких оснований заменять ее вызовом equal_range с последующим distance, что имеет смысл для функции count, не являющейся членом).
Ссылки
[Austern99] §13.2-3 • [Bentley00] §13 • [Meyers01] §34, §45 • [Musser01] §22.2 • [Stroustrup00] §17.1.4.1, §18.7.2
86. Пользуйтесь правильным алгоритмом сортировки Резюме
При сортировке вы должны четко понимать, как работает каждый из сортирующих алгоритмов, и использовать наиболее дешевый среди тех, которые пригодны для решения вашей задачи.
Обсуждение
Вам не всегда требуется полный sort; обычно надо меньшее, и весьма редко — большее. В общем случае стандартные алгоритмы сортировки располагаются от наиболее дешевых до наиболее дорогих в следующем порядке: partition, stable_partition, nth_element, partial_sort (и его вариант partial_sort_copy), sort и stable_sort. Используйте наименее дорогой из алгоритмов, которые выполняют необходимую вам работу; применение излишне мощного алгоритма — расточительство.
Время работы алгоритмов partition, stable_partition и nth_element — линейное, что является очень хорошим показателем.
Алгоритмы nth_element, partial_sort, sort и stable_sort требуют итераторы произвольного доступа. Вы не можете использовать их при наличии только двунаправленных итераторов (например, list<T>::iterator). Если вам нужны данные алгоритмы, но у вас нет итераторов произвольного доступа, вы можете воспользоваться идиомой индексного контейнера: создайте контейнер, поддерживающий итераторы произвольного доступа (например, vector), в котором будут храниться итераторы, указывающие на элементы интересующего вас диапазона, и затем примените к нему более мощный алгоритм с использованием разыменовывающей версии вашего предиката (в которой перед обычным сравнением выполняется разыменование итераторов).
Версии stable_… следует применять только тогда, когда вам необходимо сохранить относительный порядок одинаковых элементов. Заметим, что алгоритмы partial_sort и nth_element не являются устойчивыми (т.е. они не оставляют одинаковые элементы в том же относительном порядке, в котором они находились до сортировки), и у них нет стандартизированных устойчивых версий. Если вам все же требуется сохранение относительной упорядоченности элементов, вероятно, вам надо использовать stable_sort.
Само собой разумеется, не следует прибегать ни к каким алгоритмам сортировки, если вы можете обойтись без них. Если вы пользуетесь стандартным ассоциативным контейнером (set/multiset или map/multimap) или адаптером priority_queue, и вам требуется только один порядок сортировки, то не забывайте, что элементы в этих контейнерах всегда находятся в отсортированном виде.