Контейнер типа set
Контейнер типа 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', 'C1, 'G', 'H1, '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
