Стандарты программирования на С++. 101 правило и рекомендация - [78]
, >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
). Если вам нужны данные алгоритмы, но у вас нет итераторов произвольного доступа, вы можете воспользоваться идиомой индексного контейнера: создайте контейнер, поддерживающий итераторы произвольного доступа (например, vector), в котором будут храниться итераторы, указывающие на элементы интересующего вас диапазона, и затем примените к нему более мощный алгоритм с использованием разыменовывающей версии вашего предиката (в которой перед обычным сравнением выполняется разыменование итераторов).
Версии >stable_
… следует применять только тогда, когда вам необходимо сохранить относительный порядок одинаковых элементов. Заметим, что алгоритмы >partial_sort
и >nth_element
не являются устойчивыми (т.е. они не оставляют одинаковые элементы в том же относительном порядке, в котором они находились до сортировки), и у них нет стандартизированных устойчивых версий. Если вам все же требуется сохранение относительной упорядоченности элементов, вероятно, вам надо использовать >stable_sort
.
Само собой разумеется, не следует прибегать ни к каким алгоритмам сортировки, если вы можете обойтись без них. Если вы пользуетесь стандартным ассоциативным контейнером (>set
/>multiset
или >map
/>multimap
) или адаптером >priority_queue
, и вам требуется только один порядок сортировки, то не забывайте, что элементы в этих контейнерах всегда находятся в отсортированном виде.
Пример 1. >partition
. Если вам надо разделить весь диапазон на две группы (группа элементов, удовлетворяющих предикату, за которыми следует группа элементов, предикату не удовлетворяющих), то для этого достаточно воспользоваться алгоритмом >partition
. Это все, что вам надо, чтобы ответить на вопросы наподобие приведенных далее.
• Кто из студентов имеет средний бал не ниже 4.5? Для ответа на этот вопрос можно воспользоваться вызовом >partition(students.begin(), students.end(), GradeAtLeast(4.5));
, который вернет итератор, указывающий на первого студента, чей средний балл ниже 4.5.
• Какие из товаров имеют вес менее 10 кг? Вызов >partition(products.begin(), products.end(), WeightUnder(10));
вернет итератор, указывающий на первый товар, вес которого не ниже 10 кг.
Пример 2. >nth_element
. Алгоритм >nth_element
можно использовать для того, чтобы получить один элемент в корректной n-й позиции, в которой он бы находился при полной сортировке всего диапазона, при этом все прочие элементы корректно располагаются до или после этого n-го элемента. Этого достаточно, чтобы ответить на вопросы наподобие следующих.

Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)

Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.

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

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

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

Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.