Могут ли несколько прокси-классов составить битовый вектор, защищенный от STL?

Мой вопрос: можно ли это исправить/смягчить, когда 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? Или некоторые алгоритмы действительно полагаются на требование, чтобы x был настоящим логическим значением*? Или требуется слишком много последовательных пользовательских преобразований, которые мешают этому работать?

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

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

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

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

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

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

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

Относительно for(auto b: v) { /* ... */ }: не вижу причин, по которым это не должно работать. Я думаю, что он будет генерировать код, который будет гораздо менее эффективным, чем та же версия, которую вы могли бы просто свернуть самостоятельно за 15 минут (или меньше). Я упоминаю об этом только потому, что вы упомянули внутренние элементы в 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.
}