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

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

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

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

Реализации

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

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

Ссылки

Set on Github repository HowProgrammingWorks/Set