Множество (тип данных)
Множество — тип и структура данных в информатике, которая является реализацией математического объекта множество.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Реализации
Множество в Паскале
В языке Паскаль множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 1 бит на элемент. В Turbo Pascal есть ограничение на 256 элементов, в некоторых других реализациях это ограничение ослаблено.
Пример работы с множествами:
type
{определяем базовые для множеств перечислимый тип и тип-диапазон}
colors = (red,green,blue);
smallnumbers = 0..10;
{определяем множества из наших типов}
colorset = set of colors;
numberset = set of smallnumbers;
{можно и не задавать тип отдельно}
anothernumberset = set of 0..20;
{объявляем переменные типа множеств}
var
nset1,nset2,nset3:numberset;
cset:colorset;
begin
nset1 := [0,2,4,6,8,10]; {задаем в виде конструктора множества}
cset := [red,blue]; {простым перечислением элементов}
nset2 := [1,3,9,7,5]; {порядок перечисления неважен}
nset3 := []; {пустое множество}
include(nset3,7); {добавление элемента}
exclude(nset3,7); {исключение элемента}
nset1 := [0..5]; {возможно задавать элементы диапазоном}
nset3 := nset1 + nset2; {объединение}
nset3 := nset1 * nset2; {пересечение}
nset3 := nset1 - nset2; {разность}
if (5 in nset2) or {проверка на вхождение элемента}
(green in cset) then
{…}
end.
Множество в C++
Пример программы, использующей структуру set для реализации каталогов:
vector <string> vec;
void f(vector <string> vec1, int level)
{
set <string> sett;
for (int i = 0; i < vec1.size(); i++)
{
int k = vec1[i].find('/');
if (k != string::npos)
{
string s1 = vec1[i].substr(0, k);
sett.insert(s1);
}
}
for (set <string> :: iterator it = sett.begin(); it != sett.end(); it++)
{
vector <string> vec2;
for (int i = 0; i < vec1.size(); i++)
{
int k = vec1[i].find('/');
if (k != string::npos && vec1[i].substr(0, k) == (*it))
{
string s1 = vec1[i];
s1.erase(0, k + 1);
vec2.push_back(s1);
}
}
for (int i = 0; i < level; i++)
{
cout << '+';
}
cout << *it << endl;
f(vec2, level + 1);
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
s += '/';
vec.push_back(s);
}
f(vec, 0);
return 0;
}
Множество в JavaScript
Множество в JavaScript — структура данных, служащая для хранения набора значений, которые не имеют индексов или ключей (но внутри структуры данных они должны иметь порядок, например, индекс в массиве, однако, множество абстрагирует нас от этой особенности реализации).
Объект Set
Set — коллекция для хранения множества значений, причём каждое значение может встречаться лишь один раз.
Методы
set.has(item) — возвращает true если item есть в коллекции, иначе — false;
set.add(item) — добавляет элемент item в набор, возвращает set. Если пытаться добавить существующий, ничего не произойдет;
set.clear() — очищает set;
set.delete(item) — удаляет item из множества, возвращает true, если он там был, иначе false.
Перебор элементов
осуществляется через for..of либо forEach
'use strict';
let set = new Set(['first', 'second', 'third']);
for(let value of set) {
console.log(value);
};
// first, second, third
// то же самое
set.forEach((value, valueAgain, set) => {
console.log(value);
});
// first, second, third
Значение в аргументах повторяется для совместимости с Map, где у .forEach-функции также три аргумента. Но в Set первые два всегда совпадают и содержат очередное значение множества
Пример использования Set
const union = (s1, s2) => new Set([...s1, ...s2]);
// множество из всех значений s1 и s2
const intersection = (s1, s2) => new Set(
[...s1].filter(v => s2.has(v))
);
// множество из значений которые есть и в s1 и в s2
const difference = (s1, s2) => new Set(
[...s1].filter(v => !s2.has(v))
);
// множество из значений, которые есть в s1 но нет в s2
const complement = (s1, s2) => difference(s2, s1);
// множество из значений коротые есть в s2 но нет в s1
const cities1 = new Set(['Beijing', 'Kiev']);
const cities2 = new Set(['Kiev', 'London', 'Baghdad']);
const operations = [union, intersection, difference, complement];
const results = operations.map(operation => ({
[operation.name]: operation(cities1, cities2)
}));
console.dir({ cities1, cities2 });
console.dir(results);