Множество. Реализация на битовых векторах - История изменений

Ctrlalt: /* Проверка значения указанного бита */

2019-03-03T19:15:59Z

Проверка значения указанного бита

← Предыдущая версия		Версия от 19:15, 3 марта 2019
Строка 290:		Строка 290:
	Set() {		Set() {
	for (int i = 0; i < 5; i++)		for (int i = 0; i < 5; i++)
	a[i++] = 0;		a[i] = 0;
	}		}

	void insert(char value) {		void insert(char value) {
	int index = (value >= 'a' && value <= 'z' ? value - 'a' : 26 + value - '0');		int index = (value >= 'a' && value <= 'z' ? value - 'a' : 26 + value - '0');
	a[index / 8] \|= (1 << (7 - index % 8));		a[index / 8] \|= (1 << (7 - index % 8));
	}		}

Ctrlalt: /* Реализация на логическом массиве */

2019-03-03T19:12:56Z

Реализация на логическом массиве

← Предыдущая версия		Версия от 19:12, 3 марта 2019
Строка 33:		Строка 33:
	Set() {		Set() {
	for (int i = 0; i < 36; i++)		for (int i = 0; i < 36; i++)
	a[i++] = false;		a[i] = false;
	}		}

Ctrlalt: /* Битовый вектор в STL */

2015-07-08T13:07:37Z

Битовый вектор в STL

