Библиотека STL (Standart Template Library)
Страница 12. Некоторые преимущества класса set


Некоторые преимущества класса set

Прежде всего - здравствуйте. Ну, если вы все-таки читаете этот шаг, значит либо вы - Каев Артем, либо Артем счел мой скромный мысленный напряг достойным того, чтобы повесить его в своем разделе, что, конечно же, весьма и весьма приятно.

Итак, класс set. Данный шаг, конечно же, не ставит своей целью охватить все возможности класса. Просто мне хотелось немного поговорить о тех его свойствах, которые кажутся мне интересными и довольно-таки часто оказывались мне полезны.

Но сначала. Возможно, я немного повторю Артема если скажу: set или, говоря языком математики, множество, представляет собой объект, контролирующий произвольной длины последовательность уникальных элементов какого-либо типа. В общем, классический подход ко множеству такой: set используется для хранения неповторяющихся (уникальных) ключей, либо для проверки, есть ли элемент в наборе данных.

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

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

Но вот в чем возникла загвоздочка: в любой функции по опреденению не может быть повторяющихся абсцисс (то есть иксов с разными игреками). Что делать? Писать проверочку ручками (да и сортировать вдобавок!) - брала тоска. Выход я нашел такой (привожу пример, конечно же, сильно упрощенный):

1. Создайте проект Win32 Console Application (пустой). Назовем, например, set_test.

2. В нем создайте два файла: заголовок (set_test.h) и cpp-шник (соответственно, set_test.cpp). Хотя можете, конечно, хранить все в одном: проект маленький.

3. В заголовке (set_test.h) напишите:

#include <set> // это подключаем класс множеств
#include <iostream.h> // консольный ввод/вывод - он нам понадобится
#include <windows.h> // для MessageBox - лень задавать вопросы через
// консоль - вы меня поймете

using namespace std; // подключаем STL-ное пространство имен - как иначе?

// Это класс точки. Не мудрствуя лукаво, я назвал его stl_point.
// Всякие конструкторы копий мне не нужны - вот и не пишу :)


class stl_point
{
public:
double x, y;// собственно, абсцисса и ордината нашей точки
// ну и конструктор, поприветствуем:

stl_point(double tx=0, double ty=0)
{
x = tx;
y = ty;
}
};

// Теперь самое интересное. Перегружаем оператор "меньше":

bool operator<(stl_point first, stl_point second)
{
return first.x < second.x;
}

Что сие значит? Во-первых, почему именно оператор "меньше". Эта прелесть (set) осуществляет все свои сравнения (по крайней мере, при попытке добавить элемент) именно через оператор "меньше". Как узнать, какой оператор перегружать? А вы попробуйте откомпилить проект (когда мы его закончим) без его перегрузки. Выскочит соответствующий error... :) .

Во-вторых, почему именно такая перегрузка. Ну, мне же нужно повторяющиеся иксы откинуть. И вдобавок по их значениям рассортировать. Вот я и заставляю беднягу-компа сравнивать вместо двух классов два икса... поделом... :)

Но закончим с проектом. Пишем cpp-шник:

#include "set_test.h" // подключаем, что уже выстрадали

set <stl_point> set_exact; // наш список точек

int main(void)
{
int x, y;

while(1)
{
// запрашиваем иксы-игреки
cout << "Abscissa: ";
cin >> x;
cout << "Ordinate: ";
cin >> y;

// Теперь пытаемся добавить то, что навводил бедолага-пользователь,
// добавить в set. Выводим отчет о результате.
// Впрочем, на этом остановлюсь подробней.


if(!set_exact.insert(stl_point(x, y)).second)
cout << "not inserted" << endl << endl;
else
cout << "success" << endl << endl;
}
return 0;
}

Итак, что означает фраза

if(!set_exact.insert(stl_point(x, y)).second)
cout << "not inserted" << endl << endl;
else
cout << "success" << endl << endl;

Во-первых, вызвывается конструктор stl_point(x, y) - в созданный экземпляр класса сразу же кидаются икс с игреком (см. конструктор). Далее. Возвращаемое значение сразу же кидается в set_exact и не запоминается больше нигде:

set_exact.insert(stl_point(x, y)) 

Метод insert объекта set возвращает простенький объект типа pair:

template
struct pair
{
typedef T first_type;
typedef U second_type
T first;
U second;
pair();
pair(const T& x, const U& y);
template
pair(const pair& pr);
};

Как видите, pair чем-то подобен моей точке: все, что содержит - это два элемента любого (возможно, одинакового) типа - под загадочными именами first и second. :) Наш же insert в случае удачи возвращает pair(it, true), иначе - pair(it, false). Ну, что такое загадочное it - никогда не интересовался. Наверное, на воткнутый элемент итератор. А вот второй элемент, second, - правда ведь на определенную мысль наталкивает?

Итак, смотрим что там, у second'а внутри. Если элемент воткнулся - радуемся. Нет - гм... Ну я печалиться не буду :)) Компилим проект. Запускаем. Попробуйте ввести элементы с одинаковыми иксами. И наоборот - с одинаковыми игреками. Да и вообще - потестьте :))

Теперь усложняем проект. Смотрите, чем поменялся main:

#include "set_test.h" // подключаем, что уже выстрадали

set set_exact; // наш список точек

int main(void)
{
int x, y;

while(1)
{
// запрашиваем иксы-игреки - здесь пока то же самое
cout << "Abscissa: ";
cin >> x;
cout << "Ordinate: ";
cin >> y;

// А с этого места начинается новенькое - опишу ниже
// Итак, проверяем, чегой-то там вставилось или не вставилось

if(!set_exact.insert(stl_point(x, y)).second)
{
// Ну, пользователь - существо нежное. Если уж он повторно
// ту же абсциссу ввел, нужно узнать, поменять он хочет значение,
// или же просто пальчик у него почесался


if(MessageBox(NULL,
"Введенному значению абсциссы уже "
"сопоставлено значение ординаты.\nХотите заменить его "
"новым значением?",
"Неувязочка вышла!",
MB_ICONWARNING | MB_YESNO | MB_DEFBUTTON2) == IDYES)
{
// Ну, раз уж решили менять значение, для начала, не мудрствуя
// лукаво, удалим старое. Метод erase удаляет из множества
// элемент с каким-то определенным значением. Раз уж в нашем
// множестве ключевую (во всех смыслах) роль играет икс, то на
// игрек я в этом случае чихать хотел. Вы видели конструктор -
// он по дефолту вместо игрека ноль подставляет. Ну и пусть
// себе - элемент все равно будет нужный удален :)


set_exact.erase(stl_point(x));
// Напоследок еще раз проверим вставился ли наш элемент
// Увидите, вставился


if(set_exact.insert(stl_point(x, y)).second)
cout << "success" << endl << endl;
else
cout << "not inserted" << endl << endl;
}
else cout << "not inserted" << endl << endl;
}
else cout << "success" << endl << endl;

// Теперь пройдем все множество с помощью старичка-итератора
// Смысл в том, что после каждого ввода данных ныне будет
// распечатываться все множество
// О том, что есть итератор, смотри в предыдущем шаге :)


set::iterator i;

for(i=set_exact.begin(); i!=set_exact.end(); i++)
cout << "x = " << (*i).x << ", y = " << (*i).y << endl;
cout << endl;
}
return 0;
}
 
« Предыдущая статья   Следующая статья »