Множества и мультимножества
Множества — это наборы уникальных значений; мультимножества допускают повторяющиеся значения. В остальном они совершенно идентичны, так что в дальнейшем я буду говорить просто о “множествах”.
Множество представляет собой ассоциативный контейнер с быстрым доступам к значениям элементов. Значения элементов в множестве принято называть ключами. Программа может быстро определить, находится ли данный ключ в множестве.
Элементы множества всегда сортированы. Поэтому поиск нужного ключа очень прост и эффективен.
Что касается последовательных операций и прямого доступа, то тут множества далеки от совершенства. Набор функций-элементов у множеств невелик по сравнению с другими контейнерами.
Создание множеств
Объявляются множества несколько сложнее, чем рассмотренные до сих пор контейнеры, так как при этом необходимо указать функциональный объект, который будет использоваться при упорядочении элементов:
set<double, less<double> > dset;
Обязательно вставьте пробел между двумя правыми угловыми скобками, а то компилятор примет их за операцию сдвига и откажется транслировать программу.
Удобно переименовать представитель шаблона:
typedef set<double, less<double> > set_type;
set type dset;
Множество, как и другие контейнеры, можно создать из диапазона элементов другого контейнера:
double darr[6] = (1.0, 2.0, 2.5, 4.5, 3.5, 2.5};
set_type dset(darr, darr + 6) ;
В каком бы порядке ни следовали элементы в исходном контейнере, в множестве они окажутся сортированными.
Если в множество set вводятся повторяющиеся элементы, они игнорируются. В multiset ключ будет содержаться столько раз, сколько раз он вводился.
Действия над множествами
Как я сказал, функций у множеств сравнительно немного. Функции insert () и erase () имеют дополнительную форму с одним параметром, специфицирующим ключ, который нужно добавить или удалить из множества:
dset.insert (3.14);
dset.erase(3.5);
Функции lower bound () и upper bound () возвращают соответственно итератор элемента, который больше или равен, и элемента, который больше указанного ключевого значения. Пример использования этих функций показан в приведенной ниже программе.
Функция count () возвращает 'число вхождений в множество указанного ключа. В set функция может возвращать только 0 или 1. Вызов этой функции — простейший способ определить, входит ли ключ в множество.
Следующая программа иллюстрирует эти функции множеств.
#include <iostream>
#include <set>
#pragma hdrstop
#include <condefs.h>
using namespace std;
// Дать имя типу множества;
typedef multiset<double, less<double> > set_type;
//
// Операция передачи множества в поток.
//
ostream &operator“(ostream Sos, const set_type &c)
(
cout<< "{ ";
copy(c.begin (), c.end(),
ostream_iterator<set_type::value_type>(os, " "));
os << "} Size: "<< c.sizeO;
return os;
}
int main() {
set type dset;
cout << "Inserting... ";
for (int i=8; i>0; i--) { // Ввести элементы
dset.insert (i); //в множество.
cout << i << " ";
} cout<< end1;
cout.setf(ios::fixed);
cout.precision (1) ;
cout << "Initial set : " << dset<< end1;
dset.erase (2.0); // Удалить 2.0,если есть.
cout << "2.0 erased :" << dset<< endl;
dset.insert(4); // Добавить лишние четверки.
dset.insert (4); //
cout << "4's inserted : " << dset << endl;
cout<< "Count of 4.0 :"<< dset.count (4.0)<<endl;
// Сосчитать их.
set type::iterator pi =dset.lower_bound(2.5),
p2 =dset.upper bound(6.5);
dset.erase (pi, p2); // Найти диапазон значений
// и удалить его.
cout << "Erase 2.5-6.5: " << dset<< end1;
return 0;
}
Программа выводит:
Inserting. ..87654321
Initial set : ( 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 } Size: 8
2.0 erased : {1.0 3.0 4.0 5.0 6.0 7.0 8.0 ) Size: 7
4's inserted : { 1.0 3.0 4.0 4.0 4.0 5.0 6.0 7.0 8.0 }Size: 9
Count of 4.0 : 3
Erase 2.5-6.5: { 1.0 7.0 8.0 } Size: 3
