Главная » C++, C++ Builder » Всемогущее множество STL

0

Следующий класс, который мы собираемся исследовать в нашем обзоре STL — класс set (множество). Этот класс представляет собой реализацию математического понятия множества. Множество содержит одиночные элементы данного вида; в нем не может быть двух и более элементов с одинаковыми значениями. Для использования этого класса вам нужно подключить в проект заголовочный файл <set>:

#include <set>

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

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

Давайте посмотрим на методы, имеющиеся в классе set, а затем поговорим об их использовании. В табл. 5.5 приведены основные методы класса set в STL.

Таблица 5.5 Важные методы класса set

begin

Возвращает начальную позицию множества (первый элемент)

end

Возвращает последнюю позицию множества (последний элемент)

count

Возвращает количество элементов в множестве, подходящих под заданный критерий

empty

Указывает, есть (TRUE) или нет (FALSE) элементов в множестве

insert

Добавить элемент в множество, если это возможно. Если такой элемент уже есть, то новый добавлен не будет

erase

Удаляет элемент из множества, если он там есть. Если такого элемента нет, то с множеством ничего не происходит

size

Возвращает количество элементов в множестве

find

Возвращает первый же элемент, подходящий под заданный критерий или пустой элемент (NULL),

если такого элемента нет

lower_bound

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

upper_bound

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

rbegin

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

rend

Возвращает первый элемент

includes

Проверяет, не является ли множество подмножеством другого

set_union

Возвращает объединение двух множеств

set_intersection

Возвращает пересечение двух множеств

set_difference

Возвращает разность двух множеств (элементы одного множества, не присутствующие в другом)

accumulate

Урезает множество до одного значения

count_if

Возвращает количество элементов, удовлетворяющих заданному условию

swap

Обменивает элементы (сразу все) между множествами

operator=

Копирует элементы из одного множества в другое (делает точную копию)

Вот пример использования множества. В данном примере мы получаем от пользователя значения (строки) и пытаемся добавить их в множество. Если значение не добавляется, мы выводим сообщение об ошибке и продолжаем работу. Процесс повторяется, пока пользователь не введет специальное значение (DONE), которое означает, что ввод данных завершен. Тогда мы выводим список значений, которые были добавлены в множество. Для создания этой программы выберите в CBuilder новый проект консольного приложения и введите следующий код в исходный файл (project1.cpp):

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <set>

#include <string>

int main(void)

{

// Определяем используемый объект множество

std::set<std::string, less<std::string> > setString;

// В цикле пытаемся добавить элементы,

//введенные пользователем

int bDone = FALSE;

while  (!bDone )

{

// Получаем информацию от пользователя

printf("Введите значение для поиска

(DONE для выхода):");

// Храним результат в строке char szBuffer[256]; gets(szBuffer);

// Проверяем, не пора ли выходить

if  (!stricmp(szBuffer, "done") )

{

bDone = TRUE; continue;

}

// Пытаемся добавить элемент в множество int bOkToAdd = setString.insert (szBuffer ); if  (bOkToAdd == FALSE)

{

printf("Не добавляется:

такой элемент уже есть!\n");

}

}

// Когда ввод завершен, выводим все элементы

std::set<std::string, std::less<std::string> >::

iterator setIterator; setIterator = setString.begin();

// Проходим по всем значениям

while  (setIterator != setString.end() )

{

printf("Элемент: %s\n", (*setIterator).c_str() );

}

return 0;

}

В данном примере есть несколько интересных моментов. Во-первых, здесь не применяется конструкция using namespace std, которую использовали вплоть до этой точки при работе с STL. Для этого есть причины: во-первых, выражение using применять не обязательно, это просто более удобный способ распознавания областей видимости.  Вам  действительно  нужно  научиться работать с областями namespace, которые мы рассмотрим подробнее ниже.

Вторым интересным моментом является то, что множество — не более чем обычная структура данных. Вы можете добавлять в него данные и определять итератор (iterator) для него. Это важно, так как слишком много программистов, судя по всему, считают, что  множество  можно использовать только  для проверки, есть ли в нем некоторый элемент. Класс iterator работает с множеством точно также, как и с любой другой структурой в классах STL.

И, наконец, последний момент заключается в том, что мы использовали саму структуру данных для проверки корректности ввода. В основном классы, определяющие структуры  данных  (  list, vector и т.д.) не имеют никаких встроенных проверок. Пользователь может набрать одну и ту же строку два раза, и классы list и vector радостно поместят оба экземпляра в конец списка (массива). В классах же set и map (который мы рассматривали в предыдущем примере) хранятся только уникальные значения. Также как и у класса map, у класса set есть кровный брат — класс multiset (мультимножество), в котором можно хранить несколько одинаковых элементов. Но такое чудо используется крайне редко, так как для подобных вещей лучше подходят другие структуры данных, например список ( list).

Источник: Теллес М. – Borland C++ Builder. Библиотека программиста – 1998

По теме:

  • Комментарии