Как проверить, что вектор & lt; bool & gt; на самом деле вектор битов, а не байтов?
Мне нужно хранить динамический массив битов.
Справочная страница C ++ по вектору< bool> имеет следующую информацию:
Хранилище не обязательно является массивом
boolзначения, но реализация библиотеки может оптимизировать хранение так, чтобы каждое значение сохранялось в одном бите.
Как мне убедиться, что моя программа использует vector<bool> на самом деле хранит биты в векторе вместо логических значений (байтов)?
Решение
Не пытайся сделать это. Вместо этого используйте boost::dynamic_bitset что четко указывает на то, что вы на самом деле хотите. vector<bool> Оптимизация фактически создает множество возможностей для ошибок, например, при использовании итераторов (потому что она обычно возвращает прокси-объект).
Другие решения
Ну, вы всегда можете заглянуть в заголовочные файлы, которые поставляются с вашим компилятором. Поскольку контейнеры STL являются почти исключительно шаблонными классами, большинство, если не все части реализации будут видны в заголовках.
Может быть, глядя на vector объект в отладчике также может быть полезным.
Примечание: вы также должны знать, что vector<bool> В то же время сообщество C ++ довольно недовольно, и что эта оптимизация предназначена для размера, а не для скорости:
https://www.informit.com/guides/content.aspx?g=cplusplus&SEQNUM = 98
Может быть возможно проверить это во время компиляции, проверив тип возврата неконстантной версии vector<bool>::operator[]: Реализация, которая хранит свои значения в виде битов, должна возвращать ссылочный класс прокси, а не bool&,
Здесь действительно нечего проверять. Специализация vector<bool> для хранения битов вместо больших объектов требуется стандарт. §23.2.5: «Для оптимизации распределения пространства предусмотрена специализация вектора для элементов bool:».
Я предполагаю, что с некоторой точки зрения то, что вы цитировали, по крайней мере, в некотором роде правильно. Поскольку по существу некому сертифицировать соответствие компилятора и, по существу, нет компилятора, который даже пытается выполнить все требования соответствия, компилятор мог решите также игнорировать это требование.
Хотя я не знаю ни одного компилятора, который бы это делал — и если бы кто-то знал, я бы предположил, что он наверняка был бы хорошо известен. Временами были довольно горячие дискуссии об удалении vector<bool> специализация, так что если бы у кого-то были реальные примеры того, насколько лучше (или хуже) это делало вещи, я подозреваю, что мы слышали об этом.
Изменить: в C ++ 11, требования для std::vector<bool> были перенесены в §23.3.7. Что еще более важно, формулировка была изменена, чтобы указать, что упакованное представление, где каждый bool хранится в виде одного бита вместо непрерывного распределения bool Значения теперь только рекомендации.
По крайней мере, ИМО, это мало реальный разница. Насколько я знаю, во всех реальных реализациях все еще используется упакованное представление, поэтому даже если теоретически гарантировано, что упакованное хранилище больше не гарантируется, это все равно происходит на практике.
Эта программа как бы доказывает это.
#include <vector>
#include <iostream>
template <typename T>
void showSize() {
std::vector<T> myvec;
size_t capacity = myvec.capacity();
std::cout << "capacity: " << myvec.capacity() << std::endl;
std::cout << "size: " << myvec.size() << std::endl;
while (myvec.capacity() < 1024) {
while (myvec.capacity() == capacity) {
myvec.push_back(T());
}
capacity = myvec.capacity();
std::cout << "capacity: " << myvec.capacity() << std::endl;
std::cout << "size: " << myvec.size() << std::endl;
}
}
int main(int, char**) {
std::cout << std::endl << std::endl;
std::cout << "*********************" << std::endl << std::endl;
std::cout << "Booleans: " << std::endl << std::endl;
showSize<bool>();
std::cout << std::endl << std::endl;
std::cout << "*********************" << std::endl << std::endl;
std::cout << "Chars: " << std::endl << std::endl;
showSize<char>();
}
выход:
*********************
Booleans:
capacity: 0
size: 0
capacity: 64
size: 1
capacity: 128
size: 65
capacity: 256
size: 129
capacity: 512
size: 257
capacity: 1024
size: 513*********************
Chars:
capacity: 0
size: 0
capacity: 1
size: 1
capacity: 2
size: 2
capacity: 4
size: 3
capacity: 8
size: 5
capacity: 16
size: 9
capacity: 32
size: 17
capacity: 64
size: 33
capacity: 128
size: 65
capacity: 256
size: 129
capacity: 512
size: 257
capacity: 1024
size: 513
Таким образом, ключ в том, что емкость для bools увеличивается на 64 записи за раз (размер int или моя машина). Это намекает на то, что резервируется всего 8 байтов за раз.
Создать огромный vector<bool> и посмотрите на использование памяти программой.
Или просто проверить исходный код — вы можете посмотреть на vector заголовок.