Могут ли несколько прокси-классов создавать STV-доказательство битвектора?

хорошо известно, что std::vector<bool> не удовлетворяет требованиям Стандартного контейнера, главным образом потому, что упакованное представление предотвращает возврат T* x = &v[i] указателя к bool.

Мой вопрос: может ли это быть исправлено/смягчено, когда reference_proxy перегружает адрес operator&, чтобы вернуть указатель_proxy?

Прокси-указатель-указатель может содержать те же данные, что и reference_proxy в большинстве реализаций, а именно указатель на упакованные данные и маску, чтобы изолировать конкретный бит внутри указанного блока. В противном случае указатель pointer_proxy предоставит reference_proxy. По сути, оба прокси-сервера являются "жирными" указателями, которые, однако, по-прежнему довольно легки по сравнению с контейнерами-прокси на диске.

Вместо T* x = &v[0] можно было бы сделать auto x = &v[0] и без проблем использовать x как if(*x). Я также хотел бы написать for(auto b: v) { /* ... */ }

Вопросы: будет ли такой многопроцессорный подход работать с алгоритмами STL? Или некоторые алгоритмы действительно полагаются на требование, чтобы x должен был быть реальным bool*? Или требуется слишком много последовательных пользовательских преобразований, которые мешают этому работать? Я хотел бы знать любые препятствия, прежде чем пытаться полностью выполнить приведенный выше эскиз реализации.

UPDATE (на основе ответа @HowardHinnant и этого древнего обсуждения на comp.std.С++)

Вы можете пройти долгий путь, чтобы почти имитировать встроенные типы: для любого заданного типа T пара прокси (например, reference_proxy и iterator_proxy) может быть сделана взаимосогласованной в том смысле, что reference_proxy:: operator &() и iterator_proxy:: operator *() взаимно противоположны.

Однако в какой-то момент нужно сопоставить объекты-прокси, чтобы они велись так, как T * или T &. Для прокси-серверов итераторов можно перегрузить оператор → () и получить доступ к интерфейсу шаблона T без переопределения всех функций. Однако для ссылочных прокси-серверов вам нужно будет перегрузить operator.(), И это не разрешено в текущем С++ (хотя Sebastian Redl представил такое предложение на BoostCon 2013). Вы можете сделать многословную работу как элемент .get() внутри ссылочного прокси или реализовать весь интерфейс T внутри ссылки (это то, что делается для vector:: bit_reference), но это либо потеряет встроенный синтаксис или ввести пользовательские преобразования, которые не имеют встроенной семантики для преобразований типов (вы можете иметь не более одного определяемого пользователем преобразования для каждого аргумента).

Ответ 1

Мой вопрос: может ли это быть исправлено/смягчено, когда reference_proxy перегружает адрес оператора & вернуть pointer_proxy?

libС++ действительно делает это.

#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>. Это несоответствующее расширение для libС++. Но он делает запись генерического кода, который может быть создан на vector<bool>, гораздо более вероятно, чтобы скомпилировать и вести себя корректно.

Вопросы: будет ли такой мультипрокси-подход работать с STL алгоритмы? Или некоторые алгоритмы действительно полагаются на требование, чтобы x должен быть настоящим bool *? Или слишком много последовательных требуемые пользователем преобразования, которые мешают этому работать?

Все алгоритмы libС++ работают с 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. Но я не знаю, реализует ли какая-либо реализация, кроме libС++, и не обязана С++ 11.

Массив бит - это структура данных замечательная. Но, к сожалению, он плохо указан в стандарте С++. libС++ несколько устарел, чтобы продемонстрировать, что это может быть очень полезная и высокопроизводительная структура данных. Надеемся, что будущий стандарт С++ может мигрировать в этом направлении в пользу программиста на С++.

Ответ 2

Вначале я бы сказал, что на самом деле это будет больше зависеть от особенностей каждой отдельной реализации STL, поскольку она официально не соответствует стандартному требованию о том, что * reference_type будет lvalue T *. Итак, о потенциальных проблемах реализации:

Основная причина, по которой любой фрагмент кода явно зависит от указателя контейнера, являющегося реальным bool*, заключается в том, что алго использовал арифметику указателя, и в этом случае размер типа указателя становится релевантным. Арифметика указателей, хотя и обходила бы интерфейс итератора и, таким образом, побеждала бы главную цель всего проекта контейнера по-итератору STL. std::vector < > сам гарантированно будет смежным в С++ 11, что позволяет оптимизировать специализации как STL algos, так и компилятора для (:), оба из которых могут использовать арифметику указателя внутри. Если ваш тип не получен из std::vector, тогда это не должно быть проблемой; все должно просто принять вместо этого метод итератора.

Однако! STL-код может по-прежнему принимать указатели не для арифметики указателя, а для какой-то другой цели. В этом случае проблема заключается в синтаксисе Си ++. Например, ссылаясь на свой собственный вопрос:

Вместо T* x = &v[0] можно было бы сделать auto x = &v[0]

Любой шаблонный код в STL также должен будет сделать то же самое... и на данный момент кажется маловероятным, что реализация STL будет широко использовать auto. Могут быть и другие ситуации: попытки STL совершать умные трюки с изменением ценности r, которые заканчиваются неудачей, потому что они не ожидают несоответствующих ссылочных типов.

Относительно for(auto b: v) { /* ... */ }: Я не вижу причин, которые не должны работать. Я думаю, что это сгенерирует код, который будет намного менее эффективным, чем тот же самый вариант, который вы могли бы просто запустить через 15 минут (или меньше). Я только воспитываю его, так как вы упоминаете внутренности в OP, что отражает некоторое внимание к производительности. Вы также не сможете помочь, используя встроенные функции. Там ничто внутреннее не может сделать, так или иначе превосходит простой побитовый сдвиг для последовательного прохождения массива бит. Большая часть добавленных служебных данных будет из кода генерации компилятора, чтобы обновить значения и значения итератора итератора, а затем перезагрузить значение маски на следующей итерации. Он не сможет магически вывести то, что вы пытаетесь сделать, и превратить его в последовательный сдвиг op для вас. Он может, по крайней мере, иметь возможность оптимизировать этап обновления + обратной записи указателя, кэшируя его в регистр вне цикла, хотя, честно говоря, я был бы очень скептически настроен на основе моих опытов.

Здесь один из способов прохождения бит от начала до конца, просто для сравнения (версия, способная запускаться в любой произвольной точке в битовом потоке, потребует немного дополнительной логики установки):

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.
}