Существуют ли std:: fill, std:: copy для std::vector <bool>?

Когда вы думаете об этом question, я начинаю задаваться вопросом, являются ли std::copy() и/или std::fill специализированными (я действительно подразумеваю оптимизацию) для std::vector<bool>.

Требуется ли это стандартом С++ или, возможно, это общий подход к поставщикам библиотеки std С++?

Проще говоря, мне интересно узнать, есть ли следующий код:

std::vector<bool> v(10, false);
std::fill(v.begin(), v.end(), true);

в любом случае лучше/отличается от этого:

std::vector<bool> v(10, false);
for (auto it = v.begin(); it != v.end(); ++it) *it = true;

Чтобы быть очень строгим - можете, скажем: std::fill<std::vector<bool>::iterator>() перейти во внутреннее представление std::vector<bool> и установить их все байты вместо отдельных битов? Я полагаю, что создание std::fill друга std::vector<bool> не является большой проблемой для поставщика библиотеки?

[ОБНОВЛЕНИЕ]

Следующий связанный вопрос: могу ли я (или кто-либо еще:) специализировать такие алгоритмы для let say std::vector<bool>, если не уже специализированный? Это разрешено стандартом С++? Я знаю, что это будет не переносимым - но только для одной выбранной std библиотеки С++? Предполагая, что я (или кто-либо другой) найдет способ добраться до std::vector<bool> частных частей.

Ответ 1

STD - это только библиотека заголовков, и она поставляется вместе с вашим компилятором. Вы можете сами изучить эти заголовки. Для GCC vector<bool> impelemtation находится в stl_bvector.h. Вероятно, это будет тот же файл для других компиляторов. И да, есть специализированный fill (посмотрите около __fill_bvector).

Ответ 2

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

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

Пользователю разрешено создавать специализации только для типов библиотек, если специализация включает хотя бы один пользовательский тип. Я не думаю, что пользователю разрешено предоставлять любую функцию в пространстве имен std вообще: нет никаких потребностей, потому что все такие функции будут включать определенный пользователем тип и, таким образом, будут найдены в пространстве имен пользователей. Сформулировано по-другому: я думаю, вам не повезло в том, что в настоящее время алгоритмы оптимизированы для std::vector<bool>. Однако можно рассмотреть возможность создания оптимизированных версий для реализации с открытым исходным кодом (например, libstdc++ и libc++).

Ответ 3

23.2.5. Вектор класса из Международный стандарт С++ позволяет сообщить нам

Для оптимизации распределения пространства предоставляется специализация вектора для элементов bool:

после чего предоставляется спецификация битового набора. Что касается стандарта, относящегося к vector<bool>, вендорам необходимо реализовать его с помощью битрейта для оптимизации пространства. Оптимизация пространства требует затрат здесь, чтобы не оптимизировать скорость.

Легче получить книгу из библиотеки, чем найти книгу, если бы она была между всеми библиотечными книгами, скрепленными близко друг к другу в контейнерах....

Взять пример, вы пытаетесь сделать std::fill или std::copy от начала до конца. Но это не всегда так, иногда это просто не просто отображение всего байта. Итак, это небольшая проблема с точки зрения оптимизации скорости. Легко для случая, когда вам нужно будет изменить каждый бит на один, просто изменив байты на 0xF, но это не так. это становится намного сложнее, если вы должны изменять только некоторые биты байта. Затем вам нужно будет вычислить, каков будет байт; что не тривиально делать ^* или, по крайней мере, не как атомную операцию на текущем оборудовании.

Это преждевременная история оптимизации, она хороша с точки зрения пространства, но ужасна с точки зрения производительности.

Есть ли проверка "is a multiple of 8 bits" накладные расходы? Я в этом сомневаюсь.

_{* Здесь мы говорим о нескольких битах, так как это всего лишь один бит, вы можете, конечно, выполнить небольшую операцию.}