Бит-массив в С++

Ответ 1

Используйте std::bitset (если N - константа), в противном случае используйте std::vector<bool>, как упомянули другие (но не забывайте прочтение эта отличная статья от Herb Sutter)

Битовый набор - это специальный класс контейнера, который предназначен для хранения бит (элементы с двумя возможными значениями: 0 или 1, true или false,...).

Класс очень похож на обычный массив , но оптимизирует для размещения пространства: каждый элемент занимает только один бит (что в восемь раз меньше наименьшего элементального типа в С++: char).

ИЗМЕНИТЬ

Herb Sutter (в этой статье) упоминает, что

Причина std::vector <bool> является несоответствующим, так это то, что он тянет трюки под обложками в попытке оптимизировать пространство: вместо хранения полного char или int для каждого bool [1] (занимая по крайней мере 8 раз пространство на платформах с 8 -битные символы), он упаковывает bools и сохраняет их как отдельные биты (внутри, скажем, символы) во внутреннем представлении.

std::vector <bool> создает определенную оптимизацию для всех пользователей, закрепляя ее в стандарте. Это не очень хорошая идея; разные пользователи имеют разные требования, и теперь все пользователи вектора должны платить штраф за производительность, даже если они не хотят или нуждаются в экономии пространства.

РЕДАКТИРОВАТЬ 2:

И если вы использовали Boost, вы можете использовать boost::dynamic_bitset (если N известно во время выполнения)

Ответ 2

Для лучшего или худшего, std::vector<bool> будет использовать биты вместо bool's, чтобы сэкономить место. Поэтому просто используйте std::vector, как вы должны были быть в первую очередь.

Если N - константа, вы можете использовать std::bitset.

Ответ 3

Вы можете посмотреть std::bitset и std::vector<bool>. Последнее часто рекомендуется против, потому что, несмотря на vector в названии, он действительно не действует как вектор любого другого типа объекта и на самом деле не отвечает требованиям для контейнера в целом. Тем не менее, это может быть очень полезно.

OTOH, ничто не собирается (по крайней мере надежно) хранить 1 миллион значений bool менее чем за 1 миллион бит. Это просто невозможно сделать с какой-либо определенностью. Если ваши битовые наборы содержат степень избыточности, существуют различные схемы сжатия, которые могут быть эффективными (например, LZ *, Хаффман, арифметика), но без какого-либо знания содержимого невозможно сказать, что они были бы наверняка. Тем не менее, каждый из них, как правило, сохраняет каждый бит/бит только в одном бите памяти (плюс немного накладных расходов на бухгалтерию), но обычно это константа и порядка байтов до десятков байтов не более).

Ответ 4

Тип "bool" не сохраняется с использованием только 1 бит. Из вашего комментария о размере, похоже, для каждого bool используется 1 полный байт.

A C подобным образом:

uint8_t sieve[N/8]; //array of N/8 bytes

а затем логические ИЛИ байты вместе, чтобы получить все ваши биты:

sieve[0] = 0x01 | 0x02; //this would turn on the first two bits

В этом примере 0x01 и 0x02 представляют собой шестнадцатеричные числа, представляющие байты.

Ответ 5

Да, вы можете использовать bitset.

Ответ 6

Вам может быть интересно попробовать библиотеку BITSCAN в качестве альтернативы. Недавно было предложено расширение для разреженности, которое я не уверен в вашем случае, но может быть.

Ответ 7

Попробуйте std:: bitset

Ответ 8

Вы можете использовать массив байтов и индекс. Индекс n будет в байтовом индексе n/8, бит # n%8. (В случае, если std:: bitset недоступен по какой-либо причине).

Ответ 9

Если N известно во время компиляции, используйте std:: bitset, в противном случае используйте подталкивание:: dynamic_bitset.

Ответ 10

Тип "bool" не сохраняется с использованием только 1 бит. Из вашего комментария о размере, кажется, для каждого bool используется 1 полный байт.

A C подобным образом:

uint8_t sieve[N/8]; //array of N/8 bytes

Элемент массива:

result = sieve[index / 8] || (1 << (index % 8)); 

или

result = sieve[index >> 3] || (1 << (index & 7));

установить 1 в массив:

sieve[index >> 3] |= 1 << (index & 7);