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

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

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

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

Реализации[править | править код]

Множество в Паскале[править | править код]

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

Ссылки[править | править код]

Set on Github repository HowProgrammingWorks/Set