vector — есть ли подобный deque битовый набор в C ++?
Я пытаюсь сохранить очень большую маску поиска с фильтром битов.
И то и другое std::vector<bool> а также std::bitset<n> хранить их представления bool как биты, которые отличаются от обычного bool, который обычно имеет размер char или же int32_t,
Проблема заключается в том, что обе эти структуры данных хранят свои элементы в памяти в одном гигантском блоке. Операционные системы злятся на меня за то, что я запрашиваю слишком большие блоки. Одна вещь std::deque<bool> Я думаю, что он хранит свои элементы во что-то вроде связанного списка.
Теперь я знаю, что вы не можете использовать указатель на один бит без сдвига, а использование структуры типа связанного списка отрицает цель сохранения памяти. Но вы можете хранить как 2-гигабайтный блок char[], используйте сдвиги для установки отдельных битов, а затем связанный указатель на другой блок 2 ГБ, вы копаете?
Так скажите мне, если этот тип структуры существует где-то или даже возможно.
Решение
Я не знаю какого-либо прямого решения вашей проблемы, но оно может быть легко решено с помощью пользовательского контейнера.
Одно из решений — использование std :: deque для std :: bitset. Где размер набора битов равен степени 2, например, 256. Таким образом, вы можете взять индекс и просто замаскировать индекс дек и набор битов по отдельности:
std::deque< std::bitset<256> > ;
unsigned long long = 1500;
bool val = bigBitset[ index>>8 ][ index & 0xFF ];
Это также может быть заключено в класс для удобства:
class DequeBitset : public std::deque< std::bitset<256> >
{
public:
struct Index
{
unsigned long index;
unsigned long dequeIndex() const { return index>>8; }
unsigned long bitsetIndex() const { return index&0xFF; }
Index( unsigned long index ) : index(index) {}
};
public:
bool operator[]( const Index& index )
{ return std::deque< std::bitset<256> >::operator [](index.dequeIndex())[ index.bitsetIndex() ]; }
};
int _tmain(int argc, _TCHAR* argv[])
{
DequeBitset test;
test.resize(10);
bool val = test[259];
return 0;
}
Другие решения
Я не знаю, сколько блоков 2ГБ вы можете использовать. Но допустим, вам нужно 2048 блоков по 2 ГБ. Тогда почему бы не хранить указатели на блоки 2 ГБ в векторе, т.е. std::vector<uint8_t*> и добавьте новый блок 2 ГБ в этот вектор, как вам нужно, чтобы расширить структуру.
Деко / очередь, специализированные с желаемым классом «блока» (например, без знака char [N], или класс обертки (даже битовый набор), для удобства) с пользовательским равенством и побитовыми операторами, которые работают с соответствующими блоками, могли бы достичь этого.
Эти пользовательские побитовые методы должны были бы определять блоки / диапазоны для работы, переводя каждый входной «глобальный» битовый индекс операции в набор индексов (номер блока, локальный блок) в зависимости от операции модификации. Немодифицирующие операции / запросы могут быть реализованы как простой обход всех блоков.
Общая идея состоит в том, что вы разбиваете битовую маску на блоки и работаете с этой последовательностью блоков, поскольку в зависимости от фрагментации памяти вы не сможете выделить 2 ГБ или более непрерывной памяти в время выполнения. Конечно, чем меньше размер блока, тем больше вы страдаете от накладных расходов на обработку, пониженной когерентности кэша и фрагментации памяти, однако в вашем клиентском приложении вы можете выжать больше памяти из вашей памяти.
Похоже, что реализация @Crog уже существует: boost::dynamic_bitset