Поиск подстрок

Для поиска подстрок в классе string предусмотрено большое разнообразие функций. Рассмотрим некоторые их них:

size_type find (const string & str, size_type pos = 0) const;

ищет самое левое вхождение строки str в вызывающую строку, начиная с позиции pos, и возвращает позицию в строке или число npos (максимальное число типа size_type), если строка не найдена.

size_type find (const char с, size_type pos = 0) const;

ищет самое левое вхождение символа c в вызывающую строку, начиная с позиции pos, и возвращает позицию в строке или число npos, если строка не найдена.

size_type rfind (const string & str, size_type pos = npos) const;

ищет самое правое вхождение строки str в вызывающую строку до позиции pos и возвращает позицию в строке или число npos, если строка не найдена.

size_type rfind (const char c, size_type pos = 0) const;

ищет самое правое вхождение символа c в вызывающую строку, до позиции pos и возвращает позицию в строке или число npos, если строка не найдена.

Примеры

int i, j;

string s1 ("лесная королева"), s2 ("ле");

i = s1.find (s2);

j = s1.rfind (s2);

cout << “Первое вхождение S2 в S1 ” << i<< endl;

cout << “Последнее вхождение S2 в S1 “ << j<< endl;

На экране получится:

Первое вхождение S2 в S1 0

Последнее вхождение S2 в S1 11

Сравнение частей строк

Для сравнения частей строк используется функция compare (для сравнения строк целиком применяются перегруженные операции отношения):

int compare (const string & str) const;

int compare (size_type pos1, size_type n1, const string & str) const;

int compare (size_type pos1, size_type n1, const string & str, size_type pos2, size_type n2) const;

Первая форма функции сравнивает две строки целиком и возвращает значение меньше нуля, если вызывающая строка «меньше» str, равное нулю, если строки одинаковы, и больше нуля, если вызывающая строка «больше». Здесь «больше» или «меньше» означает сравнение букв по старшинству (порядку), т. е. «aa» и «aa» равны, «аб» и «ав» – вторая строка «больше» и т. п.

Вторая форма функции выполняет аналогичные действия, но сравнивает со строкой str n1 символов вызывающей строки, начиная с позиции pos1.

Третья форма функции сравнивает n1 символов вызывающей строки, начиная с позиции pos1, с подстрокой строки str длиной n2 символов, начиная с позиции pos2.

Получение характеристик строк

В классе string определено несколько методов, позволяющих получить длину строки и объем памяти, занимаемый объектом:

size_type size ( ) const; // количество элементов строки

size_type length ( ) const; // количество элементов строки

size_type max_size ( ) const; // максимальная длина строки

size_type capacity ( ) const; // объем памяти, занимаемый строкой

bool empty ( ) const; // истина, если строка пустая

Пример

string s("aaaaa");

cout << s.size( ) << endl; // выводим длину строки

Задание

Перепишите вашу программу – текстовый редактор с использованием класса string.

Контейнерные классы

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

Использование контейнеров позволяет значительно повысить надежность программ, их переносимость и универсальность, а также уменьшить сроки их разработки. Данная возможность реализуется с помощью шаблонов классов (см. приложения 1 и 2), поэтому часть библиотеки С++, в которую входят контейнерные классы, а также алгоритмы и итераторы, называют стандартной библиотекой шаблонов (STL).

Недостаток использования этой технологии – снижение быстродействия программ.

STL содержит контейнеры, реализующие основные структуры данных, используемые программами: векторы, двусторонние очереди, списки и их разновидности, словари и множества. Контейнеры можно разделить на два типа: последовательные и ассоциативные. Последовательные контейнеры обеспечивают хранение конечного количества однотипных величин в виде непрерывной последовательности. К ним относятся векторы (vector), двусторонние очереди (deque) и списки (list), а также так называемые адаптеры контейнеров – стеки (stack), очереди (queue) и очереди с приоритетом (priority-queue).

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

Ассоциативные контейнеры обеспечивают быстрый доступ к данным по ключу. Эти контейнеры построены на основе сбалансированных деревьев. Существует пять типов ассоциативных контейнеров: словари (map), словари с дубликатами(multimap), множества (set), множества с дубликатами (multiset) и битовые множества (bitset).

Практически в любом контейнерном классе определены поля следующих

типов (табл. 6).

Таблица 6

Основные поля контейнерных классов

Поле	Пояснение
value_type	Тип элемента контейнера
size_type	Тип индексов, счетчиков элементов и т.д.
iterator	Итератор
const_iterator	Константный итератор
reverse_iterator	Обратный итератор
const_ reverse_iterator	Константный обратный итератор
reference	Ссылка на элемент
const_ reference	константная ссылка на элемент
key_type	Тип ключа (для ассоциативных контейнеров)
key_compare	Тип критерия сравнения (для ассоциативных контейнеров)

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

Таблица 7

Методы, обеспечивающие доступ к элементам

Метод	Пояснение
iterator begin ( ), const_ iterator begin ( ) const	Указывает на первый элемент
iterator end ( ), const_ iterator end ( ) const	Указывает на элемент, следующий за последним
reverse_iterator rbegin ( ), const_reverse_iterator rbegin ( ) const	Указывает на первый элемент в обратной последовательности
reverse_iterator rend ( ), const_reverse_iterator rend ( ) const	Указывает на элемент, следующий за последним в обратной последовательности

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

Таблица 8

Методы, позволяющие получить информацию о размере контейнера

Метод	Пояснение
size( )	Число элементов
max_size( )	Максимальный размер контейнера
empty( )	Булевая функция, указывающая, пуст ли контейнер

Библиотека STL определяется в тринадцати заголовочных файлах:

<algoritm> <deque> <functional> <iterator> <list> <map> <memory> <numeric> <queue> <set> <stack> <utility> <vector>