Контейнеры STL

в этой главе, которая продолжает тему, начатую в главе 5, приведены подробные описания контейнеров STL. Начинается она с обзора общих возможностей и операций всех контейнерных классов, после чего каждый контейнерный класс рассматривается в отдельности. В каждом случае представлены внутренние структуры данных, основные операции контейнера и их эффективность. Также показано, как использовать различные операции контейнера; нетривиальные случаи поясняются примерами. Кроме того, типичными примерами использования контейнеров завершаются все разделы, посвященные конкретным контейнерам. Далее обсуждается интересный вопрос: в каких ситуациях следует применять тот или иной контейнер? Сравнительный анализ общих возможностей, достоинств и недостатков разных типов контейнеров поможет подобрать оптимальный контейнер для конкретной ситуации. Глава завершается подробным описанием всех членов контейнерных классов. Это описантге было задумано как своего рода справочное руководство. В нем перечислены все нюансы интерфейса контейнера и приводятся точные сигнатуры всех коитейнерпых операций. Там, где это уместно, приводятся перекрестные ссылки на похожие или вспомогательные алгоритмы.

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

Общие возможности и операции Общие возможности контейнеров

Здесь сформулированы общие возможности всех контейнерных классов STL. В большинстве случаев речь идет о требованиях, которые должны выполняться всеми контейнерами STL. Ниже перечислены три основных требования.

Традициомно коитейперпые адаптеры считаются частью STL. Тем ие мепее на концептуальном уроппе адаптер]]] не входят и иерархию STL, а <;все[-о лишь используют ее.

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

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

О В общем случае операции с элементами контейнеров небезопасны. Вызывающая сторона должна проследить за тем, чтобы параметры операции соответствовали требованиям. Нарушение правил (например, использование недействительного индекса) приводит к непредсказуемым последствиям. Обычно STL пе генерирует исключений в своем коде. Но если исключение генерируется пользовательскими операциями, вызываемыми контейнером STL, ситуация меняется. За подробностями обращайтесь на с. 148.

Общие операции над контейнерами

в табл. 6.1 перечислены операции, общие для всех контейнеров. Общие операции подчиняются правилам, упомянзпгым в предыдущем подразделе. Некоторые из них более подробно описаны далее.

продолжение

Таблица 6.1 (продолжение)

Операция

Описание

с1 < с2 с1 > с2 с1 <= с2 с1 >= с2 с1 = с2 cl.swap(c2) swap(cl,c2) с. beginO c.endO c.rbeginO

c.rendO

c.insert(pos,elem)

c.erase(beg,end)

c.clearO

c.get allocator()

Проверяет, что cl меньше c2

Проверяет, что cl больше c2 (эквивалент c2<cl)

Проверяет, что cl не больше с2 (эквивалент !(с2<с1))

Проверяет, что cl не меньше с2 (эквивалент !(с1<с2))

Присваивает с1 все элементы с2

Меняет местами содержимое с1 и с2

То же, но в форме глобальной функции

Возвращает итератор для первого элемента

Возвращает итератор для позиции за последним элементом

Возвращает обратный итератор для первого элемента при переборе в обратном направлении

Возвращает обратный итератор для позиции за последним элементом при переборе в обратном направлении

Вставляет копию elem (с разными вариантами возвращаемого значения и интерпретацией первого аргумента)

Удаляет все элементы из интервала [beg,end) (некоторые контейнеры возвращают следующий элемент после удаленного интервала)

Удаляет из контейнера все элементы (контейнер остается пустым)

Возвращает модель памяти контейнера

Инициализация

Любой контейнерный класс содержит конструктор по умолчанию, копирующий конструктор и деструктор. Кроме того, предусмотрена возможность инициализации контейнера элементами из заданного интервала. Соответствующий конструктор позволяет инициализировать контейнер элементами другого контейнера, массива или просто элементами, прочитанными из стандартного входного потока данных. Такие конструкторы оформляются в виде шаблонных функций класса (см. с. 28), поэтому различия возможны не только в типе контейнера, по и в типе элементов (при условии автоматического преобразования исходного типа элемента к итоговому типу). Несколько примеров инициализации:

О Ишшиализация элементами другого контейнера:

std:;l1st<1nt> 1: 1 - связанный список int

Копирование всех элементов списка в вектор с приведением к типу float std::vector<float> с(1.begin(),1.end());

Если система не поддерживает шаблошхые функции классов, обычно разрешается инициализация только при [10ЛИОМ соответствии типов. В таких случаях можно воспользоваться алгоритмом сору(). Пример приведен на с. 196.