Множество — тип и структура данных в информатике, которая является реализацией математического объекта множество.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Множество в различных языках программирования Множество в Паскале В языке Паскаль (а именно в нём появился этот тип данных) множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 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 первые два всегда совпадают и содержат очередное значение множества
Пример использования Setconst 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', 'Moscow']); const cities2 = new Set(['Moscow', '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);
Ссылки Set on Github repository HowProgrammingWorks/Set
Категория:Типы данных Категория:Структуры данных Категория:Составные типы данных