Являются ли std :: fill, std :: copy специализированными для std :: vector & lt; bool & gt ;?
Думая об этом вопрос Я начинаю задаваться вопросом, если std::copy() и / или std::fill специализированы (я действительно имею в виду оптимизированы) для std::vector<bool>,
Требуется ли это стандартом C ++ или, может быть, это распространенный подход поставщиков библиотек C ++ 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> не большая проблема для поставщика библиотеки?
Следующий связанный вопрос: могу ли я (или кто-либо еще 🙂 специализировать такие алгоритмы, скажем, std::vector<bool>если не специализирован? Это разрешено стандартом C ++? Я знаю, что это будет непереносимо — но только для одной выбранной библиотеки C ++ std? Предполагая, что я (или кто-то еще) найду способ добраться до std::vector<bool> интимные части тела.
Решение
STD — это библиотека только заголовков, она поставляется вместе с вашим компилятором. Вы можете сами заглянуть в эти заголовки. Для GCC vector<bool> имплементация в stl_bvector.h, Вероятно, это будет тот же файл для других компиляторов. И да, есть специализированная fill (посмотрите рядом __fill_bvector).
Другие решения
Оптимизация нигде не обязательна в стандарте. Предполагается, что это проблема «качества реализации», если можно применить оптимизацию. Однако асимптотическая сложность большинства алгоритмов ограничена.
Оптимизация допускается при условии, что правильная программа ведет себя в соответствии со стандартными мандатами. Примеры, которые вы спрашиваете об оптимизации, включающей стандартные алгоритмы с использованием итераторов на std::vector<bool>, могут достичь своей цели практически любым способом, который реализация сочтет нужным, потому что нет способа отслеживать, как они реализуются. Тем не менее, я очень сомневаюсь, что есть какая-либо стандартная реализация библиотеки, оптимизирующая операции на std::vector<bool>, Большинство людей, кажется, думают, что эта специализация — мерзость в первую очередь и что она должна исчезнуть.
Пользователь может создавать специализации библиотечных типов только в том случае, если специализация включает хотя бы один определенный пользователем тип. Я не думаю, что пользователю разрешено предоставлять какую-либо функцию в пространстве имен std вообще: в этом нет необходимости, потому что все такие функции будут включать определенный пользователем тип и, таким образом, будут находиться в пространстве имен пользователя. Сформулированы по-другому: я думаю, что вам не повезло в отношении оптимизации алгоритмов для std::vector<bool> в настоящее время. Вы можете рассмотреть возможность добавления оптимизированных версий в реализации с открытым исходным кодом (например, libstdc++ а также libc++), тем не мение.
23.2.5 Вектор класса из C ++ Международный стандарт идет так далеко, чтобы сказать нам
Для оптимизации распределения пространства предусмотрена специализация вектора для элементов bool:
после чего предоставляется специализация bitset. Это насколько стандарт идет в отношении vector<bool>поставщики должны реализовать его, используя набор битов для оптимизации пространства. Оптимизация для места идет с ценой здесь, чтобы не оптимизировать для скорости.
Получить книгу из библиотеки легче, чем найти книгу, если она находится между всеми библиотечными книгами, скрепленными в контейнерах …
Возьмите свой пример, вы пытаетесь сделать std::fill или же std::copy от начала до конца. Но это не всегда так, иногда это не просто отображение целого байта. Так что это небольшая проблема с точки зрения оптимизации скорости. Это просто для случая, когда вам придется менять каждый бит на единицу, это просто изменение байтов на 0xF, но здесь это не так; это станет намного сложнее, если вы будете изменять только определенные биты байта. Затем вам нужно будет вычислить, каким будет байт; это не тривиальная вещь*, или, по крайней мере, не как элементарная операция на текущем оборудовании.
Это история преждевременной оптимизации, она хороша с точки зрения пространства, но ужасна с точки зрения производительности.
Имеет "is a multiple of 8 bits" проверка стоит накладных расходов? Я сомневаюсь.
* Мы говорим здесь о нескольких битах, так как в случае только одного бита вы, конечно, можете выполнить битовую операцию.