Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода

Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода

Основным принципом STL является обобщение. Массивы обобщаются в контейнеры, параметризованные по типам хранящихся объектов. Функции обобщаются в алгоритмы, параметризованные по типам используемых итераторов. Указатели обобщаются в итераторы, параметризованные по типам объектов, на которые они указывают.

Но это лишь начало. Конкретные разновидности контейнеров обобщаются в категории (последовательные и ассоциативные), а похожие контейнеры наделяются сходными функциями. Стандартные блоковые контейнеры (совет 1) обладают итераторами произвольного доступа, тогда как стандартные узловые контейнеры (также описанные в совете 1) поддерживают двусторонние итераторы. Последовательные контейнеры поддерживают операции push_front и/или push_back, у ассоциативных контейнеров такие операции отсутствуют. В ассоциативных контейнерах реализованы функции lower_bound, upper_bound и equal_range, обладающие логарифмической сложностью, а в последовательных контейнерах их нет.

При таких тенденциях к обобщению возникает естественная мысль — последовать положительному примеру. Желание похвальное. Несомненно, им стоит руководствоваться при написании собственных контейнеров, итераторов и алгоритмов, но многие программисты пытаются добиться этой цели несколько иным способом. Вместо того чтобы ориентироваться на конкретный тип контейнера, они пытаются обобщить синтаксис так, чтобы в программе, например, использовался vector, но позднее его можно было бы заменить на deque или list без изменения кода, в котором этот контейнер используется. Иначе говоря, они пытаются писать контейнерно-независимый код. Подобные обобщения, какими бы благими намерениями они не были вызваны, почти всегда нежелательны.

Даже самый убежденный сторонник контейнерно-независимого кода вскоре осознает, что универсальный код, работающий как с последовательными, так и с ассоциативными контейнерами, особого смысла не имеет. Многие функции существуют только в контейнерах определенной категории; например, функции push_front и push_back поддерживаются только последовательными контейнерами; функции count и lower_bound — только ассоциативными контейнерами и т. д. Даже сигнатуры таких базовых операций, как insert и erase, зависят от категории. Например, в последовательном контейнере вставленный объект остается в исходной позиции, тогда как в ассоциативном контейнере он перемещается в позицию, соответствующую порядку сортировки данного контейнера. Или другой пример: форма erase, которой при вызове передается итератор, для последовательного контейнера возвращает новый итератор, но для ассоциативного контейнера не возвращается ничего (в совете 9 показано, как это обстоятельство влияет на программный код).

Допустим, вас посетила творческая мысль — написать код, который работал бы со всеми распространенными последовательными контейнерами: vector, deque и list. Разумеется, вам придется программировать в контексте общих возможностей этих контейнеров, а значит, функции reserve и capacity (совет 14) использовать нельзя, поскольку они не поддерживаются контейнерами deque и list. Присутствие list также означает, что вам придется отказаться от оператора [] и ограничиться двусторонними итераторами, что исключает алгоритмы, работающие с итераторами произвольного доступа — sort, stable_sort, patial_sort и nth_element (совет 31).

С другой стороны, исходное намерение поддерживать vector исключает функции pushfront и popfont; vector и deque исключают применение splice и реализацию sort внутри контейнера. Учитывая те ограничения, о которых говорилось выше, последний запрет означает, что для вашего «обобщенного последовательного контейнера» не удастся вызвать никакую форму sort.

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

В разных последовательных контейнерах действуют разные правила недействительности итераторов, указателей и ссылок. Чтобы ваш код правильно работал с vector, deque и list, необходимо предположить, что любая операция, приводящая к появлению недействительных итераторов, указателей и ссылок в любом из этих контейнеров, приведет к тем же последствиям и в используемом контейнере. Отсюда следует, что после каждого вызова insert недействительным становится абсолютно все, поскольку deque:: insert делает недействительными все итераторы, а из-за невозможности использования capacity приходится предполагать, что после операции vector:: insert становятся недействительными все указатели и ссылки (как упоминается в совете 1, контейнер deque обладает уникальным свойством — в некоторых случаях его итераторы могут становиться недействительными с сохранением действительных указателей и ссылок). Аналогичные рассуждения приводят к выводу, что после каждого вызова erase все итераторы, указатели и ссылки также должны считаться недействительными.

Недостаточно? Данные контейнера не передаются через интерфейс С, поскольку данная возможность поддерживается только для vector (совет 16). Вы не сможете создать экземпляр контейнера с типом bool — как будет показано в совете 18, vector<bool> не всегда ведет себя как vector и никогда не хранит настоящие логические величины. Вы даже не можете рассчитывать на постоянное время вставки-удаления, характерное для list, поскольку в vector и deque эти операции выполняются с линейной сложностью.

Что же остается после всего сказанного? «Обобщенный последовательный контейнер», в котором нельзя использовать reserve, capacity, operator[], push_front, pop_front, splice и вообще любой алгоритм, работающий с итераторами произвольного доступа; контейнер, у которого любой вызов insert и erase выполняется с линейной сложностью и приводит к недействительности всех итераторов, указателей и ссылок; контейнер, несовместимый с языком С и не позволяющий хранить логические величины. Захочется ли вам использовать подобный контейнер в своем приложении? Вряд ли.

Если умерить амбиции и отказаться от поддержки 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 объясняется, почему

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

typedef vector<Widget.Specia1Anocator<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>// ClStringCompare - сравнение строк

// без учета регистра: см. совет 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.