Функция insertO пытается вставить элемент в контейнер; если элемент с таким значением уже присутствует, попытка игнорируется. Чаще всего операции с множествами ограничиваются вставкой и проверкой наличия элемента в множестве. Кроме того, можно вычислить объединение, пересечение или разность двух множеств, а также проверить, является ли одно множество подмножеством другого. В нашем примере значения 0-9 вставляются в множество 25 раз, но принимаются только 10 уникальных значений.

Теперь попробуем приспособить программу Intset.cpp для вывода списка слов, использованных в документе. Решение оказывается на удивление простым:

: C07:WordSet.cpp linclude <fstream> linclude <iostream> linclude <iterator> linclude <set> linclude <string> linclude . ./require.h using namespace std;

void wordSetCchar* fileName) { ifstream source(fileName); assure(source. fileName); string word; set<string> words; while(source word)

words.insert(word); copy(words.begin(). words.endO,

ostream iterator<string>(cout. \n )); cout Number of unique words;

words.SizeO endl;

int main(int argc. char* argv[]) { if(argc > 1)

wordSet(argv[l]); else

wordSet( WordSet.cpp ); } III:-

Единственное принципиальное различие состоит в том, что в новой версии программы множество содержит строки вместо целых чисел. Слова читаются из файла, но остальные операции сходны с теми, которые использовались в программе Intset.cpp. В выходных данных отсутствуют дубликаты, а вследствие особенностей реализации множеств слова автоматически сортируются.

Множество относится к числу ассоциативных контейнеров - одной из трех категорий контейнеров стандартной библиотеки С++. Эти категории и входящие в них контейнеры перечислены ниже:

последовательные контейнеры - vector, list, deque;

контейнерные адаптеры - queue, stack, priority queue;

ассоциативные контейнеры - set, map, multiset, multimap.

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

ность элементов требуется наделить особыми свойствами, именно для этой цели предназначены контейнерные адаптеры - они моделируют такие абстрактные структуры данных, как очередь и стек. В ассоциативных контейнерах данные упорядочиваются по ключу, что обеспечивает быструю выборку данных.

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

Вектор, как вы уже знаете, представляет собой линейную последовательность с произвольным доступом к элементам. Тем не менее, вставка элемента в середину контейнера, хранящегося в памяти в виде непрерывного блока, обходится достаточно дорого; это относится и к векторам, и к массивам. Дек (deque, сокращение от double-ended queue , то есть двусторонняя очередь ) также обеспечивает произвольный доступ, почти не уступающий векторам по скорости, но он гораздо быстрее работает при выделении новой памяти. Кроме того, дек обеспечивает быструю вставку новых элементов в начало и конец последовательности. Список (list) является двусвязным, поэтому перебор элементов в нем происходит медленно, но зато быстро выполняется вставка элемента в произвольной позиции. Таким образом, список, дек и вектор обладают сходной базовой функциональностью (все эти контейнеры содержат линейные последовательности элементов), но различаются по сложности выполнения операций. Если вы только осваиваете программирование с применением контейнеров, выберите один тип контейнера и пользуйтесь им, экспериментируя с остальными типами только на стадии оптимизации программы.

Для большинства задач, которые вам предстоит решать, простых последовательных контейнеров (векторов, деков и списков) будет вполне достаточно. Все три разновидности содержат функцию push back(), используемую для вставки новых элементов в конец последовательности (у деков и списков также имеется функция push front(), предназначенная для вставки элементов в начало последовательности).

Но как производится выборка элементов в последовательном контейнере? При работе с деками и векторами можно воспользоваться оператором индексирования [ ], но со списками этот способ не работает. Для обращения к элементам всех трех разновидностей последовательных контейнеров можно применять итераторы. Каждый контейнер предоставляет соответствующий тип итератора для обращения к своим элементам.

Хотя объекты хранятся в контейнерах по значению (то есть в контейнере сохраняется копия всего объекта), в некоторых ситуациях бывает удобнее хранить указатели на объекты. Такой подход позволяет заменять объекты в пределах иерархии и учитывать полиморфное поведение классов. Рассмотрим классический пример с геометрическими фигурами, для которых определен общий набор операций, а также операции, специфические для каждого конкретного класса. В следующей программе вектор STL содержит указатели на разные виды объектов Shape, созданных в куче:

: C07:Stlshape.срр

Работа с классами геометрических фигур в STL #1 nclude <vector> linclude <iostream> using namespace std:

class Shape { public:

virtual void drawO = 0:

virtual -ShapeO {}:

class Circle : public Shape { public:

void drawO { cout Circle: :draw\n : } -CircleO { cout ~Circle\n : }

class Triangle : public Shape { public:

void drawO { cout Triangle: :draw\n ; } -TriangleO { cout -TriangleVn : }

class Square : public Shape { public:

void drawO { cout Square::draw\n : } -SquareO { cout -Square\n : }

typedef std::vector<Shape*> Container: typedef Container::iterator Iter:

int mainO { Container shapes: shapes.push back(new Circle): shapes.push back(new Square): shapes.push back(new Triangle): fordter i = shapes.beginO: i != shapes.endO: i++) (*i)->draw(): ... Завершение работы с фигурами: fordter j = shapes.beginO: j != shapes.end(): j++) delete *j: } III:-

Определения классов Shape, Circle, Square и Triangle должны выглядеть вполне знакомо. Абстрактный базовый класс Shape (о чем говорит спецификатор =0) определяет интерфейс для всех разновидностей фигур. Производные классы переопределяют виртуальную функцию draw() для выполнения операции, соответствующей данному типу. Теперь мы хотим создать несколько разнотипных объектов Shape и сохранить их в контейнере STL. Рассмотрим вспомогательное определение типа

typedef std::vector<Shape*> Container:

Это определение создает синоним для вектора с элементами Shape*, а следующее определение использует его и создает другой синоним для vector<Shape*>::iterator:

typedef Container::iterator Iter:

Обратите внимание: чтобы получить правильный тип итератора, определенный в виде вложенного класса, необходимо указать имя типа контейнера. Хотя в STL существуют разные виды итераторов (прямые, двусторонние, итераторы произ-