*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

четверг, 30 июля 2009 г.

Александр Степанов

Александр Степанов - это создатель STL. Ни добавить, ни отнять. Последние годы он занимается в основном преподаванием и написанием книг.

Недавно я купил его последнюю книгу "Elements of Programming".



Довольно своеобразная книга. Много математики, приводимой как обоснование тех или иных приемов в программировании (язык, конечно, С++), из-за чего читается немного тяжело. Забавно, я читал многие его публикации до этого, и как-то заметил, что чем дальше, тем больше он использует формальную математику для описания программирования.

Еще интересный факт: в данной книге везде при использовании шаблонов используются концепты, хотя недавно было принято решение, что в C++0x их не будет из-за общей пока недоработанности идеи.

Но вернемся к другим публикациям Степанова.

Одни из мои любимых - Notes for the Programming course at Adobe и Science of C++ Programming.

Например, ставший классикой, его пример на тему итераторов:
if (!v.empty()) {
sort(&*begin(), &*v.begin() + v.size());
}
когда спрашивается, почему в данном вполне рабочем примере обязательно нужна проверка v.empty() и почему нельзя второй аргумент нельзя записать как &*v.end()?

Но вот что лично мне понравилось, это способ реализации оператора присваивания для класса. Обычно, когда в классе есть конструктор копирования и оператор присваивания, стандартный прием - это сделать закрытую функцию типа clone() или copy(), которая умеет правильно копировать класс, если внутренняя его структура нетривиальна, и вызывать эту функцию из конструктора копирования и оператора присваивания, тем самым избегая дублирования кода.

Но Степанов говорит следующее: "...присваивание должно осуществляться вызовом деструктора и последующим конструктором". То есть надо просто сделать полноценный конструктор копирования, а оператор присваивание реализовать так:
T& T::operator=(const T& x) {
if (this != &x) {
this->T::~T();
new (this) T(x);
}
return *this;
}
Получается, что старый объект сам себя разрушает, вызвав деструктор (но память под ним не освобождается), а затем оператором new с явным размещением (память под объект тут уже повторно не распределяется) объект создается снова через конструктор копирования.

В общем, данные pdf-ки - очень интересное чтиво. Причем, Степанов никогда не забывает об эффективности (ибо неграмотное использования возможностей шаблонов элементарно делает программу очень медленной и жадной до ресурсов), и, например, главы про техники перемещения, а не копирования объектов очень познавательны.

12 комментариев:

  1. А расскажите про "уже ставшей классикой вопрос про итераторы"?
    Что там вообще происходит?

    ОтветитьУдалить
  2. Вы точно не описались?
    Может все же
    if (!v.empty()) {
    sort(&*v.begin(), &*v.begin() + v.size());
    }

    ОтветитьУдалить
  3. Да, это опечатка. Спасибо, исправил.

    Ну суть в том, что проверка на empty() нужна, так как если контейнер пуст, то итератор begin() будет указывать на несуществующее место в памяти со всеми вытекающими.

    Далее, писать &*end() нельзя, так как итератор end() вообще указывает не на реальное место в памяти, а "за" последний элемент. Поэтому разыменовывать его тоже нельзя.

    Вообще, суть это примера была в том, что Степанов писал, как он спорил с комитетом по стандарту, что первое: элементы вектора должны гарантированно располагаться в памяти последовательно (что делает данный пример рабочим вообще, и такое на первый взгляд кривое написание может иногда работать быстрее, чем просто "sort(v.begin(), v.end())"), и второе: для некоторых контейнеров (например, для вектора) итераторы должны быть просто указателяли.

    По первому пункту его послушали, а по второму - нет. Поэтому итератор - это не указатель, а всегда объект с перегруженным оператором '*'. Из-за чего и надо городить "&*begin()" вместо просто возможного "begin()".

    ОтветитьУдалить
  4. забавно получается.
    читаю я сейчас "Стандарты программирования C++" (в книге разбитается Coding standards, а не сам с++) Саттера и Александреску.

    В совете 56 ("Обеспечьте бессбойную функцию обмена") авторы крайне настоятельно советуют не использовать трюк с размещающим new в операторе копирования.

    А Мэйерс в "Эффективном использовании STL" рекумендует писать &v[0], нежели &*v.begin(), хотя тут конечно дело вкуса и стиля.

    Но что самое интересное, как бы я не пробовал сортировать большие (10 миллионов) вектора интов, сорт с итераторами не медленнее, а вообщем-то на пару процентов быстрее. Или в книге есть пример (и желательно компилятор), когда передача указателей быстрее?

    "Стандарты программирования С++" целиком находятся через books.google.com по названию.

    ОтветитьУдалить
  5. Я тоже читал во многих местах, что new с размещением во конструкторе копирования не стоит того, чтобы играть в эти игры. Даже в примерах самого Страуструпа я такого не видел. Везде так или иначе ручная работа, обычно через закрытую функцию copy(), которая вызывается в конструкторе копирования и операторе присваивания.

    Мне кажется, что итераторы более подвержены оптимизации. Это же классы по сути с перегружеными операторами типа "()". А так как семантика класса доступна компилятору всегда, нежели назначение какого-то указателя, то возможностей для оптимизации больше.

    Хотя мне тут приводили пример в коментах к посту про скорость указателей и функциональных объектов (http://easy-coding.blogspot.com/2009/07/blog-post_25.html), что последний GCC весьма неплохо умеет оптимизировать работу с указателями в плане подстановки их в темплейтные алгоритмы.

    ОтветитьУдалить
  6. т.е. получается, что вы со мной согласны и оба "трюка" степанова -- не самая лучшая затея?

    ОтветитьУдалить
  7. Если разбираться по делу, то тут есть только одна проблема -- конструктор (тот, что с размещением) может в принципе метнуть исключение, что приведет к полусконструированному объекту. После такой ошибки вообще нельзя дальше использовать этот объект. Если же делать вручную, то можно отловить все возможные исключения и недопустить неопределенности в состоянии. В этом случае еще можно как-то продолжать использовать этот объект. Да, присваивание дало сбой, но с этим можно жить. В случае же использования конструктора с размещением - объект надо бросать.

    Вот по этой причине лично я не использую подобные трюк в своих программах.

    ОтветитьУдалить
  8. Посоветуйте,пожалуйста,по каким параметрам можно протестировать контейнеры STL и проводились ли такие тесты?

    ОтветитьУдалить
  9. asinxron: а на предмет чего вы хотели бы их протестировать?

    ОтветитьУдалить
  10. Мне нужно сравнить функционально похожие контейнеры STL и QT (например vector Qvector),но кроме алгоритмической оценки сложности скорости основных методов ,других подходов я не нашел...

    ОтветитьУдалить
  11. Увы, у меня нет особых данных по сравнению STL и QT.

    ОтветитьУдалить