Множество (тип данных)

Множество—типиструктура данныхвинформатике,которая является реализацией математического объектамножество.

Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.

В зависимости от идеологии, разные языки программирования рассматривают множество какпростойилисложныйтип данных.

Множество в различных языках программирования

Множество вПаскале

В языке Паскаль (а именно в нём появился этот тип данных) множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 1 бит на элемент. ВTurbo Pascalесть ограничение на 256 элементов, в некоторых других реализациях это ограничение ослаблено.

Пример работы с множествами:

type
{определяем базовые для множеств перечислимый тип и тип-диапазон}
colors=(red,green,blue);
smallnumbers=0..10;
{определяем множества из наших типов}
colorset=setofcolors;
numberset=setofsmallnumbers;
{можно и не задавать тип отдельно}
anothernumberset=setof0..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(5innset2)or{проверка на вхождение элемента}
(greenincset)then
{…}
end.

Множество в C++

Пример программы, использующей структуру set для реализации каталогов:

vector<string>vec;

voidf(vector<string>vec1,intlevel)
{
set<string>sett;
for(inti=0;i<vec1.size();i++)
{
intk=vec1[i].find('/');
if(k!=string::npos)
{
strings1=vec1[i].substr(0,k);
sett.insert(s1);
}
}

for(set<string>::iteratorit=sett.begin();it!=sett.end();it++)
{
vector<string>vec2;
for(inti=0;i<vec1.size();i++)
{
intk=vec1[i].find('/');
if(k!=string::npos&&vec1[i].substr(0,k)==(*it))
{
strings1=vec1[i];
s1.erase(0,k+1);
vec2.push_back(s1);
}
}
for(inti=0;i<level;i++)
{
cout<<'+';
}
cout<<*it<<endl;
f(vec2,level+1);
}
}


intmain()
{
intn;
cin>>n;

for(inti=0;i<n;i++)
{
strings;
cin>>s;
s+='/';
vec.push_back(s);
}

f(vec,0);
return0;
}

Множество в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';

letset=newSet(['first','second','third']);

for(letvalueofset){
console.log(value);
};
// first, second, third

// то же самое
set.forEach((value,valueAgain,set)=>{
console.log(value);
});
// first, second, third

Значение в аргументах повторяется для совместимости сMap,где у.forEach-функции также три аргумента. Но в Set первые два всегда совпадают и содержат очередное значение множества

Пример использования Set

constunion=(s1,s2)=>newSet([...s1,...s2]);
// множество из всех значений s1 и s2

constintersection=(s1,s2)=>newSet(
[...s1].filter(v=>s2.has(v))
);
// множество из значений которые есть и в s1 и в s2

constdifference=(s1,s2)=>newSet(
[...s1].filter(v=>!s2.has(v))
);
// множество из значений, которые есть в s1 но нет в s2

constcomplement=(s1,s2)=>difference(s2,s1);
// множество из значений коротые есть в s2 но нет в s1

constcities1=newSet(['Beijing','Moscow']);
constcities2=newSet(['Moscow','London','Baghdad']);

constoperations=[union,intersection,difference,complement];

constresults=operations.map(operation=>({
[operation.name]:operation(cities1,cities2)
}));


console.dir({cities1,cities2});
console.dir(results);

Ссылки

Set on Github repository HowProgrammingWorks/Set