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

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

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

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

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

Недостаточно? Данные контейнера не передаются через интерфейс С, поскольку данная возможность поддерживается только для vector(совет 16). Вы не сможете создать экземпляр контейнера с типом bool— как будет показано в совете 18, vectorне всегда ведет себя как 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 vw;

Widget bestWidget;

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

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

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

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

class Widget{...};

typedef vector WidgetContaner;

typedef WidgetContainer:.i terator WCIterator;

WidgetContanervw;

Widget bestWidget;

WCIteratori =find(vw.begin().vw.end(),bestWidget):

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