Множество (тип данных)
Из Википедии, бесплатной энциклопедии
Множество — тип и структура данных в информатике, которая является реализацией математического объекта множество.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Реализации[править | править код]
Множество в Паскале[править | править код]
В языке Паскаль (а именно в нём появился этот тип данных) множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 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', '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);