Ответ 1
Обновление
Прошло столько времени с тех пор, как я разместил это, но:
Я уже знаю, что это проще и понятнее, чем целое, но как быстро?
Если вы используете bitset таким образом, чтобы сделать его более понятным и чистым, чем бит-возиться, например, проверять один бит за раз, а не использовать битовую маску, то вы неизбежно теряете все те преимущества, которые побитовые операции обеспечивают, например, возможность проверить, установлено ли 64 бита одновременно с маской или с помощью инструкций FFS для быстрого определения того, какой бит установлен между 64-битами.
Я не уверен, что bitset несет штраф за использование всеми возможными способами (например: используя его побитовое operator&), но если вы используете его как логический массив фиксированного размера, который в значительной степени Я всегда вижу, как люди используют его, тогда вы обычно теряете все эти преимущества, описанные выше. Мы, к сожалению, не можем получить такой уровень выразительности только для доступа к одному биту за раз с помощью operator[], и оптимизатор вычислит все побитовые манипуляции, FFS и FFZ и т.д. Для нас, по крайней мере, с момента последнего время, которое я проверил (иначе bitset будет одной из моих любимых структур).
Теперь, если вы собираетесь использовать bitset<N> bits взаимозаменяемо с похожим, скажем, uint64_t bits[N/64], как при доступе к одному и тому же пути с помощью побитовых операций, он может быть на парах (не проверял с этого древнего сообщения). Но тогда вы теряете многие преимущества использования bitset в первую очередь.
for_each метод
Раньше я думал о некоторых недоразумениях, когда я предложил метод for_each для итерации через такие вещи, как vector<bool>, deque и bitset. Точка такого метода заключается в использовании внутреннего знания контейнера для более эффективного итерации элементов при вызове функтора, так же как некоторые ассоциативные контейнеры предлагают собственный метод find вместо использования std::find, чтобы сделать лучше чем поиск по линейному времени.
Например, вы можете перебирать все биты набора vector<bool> или bitset, если у вас есть внутреннее знание этих контейнеров, проверяя 64 элемента за раз, используя 64-разрядную маску, когда заняты 64 смежных индекса, а также использовать инструкции FFS, если это не так.
Но дизайн итератора, который должен был выполнять этот тип скалярной логики в operator++, неизбежно должен был бы сделать что-то значительно более дорогое, просто по характеру, в котором итераторы разработаны в этих особых случаях. bitset не хватает итераторов, и это часто заставляет людей хотеть использовать его, чтобы избежать использования побитовой логики, чтобы использовать operator[] для проверки каждого бита отдельно в последовательном цикле, который просто хочет узнать, какие биты установлены. Это тоже не так эффективно, как это может сделать реализация метода for_each.
Двойные/вложенные итераторы
Другой альтернативой предложенному выше методу for_each, предназначенному для контейнера, будет использование двойных/вложенных итераторов: то есть внешний итератор, который указывает на поддиапазон итератора другого типа. Пример кода клиента:
for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it)
{
for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it)
// do something with *inner_it (bit index)
}
Несмотря на то, что он не соответствует плоскому типу конструкции итератора, доступному сейчас в стандартных контейнерах, это может позволить некоторые очень интересные оптимизации. Например, представьте себе такой случай:
bitset<64> bits = 0x1fbf; // 0b1111110111111;
В этом случае внешний итератор может, используя всего несколько битовых итераций ((FFZ/или/дополнение), вывести, что первый диапазон бит для обработки будет битами [0, 6], и в этот момент мы можем итерации через этот поддиапазон очень дешево через внутренний/вложенный итератор (он просто увеличит целое число, сделав ++inner_it эквивалентным только ++int). Затем, когда мы увеличиваем внешний итератор, он может очень быстро и снова с несколькими побитовыми инструкциями определить, что следующий диапазон будет [7, 13]. После того, как мы перейдем через этот субдиапазон, мы закончили. Возьмем это как еще один пример:
bitset<16> bits = 0xffff;
В этом случае первый и последний поддиапазоны будут [0, 16), и биты могут определить, что с одной побитовой инструкцией, в какой точке мы можем выполнять итерацию по всем битам, а затем мы закончили.
Этот тип вложенного дизайна итератора будет особенно хорошо отображаться в vector<bool>, deque и bitset, а также в других структурах данных, которые люди могут создавать как развернутые списки.
Я говорю это так, что выходит за рамки только спекуляций с креслами, поскольку у меня есть набор структур данных, которые похожи на аналогичных deque, которые фактически совпадают с последовательной итерацией vector (все еще заметно медленнее для случайных -access, особенно если мы просто храним кучу примитивов и делаем тривиальную обработку). Однако для достижения сопоставимых времен до vector для последовательной итерации мне пришлось использовать эти типы методов (метод for_each и двойные/вложенные итераторы), чтобы уменьшить количество обработки и разветвления на каждой итерации. Я не мог соперничать с другими временами, используя только плоский дизайн итератора и/или operator[]. И я, конечно, не умнее, чем стандартные разработчики библиотек, но придумал контейнер deque, который может быть последовательно повторен гораздо быстрее, и это настоятельно предлагает мне, что это проблема со стандартным дизайном итераторов интерфейса в этом который приходит с некоторыми накладными расходами в этих особых случаях, которые оптимизатор не может оптимизировать.
Старый ответ
Я один из тех, кто даст вам аналогичный ответ, но я постараюсь дать вам нечто более глубокое, чем "just because". Это то, что я натолкнулся на фактическое профилирование и время, а не просто на недоверие и паранойю.
Одна из самых больших проблем с bitset и vector<bool> заключается в том, что их дизайн интерфейса "слишком удобен", если вы хотите использовать их как массив логических элементов. Оптимизаторы отлично справляются со всей структурой, которую вы создаете, чтобы обеспечить безопасность, снизить затраты на обслуживание, сделать изменения менее навязчивыми и т.д. Они выполняют особенно прекрасную работу по выбору инструкций и распределению минимального количества регистров, чтобы такой код работал так быстро, как не очень безопасные, не очень простые в обслуживании/альтернативные варианты.
Часть, которая делает интерфейс битета "слишком удобным" за счет эффективности, - это operator[] с произвольным доступом, а также дизайн итератора для vector<bool>. Когда вы обращаетесь к одному из них по индексу n, код должен сначала определить, к какому байту принадлежит n-й бит, а затем к второму индексу к этому биту. Эта первая фаза обычно включает в себя разделение /rshifts против lvalue вместе с модулем/побитовым и которое является более дорогостоящим, чем фактическая операция бит, которую вы пытаетесь выполнить.
Конструкция итератора для vector<bool> сталкивается с подобной неловкой дилеммой, где она либо должна входить в другой код каждые 8+ раз, когда вы ее выполняете, либо оплачиваете такую стоимость индексации, описанную выше. Если первое сделано, это делает логику асимметричной по итерациям, и конструкции итератора имеют тенденцию к быстрому результату в тех редких случаях. Чтобы продемонстрировать, если vector имел собственный метод for_each, вы могли бы перебирать, скажем, диапазон из 64 элементов сразу, просто маскируя биты против 64-разрядной маски для vector<bool>, если все биты устанавливаются без проверки каждого бита отдельно. Он мог бы даже использовать FFS, чтобы разобраться в диапазоне все сразу. Конструкция итератора неизбежно должна была бы сделать это скалярным способом или сохранить больше состояния, которое должно быть избыточно проверено на каждой итерации.
Для случайного доступа оптимизаторы не могут оптимизировать эти накладные расходы на индексацию, чтобы выяснить, какой байт и относительный бит для доступа (возможно, слишком зависимые от времени выполнения), когда это не нужно, и вы склонны видеть значительную прибыль с этим более ручным битом обработки кода последовательно с расширенным знанием того, в каком байте/слове/dword/qword он работает. Это несколько несправедливое сравнение, но трудность с std::bitset заключается в том, что нет никакого способа сделать справедливое сравнение в таких случаях, когда код знает, к какому байту он хочет получить доступ заранее, и чаще всего вы, как правило, имеете эту информацию заранее. Это сравнение яблок с оранжевым в случайном доступе, но вам часто нужны апельсины.
Возможно, это не так, если в проекте интерфейса был bitset, где operator[] возвращался прокси-сервер, требуя использовать шаблон доступа с двумя индексами. Например, в таком случае вы получите доступ к биту 8, написав bitset[0][6] = true; bitset[0][7] = true; с параметром шаблона, чтобы указать размер прокси (например, 64 бита). Хороший оптимизатор может принять такой дизайн и сделать его соперником в ручном режиме старой школы, чтобы вручную манипулировать бит, переведя его на: bitset |= 0x60;
Другая конструкция, которая может помочь, заключается в том, что bitsets предоставил метод for_each_bit, передавая бит-прокси на предоставляемый вами функтор. Это могло бы реально противостоять ручному методу.
std::deque имеет аналогичную проблему с интерфейсом. Его производительность не должна быть намного медленнее, чем std::vector для последовательного доступа. Тем не менее, к сожалению, мы последовательно обращаемся к нему с помощью operator[], который предназначен для случайного доступа или через итератор, а внутренняя репутация deqes просто не очень эффективно сопоставляется с дизайном на основе итератора. Если deque предоставил собственный метод for_each, то он мог бы начать намного ближе к производительности последовательного доступа std::vector's. Это некоторые из редких случаев, когда дизайн интерфейса Sequence поставляется с некоторыми издержками эффективности, которые оптимизаторы часто не могут стереть. Часто хорошие оптимизаторы могут обеспечить удобство освобождения от времени исполнения в сборке продукции, но, к сожалению, не во всех случаях.
Извините!
Также жаль, в ретроспективе я немного бродил с этим сообщением о vector<bool> и deque в дополнение к bitset. Это потому, что у нас была кодовая база, где использование этих трех и, в частности, их повторение или использование их со случайным доступом, часто были горячими точками.
Яблоки в апельсины
Как было подчеркнуто в старом ответе, сравнение простого использования bitset с примитивными типами с низкоуровневой побитовой логикой сравнивает яблоки с апельсинами. Это не нравится bitset реализовано очень неэффективно для того, что он делает. Если вам действительно нужно получить доступ к кучке битов со случайным шаблоном доступа, который по какой-то причине или по-другому должен проверять и устанавливать только один бит времени, тогда он может быть идеально реализован для такой цели. Но я считаю, что почти все случаи использования, с которыми я столкнулся, не требовали этого, и когда это не требуется, старый способ школы, включающий побитовые операции, имеет тенденцию быть значительно более эффективным.