Эффективное использование STL
вернуться

Мейерс Скотт
Шрифт:

В разных последовательных контейнерах действуют разные правила недействительности итераторов, указателей и ссылок. Чтобы ваш код правильно работал с

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

Недостаточно? Данные контейнера не передаются через интерфейс C, поскольку данная возможность поддерживается только для

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 объясняется, почему

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

typedef vector<Widget, SpecialAllocator<Widget> WidgetContainer;