Контейнер
типа set
Множество (set)
является ассоциативным контейнером, который хранит объекты типа key. В этом
случае говорят о типе Simple Associative Container, имея в виду, что как value,
так и key имеют один тип key. Говорят также о Unique Associative Container,
имея в виду, что в контейнере типа set не может быть одинаковых элементов. Рассмотрим
работу контейнера на примерах. Не забудьте вставить директиву #include <set>:
void
main ()
{
//========
Создаем множество целых
set<int>
s;
s.insert(1);
s.insert(2);
s.insert
(3);
//=======
Повторно вставляем единицу (она не пройдет)
s.insert
(1);
//====
Два раза вставляем "в конец последовательности"
s.
insert (--s.end() , 4); s.insert(—s.endO, -1);
pr(s,"Set
of ints");
//========
Второе множество
set<int>
ss;
for
(int i=l; i<5; i++) ss.insert (i*10);
//========
Вставляем диапазон
s.
insert (++ss. begin () , —s s.end() );
pr(s,
"After insertion"); cout«"\n\n";
}
Эта программа
выведет в окно Output следующие строки:
Set
of ints # Sequence:
1.
-1
2.
1
3.
2
4.
3
5.
4
After
insertion # Sequence:
1.
-1
2.
1
3.
2
4.
3
5.
4
6.
20
7.
30
Как видно из
распечатки, несмотря на то что и 4 и -1 были вставлены в конец последовательности,
контейнер сам распорядился порядком следования и разместил элементы в порядке
возрастания ключей. Вставка диапазона из другого множества также происходит
по этим законам. Следующий содержательный пример я обнаружил на сайте компании
Silicon Graphics. Он приведен в слегка измененном виде:
//=========
Предикат
inline
bool NoCase(char a,
char b)
{
//
Определяет отношение less для обычных символов
//
без учета регистра (Подключите stdlib.h)
return
tolower(a) < tolower (b) ; !;
}
//=========
Функциональный объект
struct
LessStr
{
//====
Определяет отношение less для C-style строк
bool
operator()(const char* a, const char* b)
const
{
return
strcmp(a, b) < 0;
}
};
Два отношения
порядка для типов данных, хорошо вам знакомых (char и char*), для разнообразия
заданы: одно в виде предиката, другое в виде функционального объекта. Ниже они
будут использованы в конструкторе шаблона классов set. Тем самым определен порядок
сортировки элементов контейнера:
void
main ()
{
//======
Обычные неупорядоченные массивы символов
const
int N = 6;
const char* a[N] =
{
"Set",
"Pet", "Net", "Get", "Bet", "Let"
};
const
char* b[N] =
{
"Met",
"Wet", "Jet",
"Set",
"Pet", "Net",
}
;
//========
Создаем два множества обычных строк,
//========
определяя отношение порядка
set<const
char*, LessStr> A(a, a + N);
set<const
char*, LessStr> B(b, b + N);
//========
Создаем пустое множество
set<const
char*, LessStr> C;
//========
Выходной итератор привязываем к cout
cout
« "Set A: {";
copy
(A.begin (), A.end.(),
ostream_iterator<const
char*>(cout, "; "));
cout
« ' } ' ;
cout
« "\n\nSet B:
copy
(B.begin (), B.end(), .. ostream_iterator<const char*>(cout, ", "));
//=======
Создаем и выводим объединение двух множеств
cout
« "\n\nUnion A U В: ";
set_union
(A.begin () , A.end(), B.begin(), B.end(),
ostream_iterator<const
char*>(cout, ", "),
LessStr
() )';
//=======
Создаем и выводим пересечение двух множеств
cout
« "\n\nlntersection А & В: ";
set_intersection
(A.begin () , A.end(), B.beginO, B.end(), ostream_iterator<const char*>(cout,
" "), LessStrO);
//=====
Создаем разность двух множеств
//=====
Используем inserter для заполнения множества С
set_dif
ference (A.begin () , A.end(), B.beginO, B.end(),
inserter
(С, C.begin()),
LessStr()
) ;
cout
« "\n\nDifference A/B: ";
//=====
Копируем множество прямо в выходной поток сору
С.
begin () , С.
end
();
ostream_iterator<const
char*>(cout, " "));
С.
clear () ;
//=====
Повторяем в обратную сторону
set_dif
ference (В. begin () , B.endO, A.begin(), A.end(),
inserter
(С, C.begin()), LessStrO);
cout
« "\n\nDifference B/A: ";
copy
(C.begin (), C.end(),
ostream_iterator<const
char*>(cout, " "));
cout
« "\n\n";
//======
Выводим разделитель
vector<char>
line(50, ' = ');
ostream_iterator<char>
os(cout, "") ;
copy
(line .begin О , line.endO, os) ;
//======
Обычные массивы символов
char
D[] = { 'a', 'b', 'с', 'd', ' e', 'f' };
char
E[] = { 'A', 'B', 'C
1, 'G', 'H
1, 'H' };
cout
« "\n\nSet D:
";
for
(int i=0; i<N; i++) cout « D[i] « ", ";
cout
« "\n\nSet E:
";
for
(int i=0; i<N; i + -i-)
cout
« E[i]«",";
cout
« "\n\nSymmetric Difference D/E (nocase): ";
//======
Используем алгоритм set_symmetric_difference
//======
для обычных массивов символов
set_symmetric_difference(D,
D + N, E, E + N,
ostream_iterator<char>(cout,
" "), NoCase);
cout«"\n\n";
}
Новые возможности
STL, которые использованы в этом фрагменте, — это использование адаптера insert_iterator
и копирование содержимого контейнера прямо в выходной поток (см. ostream_iterator).
Вывод в поток осуществляется с помощью особого типа итератора ostream_iterator,
который осуществляет форматируемый вывод объектов типа Т в указанный выходной
поток (ostream). Шаблон класса ostream_iterator настраивается на тип данных,
в нашем случае const char*, а затем char, и берет в качестве параметров объект
потокового вывода (cout) и разделитель, который мы специально изменяем по ходу
дела для того, чтобы вы его обнаружили.
Insert_iterator
— это адаптер (настройщик) итератора, который настраивает операнд, являющийся
мишенью операции. Присвоение с помощью (сквозь призму) такого итератора вставляет
объект в контейнер, раздвигая его, то есть, используя метод insert. Он следит
за текущей позицией в контейнере (insertion point) и производит вставку перед
ней. Здесь вы, однако, должны учесть различную семантику операции вставки в
различные типы контейнеров. Если это последовательность (sequence), то все происходит
именно так, как только что было сказано, но если это сортируемый ассоциативный
контейнер, то вы не можете управлять позицией вставки. Для таких контейнеров
указание места вставки служит лишь отправной точкой для поиска реальной позиции
в контейнере. В результате вставки при выводе вы увидите упорядоченную по возрастанию
ключа последовательность. Порядок вставки в сортируемые ассоциативные контейнеры
не влияет на порядок элементов, который вы увидите на экране. Однако он может
повлиять на эффективность процесса вставки.
Пары
Парой называется
шаблон класса, который хранит пару объектов различного типа. Пара похожа на
контейнер в том, что она владеет своими элементами, но она не является контейнером,
так как не поддерживает стандартных методов и итераторов, присущих контейнерам.
У пары есть два элемента данных (first, second), которые дают возможность манипулировать
вложенными объектами. Следующий фрагмент иллюстрирует логику использования пары:
pair<bool,
double> result = FindRoot();
if
(result.first)
print(result.second);
else
report_error()
;
Ассоциативные
контейнеры используют тип пар _Pairib. Он определяет пару:
pair<iterator,
bool>
Первый элемент
каждой такой пары является итератором соответствующего типа, а второй — результатом
какого-либо действия. Например, метод insert возвращает пару типа _Pairib, анализируя
которую вы можете узнать результат вставки (успех или неудача). Рассмотрим пример:
void
main ()
{
//==========
Массив объектов класса Man
Man
ar[] =
{
joy,duke,
win, joy,charlie
);
uint
size =
sizeof(ar)
/sizeof(Man);
//==========
Создаем множество объектов класса Man
set<Man>
s (ar, ar+size); pr(s, "Set of Man");
//==========
Ищем объект и удаляем его
set<Man>::iterator
p = s.find(joy);
if
(p != s.end() )
{
s.erase(p);
cout
« "\n\n"« joy «" found and erased";
}
pr(s,"After
erasure");
//==========
Объявляем пару
set<Man>::_Pairib
pib;
//==========
Пробуем вставить объект
pib
= s.insert(joy);
//==========
Анализируем результат вставки
cout
« "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//==========
Пробуем вставить повторно
pib
= s.insert(joy);
cout
« "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//==========
Сравниваем ключи
cout
« "\n\ns.key_comp() (zoran,count) returned "
«
s.key_comp()(zoran,ar[0]);
cout
« "\n\ns.key_comp()(count,zoran) returned "
«
s.key_comp()(ar[0],zoran);
cout
<<"\n\n";
}
Приведем
результат работы этой программы:
Set
of Man # Sequence:
1.
Joy Amore, Age: 18
2.
Winton Kelly, Age: 50
3.
Charlie Parker, Age: 60
4.
Duke Ellington, Age: 90
Joy
Amore, Age: 18 found and erased After erasure # Sequence:
1.
Winton Kelly, Age: 50
2.
Charlie Parker, Age: 60
3.
Duke Ellington, Age: 90
Inserting:
Joy Amore, Age: 18
Result
is: 1
Inserting:
Joy Amore, Age: 18
Result
is: 0
s.key_comp()(zoran,count)
returned 0 s.key_comp()(count,zoran) returned 1