Форма входа
0/0
Эффективное использование STL - Скотт Мейерс
- Дата:20.06.2024
- Категория: Компьютеры и Интернет / Программирование
- Название: Эффективное использование STL
- Автор: Скотт Мейерс
- Просмотров:1
- Комментариев:0
Уважаемые читатели!
Тут можно читать бесплатно Эффективное использование STL - Скотт Мейерс. Жанр: Программирование. Так же Вы можете читать полную версию (весь текст) онлайн книги без регистрации и SMS на сайте Knigi-online.info (книги онлайн) или прочесть краткое содержание, описание, предисловие (аннотацию) от автора и ознакомиться с отзывами (комментариями) о произведении.
Описание онлайн-книги Эффективное использование STL - Скотт Мейерс:
В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.
Читем онлайн Эффективное использование STL - Скотт Мейерс
Шрифт:
-
+
Интервал:
-
+
Закладка:
Сделать
Несколько странно выгладит частое присутствие equal_range в столбце, относящемся к сортированным интервалам. Оно связано с особой ролью проверки эквивалентности при поиске. Использование lower_bound и upper_bound чревато ошибочной проверкой равенства, а при использовании equal_range более естественно выглядит проверка эквивалентности. Во второй строке предпочтение отдается equal_range еще по одной причине: equal_range работает с логарифмическим временем, а вызов find связан с линейными затратами времени.
Для контейнеров multiset и multimap в качестве возможных кандидатов для поиска первого объекта с заданным значением указаны два алгоритма, find и lower_bound. Обычно для решения этой задачи выбирается find — возможно, вы обратили внимание, что именно этот алгоритм указан в таблице для контейнеров set и map. Однако multi-контейнеры не гарантируют, что при наличии нескольких элементов с заданным значением find найдет первый элемент в контейнере; известно лишь то, что будет найден один из этих элементов. Если вы действительно хотите найти первый объект с заданным значением, воспользуйтесь lower_bound и выполните вручную вторую часть проверки эквивалентности, описанной в совете 19 (без этой проверки можно обойтись при помощи equal_range, но вызов equal_range обходится дороже, чем вызов lower_bound).
Выбрать между count, find, binary_search, lower_bound, upper_bound и equal_range несложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором.
Совет 46. Передавайте алгоритмам объекты функций вместо функций
Часто говорят, что повышение уровня абстракции языков высокого уровня приводит к снижению эффективности сгенерированного кода. Александр Степанов, изобретатель STL, однажды разработал небольшой комплекс тестов для оценки «платы за абстракцию» при переходе с C на C++. В частности, результаты этих тестов показали, что код, сгенерированный для работы с классом, содержащим double, почти всегда уступает по эффективности соответствующему коду, непосредственно работающему с double. С учетом сказанного вас может удивить тот факт, что передача алгоритмам объектов функций STL — то есть объектов, маскирующихся под функции, — обычно обеспечивает более эффективный код, чем передача «настоящих» функций.
Предположим, вы хотите отсортировать вектор чисел типа double по убыванию. Простейшее решение этой задачи средствами STL основано на использовании алгоритма sort с объектом функции типа greater<double>:
vector<double> v;
…
sort(v.begin(), v.end(), greater<double>());
Вспомнив о «плате за абстракцию», программист решает заменить объект функции «настоящей» функцией, которая к тому же оформлена как подставляемая (inline):
inline bool doubleGreater(double d1, double d2) {
return d1 > d2;
}
…
sort(v.begin(), v.end(), doubleGreater);
Как ни странно, хронометраж двух вызовов sort показывает, что вызов с greater<double> почти всегда работает быстрее. В своих тестах я сортировал вектор, содержащий миллион чисел типа double, на четырех разных платформах STL с оптимизацией по скорости, и версия с greater<double> всегда работала быстрее. В худшем случае выигрыш в скорости составил 50%, в лучшем он достигал 160%. Вот тебе и «плата за абстракцию»…
Факт объясняется просто. Если функция operator() объекта функции была объявлена подставляемой (явно, с ключевым словом inline, или косвенно, посредством определения внутри определения класса), большинство компиляторов благополучно подставляет эту функцию во время создания экземпляра шаблона при вызове алгоритма. В приведенном выше примере это происходит с функцией greater<double>::operator(). В результате код sort не содержит ни одного вызова функций, а для такого кода компилятор может выполнить оптимизацию, недоступную при наличии вызовов (связь между подстановкой функций и оптимизацией компиляторов рассматривается в совете 33 «Effective C++» и главах 8-10 книги «Efficient C++» [10]).
При вызове sort с передачей doubleGreater ситуация выглядит иначе. Чтобы убедиться в этом, необходимо вспомнить, что передача функции в качестве параметра другой функции невозможна. При попытке передачи функции в качестве параметра компилятор автоматически преобразует функцию в указатель на эту функцию, поэтому при вызове передается указатель. Таким образом, при вызове
sort(v.begin(), v.end(), doubleGreater);
алгоритму sort передается не doubleGreater, а указатель на doubleGreater. При создании экземпляра шаблона объявление сгенерированной функции выглядит так:
void sort(vector<double>::iterator first, // Начало интервала
vector<double>:iterator last, // Конец интервала
bool (*comp)(double, double)); // Функция сравнения
Поскольку comp является указателем на функцию, при каждом его использовании внутри sort происходит косвенный вызов функции (то есть вызов через указатель). Большинство компиляторов не пытается подставлять вызовы функций, вызываемых через указатели, даже если функция объявлена с ключевым словом inline и оптимизация выглядит очевидной. Почему? Наверное, потому, что разработчики компиляторов не считают нужным ее реализовать. Пожалейте их — народ постоянно чего-нибудь требует, а успеть все невозможно. Впрочем, это вовсе не означает, что требовать не нужно.
Подавление подстановки кода функций объясняет один факт, который кажется невероятным многим опытным программистам C: функция C++ sort почти всегда превосходит по скорости функцию C qsort. Конечно, в C++ приходится создавать экземпляры шаблонов функций и вызывать operator(), тогда как в C все ограничивается простым вызовом функции, однако все «излишества» C++ теряются во время компиляции. На стадии выполнения sort обращается к подставленной функции сравнения (при условии, что функция была объявлена с ключевым словом inline, а ее тело доступно на стадии компиляции), тогда как qsort вызывает функцию сравнения через указатель. Результат — sort работает гораздо быстрее. В моих тестах с вектором, содержащим миллион чисел double, превосходство по скорости достигало 670%, но я не призываю верить мне на слово. Вы легко убедитесь в том, что при передаче объектов функций в качестве параметров алгоритмов «плата за абстракцию» превращается в «премию за абстракцию».
Существует и другая причина для передачи объектов функций в параметрах алгоритмов, не имеющая ничего общего с эффективностью. Речь идет о компилируемости программ. По каким-то загадочным причинам некоторые платформы STL отвергают абсолютно нормальный код — это связано с недоработками то ли компилятора, то ли библиотеки, то ли и того и другого. Например, одна распространенная платформа STL отвергает следующий (вполне допустимый) фрагмент, выводящий в cout длину всех строк в множестве:
set<string> s;
…
transform(s.begin(), s.end(),
ostream_iterator<string::size_type>(cout, "n"),
mem_fun_ref(&string::size)
);
Проблема возникает из-за ошибки в работе с константными функциями классов (такими как string::size) в этой конкретной платформе STL. Обходное решение заключается в использовании объекта функции:
struct StringSize:
public_unary_function<string, string::size_type> { // См. совет 40
string::size_type operator()(const string& s) const {
return s.size();
}
};
transform (s.begin(), s.end(),
ostream_iterator<string::size_type>(cout, "n"), StringSize();
Существуют и другие обходные решения, но приведенный фрагмент хорош не только тем, что он компилируется на всех известных мне платформах STL. Он также делает возможной подстановку вызова string::size, что почти наверняка невозможно в предыдущем фрагменте с передачей mem_fun_ref(&string::size). Иначе говоря, определение класса функтора StringSize не только обходит недоработки компилятора, но и может улучшить быстродействие программы.
Другая причина, по которой объекты функций предпочтительнее обычных функций, заключается в том, что они помогают обойти хитрые синтаксические ловушки. Иногда исходный текст, выглядящий вполне разумно, отвергается компилятором по законным, хотя и неочевидным причинам. Например, в некоторых ситуациях имя экземпляра, созданного на базе шаблона функции, не эквивалентно имени функции. Пример:
На этой странице вы можете бесплатно читать книгу Эффективное использование STL - Скотт Мейерс бесплатно.
Похожие на Эффективное использование STL - Скотт Мейерс книги
- Язык программирования C++. Пятое издание - Стенли Липпман - Программирование
- Основы объектно-ориентированного программирования - Бертран Мейер - Прочая околокомпьтерная литература
- Аквариум. (Новое издание, исправленное и переработанное) - Виктор Суворов (Резун) - Шпионский детектив
- Вальтер Скотт. Собрание сочинений в двадцати томах. Том 6 - Вальтер Скотт - Историческая проза
- Стихотворения и поэмы - Юрий Кузнецов - Поэзия
