Скотт Мейерс - Эффективное использование STL

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

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

---

Если умерить амбиции и отказаться от поддержки list, вы все равно теряете reserve, capacity, push_front и pop_front; вам также придется полагать, что вызовы insert и erase выполняются с линейной сложностью, а все итераторы, указатели и ссылки становятся недействительными; вы все равно теряете совместимость с С и не можете хранить в контейнере логические величины.

Даже если отказаться от последовательных контейнеров и взяться за ассоциативные контейнеры, дело обстоит не лучше. Написать код, который бы одновременно работал с set и map, практически невозможно, поскольку в set хранятся одиночные объекты, а в map хранятся пары объектов. Даже совместимость с set и multiset (или map и multimap) обеспечивается с большим трудом. Функция insert, которой при вызове передается только значение вставляемого элемента, возвращает разные типы для set/map и их multi-аналогов, при этом вы должны избегать любых допущений относительно того, сколько экземпляров данной величины хранится в контейнере. При работе с map и multimap приходится обходиться без оператора [], поскольку эта функция существует только в map.

Согласитесь, игра не стоит свеч. Контейнеры действительно отличаются друг от друга, обладают разными достоинствами и недостатками. Они не были рассчитаны на взаимозаменяемость, и с этим фактом остается только смириться. Любые попытки лишь искушают судьбу, а она этого не любит.

Но рано или поздно наступит день, когда окажется, что первоначальный выбор контейнера был, мягко говоря, не оптимальным, и вы захотите переключиться на другой тип. При изменении типа контейнера нужно не только исправить ошибки, обнаруженные компилятором, но и проанализировать весь код, где он используется, и разобраться, что следует изменить в свете характеристик нового контейнера и правил перехода итераторов, указателей и ссылок в недействительное состояние. Переходя с vector на другой тип контейнера, вы уже не сможете рассчитывать на С-совместимую структуру памяти, а при обратном переходе нужно проследить за тем, чтобы контейнер не использовался для хранения bool.

Если вы знаете, что тип контейнера в будущем может измениться, эти изменения можно упростить обычным способом — инкапсуляцией. Одно из простейших решений основано на использовании определений typedef для типов контейнера и итератора. Следовательно, фрагмент

class Widget{...};

vector<Widget> vw;

Widget bestWidget;

… // Присвоить значение bestWidget

vector<Widget>::iterator i = // Найти Widget с таким же значением,

 find(vw.begin(),vw.end().bestWidget) // как у bestWidget

записывается в следующем виде:

class Widget{...};

typedef vector<Widget> WidgetContaner;

typedef WidgetContainer:iterator WCIterator;

WidgetContaner vw;

Widget bestWidget;

…

WCIterator i = find(vw.begin().vw.end(),bestWidget);

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

class Widget{...};

template<typename T> // В совете 10 объясняется, почему

SpecialAllocator{...}; // необходимо использовать шаблон

typedef vector<Widget, SpecialAllocator<Widget> WidgetContainer;

typedef WidgetContainer::iterator WCIterator;

WidgetContainer vw;// Работает

Widget bestWidget;

WCIterator i=find(vw.begin().vw.end().bestWidget); // Работает

Даже если вас не интересуют аспекты typedef, связанные с инкапсуляцией, вы наверняка оцените экономию времени. Предположим, у вас имеется объект типа

map<string,

 vector<Widget>::iterator,

 CIStringCompare> // CIStringCompare - сравнение строк

                  // без учета регистра: см. совет 19

и вы хотите перебрать элементы множества при помощи const_iterator. Захочется ли вам вводить строку

map<string.vector<Widget>::iterator, CIStringCompare>::const_iterator

больше одного раза? После непродолжительной работы в STL вы поймете, что typedef — ваш друг.

Typedef всего лишь определяет синоним для другого типа, поэтому инкапсуляция производится исключительно на лексическом уровне. Она не помешает клиенту сделать то, что он мог сделать ранее (и не позволит сделать то, что было ранее недоступно). Если вы захотите ограничить зависимость клиента от выбранного типа контейнера, вам понадобятся более серьезные средства — классы.

Чтобы ограничить объем кода, требующего модификации при замене типа контейнера, скройте контейнер в классе и ограничьте объем информации, доступной через интерфейс класса. Например, если вам потребуется создать список клиентов, не используйте класс list напрямую, определите класс CustomerList и инкапсулируйте list в его закрытой части:

class CustomerList {

private:

 typedef list<Customer> CustomerContainer;

 typedef CustomerContainer::iterator CCIterator;

 CustomerContainer customers:

public: // Объем информации, доступной

 …      // через этот интерфейс, ограничивается

};

На первый взгляд происходящее выглядит глупо. Ведь список клиентов — это список, не правда ли? Вполне возможно. Но в будущем может оказаться, что возможность вставки-удаления в середине списка используется не так часто, как предполагалось вначале, зато нужно быстро выделить 20% клиентов с максимальным объемом сделок — эта задача просто создана для алгоритма nthelement (совет 31). Однако nthelement требует итератора произвольного доступа и не будет работать с контейнером list. В этой ситуации «список» лучше реализовать на базе vector или deque.

Рассматривая подобные изменения, необходимо проанализировать все функции класса CustomerList, а также всех «друзей» (friend) и посмотреть, как на них отразится это изменение (в отношении быстродействия, недействительности итераторов/указателей/ссылок и т. д.), но при грамотной инкапсуляции деталей реализации CustomerList это изменение практически не повлияет на клиентов CustomerList.

Совет 3. Реализуйте быстрое и корректное копирование объектов в контейнерах

В контейнерах хранятся объекты, но не те, которые вы им передаете. Более того, при получении объекта из контейнера вам предоставляется не тот объект, который находился в контейнере. При включении объекта (вызовом insert, push_back и т. д.) в контейнер заносится копия указанного объекта. При получении объекта из контейнера (например, вызовом front или back) вы также получаете копию. Копирование на входе, копирование на выходе — таковы правила STL.

Но и после того, как объект окажется в контейнере, он может участвовать в операциях копирования. В результате вставки или удаления элементов в vector, string и deque существующие элементы контейнера обычно перемещаются (копируются) в памяти (советы 5 и 14). Алгоритмы сортировки (совет 31), next_permutation и previous_permutation; remove, unique и их родичи (совет 32); rotate и reverse — все эти операции приводят к копированию объектов. Да, копирование объектов действительно занимает очень важное место в STL.

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

class Widget{

public:

 Widget(const Widget&):// Копирующий конструктор

 Widget& operator=(const Widget&);// Копирующий оператор присваивания

 …

};

Как обычно, если вы не объявите эти функции самостоятельно, компилятор сделает это за вас. Встроенные типы (int, указатели и т. д.) копируются простым копированием их двоичного представления. Копирующие конструкторы и операторы присваивания описаны в любом учебнике по C++. В частности, эти функции рассмотрены в советах 11 и 27 книги «Effective C++».

Теперь вам должен быть ясен смысл этого совета. Если контейнер содержит объекты, копирование которых сопряжено с большими затратами, простейшее занесение объектов в контейнер может заметно повлиять на скорость работы программы. Чем больше объектов перемещается в контейнере, тем больше памяти и тактов процессора расходуется на копирование. Более того, у некоторых объектов само понятие «копирование» имеет нетрадиционный смысл, и при занесении таких объектов в контейнер неизменно возникают проблемы (пример приведен в совете 8).