← Предыдущая версия		Версия от 13:07, 8 июля 2015
Строка 317:		Строка 317:
	== Битовый вектор в STL ==		== Битовый вектор в STL ==

	В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>bitset<N></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><bitset></tt> и пространство имён <tt>std</tt>:		В стандартной библиотеке шаблонов C++ присутствует шаблон [http://www.cplusplus.com/reference/bitset/bitset/ <tt>bitset<N></tt>]. Для возможности его использования требуется подключить заголовочный файл <tt><bitset></tt> и пространство имён <tt>std</tt>:

	#include <iostream>		#include <iostream>

Ctrlalt в 22:36, 4 июля 2015

2015-07-04T22:36:41Z

← Предыдущая версия		Версия от 22:36, 4 июля 2015
Строка 16:		Строка 16:

	== Демонстрация работы ==		== Демонстрация работы ==
	[~~[Демонстрация работы можества, реализованного на битовом векторе]~~]		* [http://visualgo.net/bitmask.html VisuAlgo — Bitmask]

	== Реализация на логическом массиве ==		== Реализация на логическом массиве ==
Строка 364:		Строка 364:

	== Ссылки ==		== Ссылки ==
	* [~~http~~:~~//visualgo.net/bitmask.html VisuAlgo — Bitmask~~]		Задачи:
			* [[:Категория:Задачи: Битовая арифметика\|Задачи: Битовая арифметика]]

	[[Category:Базовые структуры и абстрактные типы данных]]		[[Category:Базовые структуры и абстрактные типы данных]]

Ctrlalt в 19:38, 29 сентября 2014

2014-09-29T19:38:50Z

← Предыдущая версия		Версия от 19:38, 29 сентября 2014
Строка 362:		Строка 362:

	Шаблоны АТД «Множество», представленные в STL, будут рассмотрены в следующих параграфах.		Шаблоны АТД «Множество», представленные в STL, будут рассмотрены в следующих параграфах.

			== Ссылки ==
			* [http://visualgo.net/bitmask.html VisuAlgo — Bitmask]

	[[Category:Базовые структуры и абстрактные типы данных]]		[[Category:Базовые структуры и абстрактные типы данных]]

Ctrlalt в 12:10, 23 мая 2013

2013-05-23T12:10:38Z

← Предыдущая версия		Версия от 12:10, 23 мая 2013
Строка 5:		Строка 5:
	Минимальный набор функций, обеспечиваемый множеством, содержит следующие операции:		Минимальный набор функций, обеспечиваемый множеством, содержит следующие операции:

	{\|		{\| class="methodlist"
	\| ~~<tt>~~void insert(T value)~~</tt>~~ \|\| — добавление значения <tt>value</tt> в множество;		\| \|\| void \|\| insert(T value) \|\| — добавление значения <tt>value</tt> в множество;
	\|-		\|-
	\| ~~<tt>~~void remove(T value)~~</tt>~~ \|\| — исключение значения <tt>value</tt> из множества;		\| \|\| void \|\| remove(T value) \|\| — исключение значения <tt>value</tt> из множества;
	\|-		\|-
	\| ~~<tt>~~bool contains(T value)~~</tt>~~ \|\| — проверка на вхождение значения <tt>value</tt> в множество.		\| \|\| bool \|\| contains(T value) \|\| — проверка на вхождение значения <tt>value</tt> в множество.
	\|}		\|}

Строка 335:		Строка 335:
	STL предоставляет следующий набор методов для битового вектора:		STL предоставляет следующий набор методов для битового вектора:

	{\|		{\| class="methodlist"
	\|		\| \|\| \|\| bitset<N>() \|\| — конструктор битового вектора размера <tt>N</tt>; поддерживается инициализация константой типа <tt>unsigned long</tt> или <tt>string</tt>;
	*<tt>bitset<N>()~~</tt>~~
	\| — конструктор битового вектора размера <tt>N</tt>; поддерживается инициализация константой типа <tt>unsigned long</tt> или <tt>string</tt>;
	\|-		\|-
	\|		\| \|\| bitset<N>& \|\| set(size_t i, bool v = true) \|\| — присвоение биту <tt>i</tt> значения <tt>v</tt>. Вызов без параметров устанавливает значения всех битов в единицы;
	*<tt>bitset<N>&~~<br>~~ set(size_t i, bool v = true)~~</tt>~~
	\| ~~<br>~~— присвоение биту <tt>i</tt> значения <tt>v</tt>. Вызов без параметров устанавливает значения всех битов в единицы;
	\|-		\|-
	\|		\| \|\| bitset<N>& \|\| reset(size_t i) \|\| — установка значения бита <tt>i</tt> в нуль. Вызов без параметров устанавливает значения всех битов в нули;
	*<tt>bitset<N>& reset(size_t i)~~</tt>~~
	\| — установка значения бита <tt>i</tt> в нуль. Вызов без параметров устанавливает значения всех битов в нули;
	\|-		\|-
	\|		\| \|\| bitset<N>& \|\| flip(size_t i) \|\| — инверсия бита <tt>i</tt>. Вызов без параметров инвертирует значения всех битов;
	*<tt>bitset<N>& flip(size_t i)~~</tt>~~
	\| — инверсия бита <tt>i</tt>. Вызов без параметров инвертирует значения всех битов;
	\|-		\|-
	\|		\| \|\| bool \|\| test(size_t i) \|\| — проверка значения бита <tt>i</tt>;
	*<tt>bool test(size_t i)~~</tt>~~
	\| — проверка значения бита <tt>i</tt>;
	\|-		\|-
	\|		\| \|\| bool \|\| any() \|\| — проверка на наличие хотя бы одного единичного бита;
	*<tt>bool any()~~</tt>~~
	\| — проверка на наличие хотя бы одного единичного бита;
	\|-		\|-
	\|		\| \|\| bool \|\| none() \|\| — проверка на отсутствие единичных битов;
	*<tt>bool none()~~</tt>~~
	\| — проверка на отсутствие единичных битов;
	\|-		\|-
	\|		\| \|\| size_t \|\| size() \|\| — получение количества битов в векторе;
	*<tt>size_t size()~~</tt>~~
	\| — получение количества битов в векторе;
	\|-		\|-
	\|		\| \|\| size_t \|\| count() \|\| — получение количества единичных битов в векторе;
	*<tt>size_t count()~~</tt>~~
	\| — получение количества единичных битов в векторе;
	\|-		\|-
	\|		\| \|\| string \|\| to_string() \|\| — получение представления битового вектора в виде строки;
	*<tt>string to_string()~~</tt>~~
	\| — получение представления битового вектора в виде строки;
	\|-		\|-
	\|		\| \|\| unsigned long \|\| to_ulong() \|\| — получение представления битового вектора в виде значения типа <tt>unsigned long</tt>. Если вектор не умещается в этот тип, возбуждается исключение <tt>overflow_error</tt>.
	*<tt>unsigned long to_ulong()~~</tt>~~
	\| — получение представления битового вектора в виде значения типа <tt>unsigned long</tt>. Если вектор не умещается в этот тип, возбуждается исключение <tt>overflow_error</tt>.
	\|}		\|}

Ctrlalt в 12:29, 2 мая 2013

2013-05-02T12:29:09Z

← Предыдущая версия		Версия от 12:29, 2 мая 2013
Строка 385:		Строка 385:
	Шаблоны АТД «Множество», представленные в STL, будут рассмотрены в следующих параграфах.		Шаблоны АТД «Множество», представленные в STL, будут рассмотрены в следующих параграфах.

	[[Category:Базовые структуры данных ~~и АТД~~]]		[[Category:Базовые структуры и абстрактные типы данных]]

Ctrlalt: Ctrlalt переименовал страницу АТД «Множество». Реализация на битовых векторах в Множество. Реализация на битовых векторах

2013-05-02T12:24:42Z

Ctrlalt переименовал страницу АТД «Множество». Реализация на битовых векторах в Множество. Реализация на битовых векторах

← Предыдущая версия	Версия от 12:24, 2 мая 2013
(нет различий)

Ctrlalt: /* Реализация на битовом векторе */

2013-05-02T11:00:55Z

Реализация на битовом векторе

← Предыдущая версия		Версия от 11:00, 2 мая 2013
Строка 156:		Строка 156:
	r2 = a2 \|\| b2;		r2 = a2 \|\| b2;
	//r2 == 1		//r2 == 1
	\| (отсутствует)		\| отсутствует;<br>для логических переменных<br>эквивалентом является<tt>!=</tt>
	\|-		\|-
	\| Битовая операция<br>в С++		\| Битовая операция<br>в С++

Ctrlalt: /* Битовый вектор в STL */

2013-03-03T19:48:38Z

Битовый вектор в STL

← Предыдущая версия		Версия от 19:48, 3 марта 2013
Строка 336:		Строка 336:

	{\|		{\|
	\| <tt>bitset<N>()</tt> \|\| — конструктор битового вектора размера <tt>N</tt>; поддерживается инициализация константой типа <tt>unsigned long</tt> или <tt>string</tt>;		\|
			*<tt>bitset<N>()</tt>
			\| — конструктор битового вектора размера <tt>N</tt>; поддерживается инициализация константой типа <tt>unsigned long</tt> или <tt>string</tt>;
	\|-		\|-
	\| <tt>bitset<N>&<br> set(size_t i, bool v = true)</tt> \|\| <br>— присвоение биту <tt>i</tt> значения <tt>v</tt>. Вызов без параметров устанавливает значения всех битов в единицы;		\|
			*<tt>bitset<N>&<br> set(size_t i, bool v = true)</tt>
			\| <br>— присвоение биту <tt>i</tt> значения <tt>v</tt>. Вызов без параметров устанавливает значения всех битов в единицы;
	\|-		\|-
	\| <tt>bitset<N>& reset(size_t i)</tt> \|\| — установка значения бита <tt>i</tt> в нуль. Вызов без параметров устанавливает значения всех битов в нули;		\|
			*<tt>bitset<N>& reset(size_t i)</tt>
			\| — установка значения бита <tt>i</tt> в нуль. Вызов без параметров устанавливает значения всех битов в нули;
	\|-		\|-
	\| <tt>bitset<N>& flip(size_t i)</tt> \|\| — инверсия бита <tt>i</tt>. Вызов без параметров инвертирует значения всех битов;		\|
			*<tt>bitset<N>& flip(size_t i)</tt>
			\| — инверсия бита <tt>i</tt>. Вызов без параметров инвертирует значения всех битов;
	\|-		\|-
	\| <tt>bool test(size_t i)</tt> \|\| — проверка значения бита <tt>i</tt>;		\|
			*<tt>bool test(size_t i)</tt>
			\| — проверка значения бита <tt>i</tt>;
	\|-		\|-
	\| <tt>bool any()</tt> \|\| — проверка на наличие хотя бы одного единичного бита;		\|
			*<tt>bool any()</tt>
			\| — проверка на наличие хотя бы одного единичного бита;
	\|-		\|-
	\| <tt>bool none()</tt> \|\| — проверка на отсутствие единичных битов;		\|
			*<tt>bool none()</tt>
			\| — проверка на отсутствие единичных битов;
	\|-		\|-
	\| <tt>size_t size()</tt> \|\| — получение количества битов в векторе;		\|
			*<tt>size_t size()</tt>
			\| — получение количества битов в векторе;
	\|-		\|-
	\| <tt>size_t count()</tt> \|\| — получение количества единичных битов в векторе;		\|
			*<tt>size_t count()</tt>
			\| — получение количества единичных битов в векторе;
	\|-		\|-
	\| <tt>string to_string()</tt> \|\| — получение представления битового вектора в виде строки;		\|
			*<tt>string to_string()</tt>
			\| — получение представления битового вектора в виде строки;
	\|-		\|-
	\| <tt>unsigned long to_ulong()</tt> \|\| — получение представления битового вектора в виде значения типа <tt>unsigned long</tt>. Если вектор не умещается в этот тип, возбуждается исключение <tt>overflow_error</tt>.		\|
			*<tt>unsigned long to_ulong()</tt>
			\| — получение представления битового вектора в виде значения типа <tt>unsigned long</tt>. Если вектор не умещается в этот тип, возбуждается исключение <tt>overflow_error</tt>.
	\|}		\|}