vector<char> VS vector<bool> в C++11

Question

Почему мы должны использовать vector<char> вместо vector<bool>? В чем причина того, что vector<char> быстрее?

Answer 1

std::vector<bool> это специализация std::vector<T> это сделано главным образом для космической эффективности (дискуссионный). Тем не менее, он ведет себя так же, но не так, как обычныйstd::vector<T>, Это связано главным образом с тем, что std::vector<bool> это не контейнер в обычном смысле стандартной библиотеки C++, а массив битов. Некоторые из различий между std::vector<bool> и регулярный std::vector являются:

• std::vector<bool>::iterator не является итератором с произвольным доступом.
• std::vector<bool> не требуется хранить его элементы как непрерывный массив.
• std::vector<bool> разоблачений class std::vector<bool>::reference как метод доступа к отдельным битам. В частности, объекты этого класса возвращаются operator[], std::vector<bool>::front, std::vector<bool>::back по значению.
• std::vector<bool> не использует std::allocator_traits::construct построить битовые значения.
• std::vector<bool> не гарантирует, что разные элементы в одном и том же контейнере могут быть изменены одновременно разными потоками.
• std::vector<bool> имеет другой интерфейс (т.е. flip())

Эти различия, кроме разрыва концептуального значения std::vector как непрерывный контейнер также имеет тенденцию нарушать пользовательский код, особенно когда этот код является общим (то есть код шаблона).

Для уточнения рассмотрим следующий пример:

template<class T> void foo(std::vector<T> &v) {
 T &frnt = v.front();
 ...
}

Приведенный выше пример работает для каждого T кроме случаев, когда T = bool, Как уже упоминалось, причина этого отказа заключается в том, что v.front()Возвращаемое значение является временным (возвращается по значению) и поэтому не может привязываться к ссылке.

Чтобы избежать этого, многие кодеры избегают использования std::vector<bool> и предпочитаю использование std::vector<char>, Из-за многих проблем, вызванных, многие заявляют, что использование std::vector<bool> можно рассматривать как преждевременную оптимизацию. Для решения этого вопроса есть предложения от многих выдающихся членов сообщества C++. Одно из этих предложений предлагает удалить std::vector<bool> под другим именем, что он не будет ссылаться на контейнеры стандартной библиотеки C++.

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

Список используемой литературы

1. вектор: Больше проблем, лучшие решения, Херб Саттер
2. Наvector<bool> Говард Хиннант
3. std::vector<bool>

Answer 2

vector<bool> это массив битов. vector<char> это массив байтов. Первый использует меньше места в обмен на более сложные операции индексации.

Будь то vector<char> на самом деле быстрее или нет, вероятно, является функцией архитектуры, особенно кеша. Если твой vector<bool> полностью помещается в кэш L1 на x86_64, это может быть быстрее, чем vector<char> который не

Обычные рекомендации применяются, если производительность имеет значение, измерьте производительность в вашем приложении.

Answer 3

Почему мы должны использовать vector<char> вместо vector<bool>?

Как правило, вы не хотели бы предпочесть vector<char>,

В чем причина того, что vector<char> быстрее?

Обычно, vector<char> имеет тенденцию быть медленнее

---

Давайте обсудим недостатки vector<bool>,

cppreference: разные элементы в одном и том же контейнере могут быть изменены одновременно разными потоками, за исключением элементов std::vector<bool>

Если вам нужно одновременное изменение отдельных элементов в одном контейнере, то std::vector<bool> должен быть защищен замком, а vector<char> не. Более простой код для vector<char> является явным преимуществом и может быть более эффективным при условии высокого параллелизма. Если у вас есть этот сценарий, не забудьте рассмотреть ложный обмен, хотя и не забудьте измерить.

---

Говард Хиннант написал статью, в которой обсуждаются плюсы и минусы vector<bool>, Краткая версия плюсов:

Часто это является как пространственной, так и скоростной оптимизацией структуры массива данных bools, если она правильно реализована.

Краткая версия минусов:

Однако он не ведет себя точно так же, как массив bools, и поэтому не должен претендовать на него.

Аргумент статьи не в том, что вы не должны использовать vector<bool>, но это vector<bool> должно быть чем-то отличным от специализации вектора, так как он не полностью соответствует интерфейсу, который он специализирует.