Могут ли несколько прокси-классов образовывать битовый вектор, защищенный от STL?
Это хорошо известный тот std::vector<bool> не удовлетворяет контейнерным требованиям Стандарта, главным образом потому, что упакованное представление предотвращает T* x = &v[i] от возврата указателя на бул.
Мой вопрос: это может быть исправлено / смягчено, когда reference_proxy перегружает адрес operator& вернуть указатель_прокси?
Указатель-прокси может содержать те же данные, что и reference_proxy в большинстве реализаций, а именно указатель на упакованные данные и маску для выделения конкретного бита внутри указанного блока. Переадресация pointer_proxy выдаст reference_proxy. По сути, оба прокси являются «жирными» указателями, которые, однако, все еще довольно легки по сравнению с дисковыми прокси-контейнерами.
Вместо T* x = &v[0] тогда можно было бы сделать auto x = &v[0]и использовать x лайк if(*x) без проблем. Я также хотел бы иметь возможность написать for(auto b: v) { /* ... */ }
Вопросы: будет ли такой мульти-прокси подход работать с алгоритмами STL? Или некоторые алгоритмы действительно полагаются на требование x должен быть реальным bool*? Или требуется слишком много последовательных пользовательских преобразований, чтобы это не сработало? Я хотел бы знать любое из таких препятствий, прежде чем пытаться полностью завершить приведенный выше эскиз реализации.
ОБНОВИТЬ (на основе ответа @HowardHinnant и этого древняя дискуссия на comp.std.c ++)
Вы можете пройти долгий путь, почти имитируя встроенные типы: для любого данного типа T пара прокси (например, reference_proxy и iterator_proxy) может быть сделана взаимно согласованной в том смысле, что reference_proxy :: operator&() и iterator_proxy :: operator * () обратны друг другу.
Однако в какой-то момент нужно сопоставить прокси-объекты обратно, чтобы они вели себя как T * или T&, Для прокси-серверов итераторов можно перегрузить оператор -> () и получить доступ к интерфейсу шаблона T без переопределения всей функциональности. Однако для ссылочных прокси вам потребуется перегрузить оператор. (), А это не разрешено в текущем C ++ (хотя Себастьян Редл представил такое предложение на BoostCon 2013). Вы можете сделать подробный обходной путь, например член .get () внутри ссылочного прокси, или реализовать весь интерфейс T внутри ссылки (это то, что делается для vector :: bit_reference), но это либо утратит встроенный синтаксис или ввести пользовательские преобразования, которые не имеют встроенной семантики для преобразования типов (вы можете иметь не более одного пользовательского преобразования на аргумент).
Решение
Мой вопрос: это можно исправить / смягчить, когда
reference_proxy перегружает адрес оператора& вернуть
pointer_proxy?
Libc ++ на самом деле делает это.
#include <vector>
#include <cassert>
int main()
{
std::vector<bool> v(1);
std::vector<bool>::pointer pb = &v[0];
assert(*pb == false);
*pb = true;
assert(v[0] == true);
std::vector<bool>::const_pointer cbp = pb;
assert(*cbp == true);
v[0] = false;
assert(*cbp == false);
}
Это даже распространяется на const_pointer а также const_reference способами, которые имитируют одни и те же типы для vector<int>, Это несоответствующее расширение для libc ++. Но это делает написание общего кода, который может быть создан на vector<bool> гораздо больше шансов скомпилировать и вести себя правильно.
Вопросы: будет ли такой мульти-прокси подход работать с STL
алгоритмы? Или некоторые алгоритмы действительно полагаются на требование
х должен быть настоящим придурком *? Или слишком много подряд
Требуются ли определенные пользователем преобразования, которые мешают этому работать?
Все алгоритмы libc ++ работают с vector<bool>, Некоторые из них с довольно впечатляющее выступление. Один алгоритм в частности должен иметь особый режим, который стандарт, к сожалению, не предусматривает:
#include <vector>
#include <cassert>
int main()
{
std::vector<bool> v(1);
bool b = true;
assert(v[0] == false);
assert(b == true);
std::swap(b, v[0]);
assert(v[0] == true);
assert(b == false);
}
Это очень легко реализовать. Нужно просто убедиться, swap работает для любой комбинации bool а также vector<bool>::reference, Но я не знаю, делает ли это какую-либо реализацию, кроме libc ++, и это не требуется C ++ 11.
Массив битов является замечательно структура данных. Но, к сожалению, это плохо указано в стандарте C ++. libc ++ несколько объявил вне закона, чтобы продемонстрировать, что это может быть очень полезной и высокопроизводительной структурой данных. Надежда состоит в том, что будущий стандарт C ++ может перейти в этом направлении в пользу программиста C ++.
Другие решения
Сначала я бы сказал, что это будет зависеть в большей степени от особенностей каждой отдельной реализации STL, поскольку он официально не соответствует стандартному требованию, что * reference_type должен быть lvalue из T *. Что касается потенциальных вопросов реализации:
Основная причина, по которой любой фрагмент кода будет явно зависеть от того, является ли указатель контейнера реальный bool* если алгоритм использовал арифметику указателя, то в этом случае размер типа указателя становится релевантным. Арифметика с указателями, однако, должна обходить интерфейс итератора и, таким образом, сводить на нет основную цель всей конструкции контейнера STL за итератором. станд :: вектор<> Сам по себе гарантированно является смежным в C ++ 11, что позволяет оптимизировать специализацию как STL-алгоритмов, так и компилятора для (:), которые оба могут использовать арифметику указателей внутри. Если ваш тип не является производным от std :: vector, тогда это не должно быть проблемой; вместо этого все должно предполагать метод итератора.
Тем не мение! STL код еще может указатели не для арифметики указателей, а для какой-то другой цели. В этом случае проблема С ++ синтаксис. Например, процитировал свой вопрос:
Вместо
T* x = &v[0]тогда можно было бы сделатьauto x = &v[0]
Любой шаблонный код в STL также должен будет делать то же самое … и в этот момент кажется маловероятным, что реализации STL будут широко использовать auto, Могут быть и другие ситуации, когда STL пытается выполнить хитрые приемы приведения значений r, которые в итоге заканчиваются неудачей, поскольку он не ожидает несовпадающих ссылочных типов.
относительно for(auto b: v) { /* ... */ }Я не вижу причин, которые не должны работать. Я думаю, что он сгенерирует код, который будет гораздо менее эффективным, чем та же версия, которую вы могли бы просто развернуть за 15 минут (или меньше). Я только поднимаю это, так как вы упоминаете встроенные функции в ОП, что предполагает некоторое внимание к производительности. Вы не сможете выручить это, используя встроенные функции. Нет ничего такого, что могло бы превзойти простой побитовый сдвиг для последовательного обхода массива битов. Большая часть дополнительных издержек будет исходить от кода компилятора, который обновляет указатель итератора и значения маски, а затем перезагружает значение маски на следующей итерации. Он не сможет волшебным образом сделать вывод о том, что вы пытаетесь сделать, и превратить его в опцию последовательного сдвига для вас. По крайней мере, он может оптимизировать этап обновления + записи указателя, кэшируя его в регистр вне цикла, хотя, честно говоря, я буду очень скептически относиться к своему опыту.
Вот один из способов прохождения битов от начала до конца, просто для сравнения (версия, способная запускаться в любой произвольной точке потока битов, потребует немного дополнительной логики настройки):
uint64_t* pBitSet = &v[-1]; // gets incremented on first iteration through loop.
uint64_t curBitSet = v[0];
for (int i=0; i<v.length(); ++i) {
if ((i % 64) == 0) {
curBitSet = *(++pBitSet);
}
int bit = curBitSet & 1;
curBitSet >>= 1;
// do stuff based on 'bit' here.
}