Could multiple proxy classes make up a STL-proof bitvector?

Question

It's well known that std::vector<bool> does not satisfy the Standard's container requirements, mainly because the packed representation prevents T* x = &v[i] from returning a pointer to a bool.

My question is: can this be remedied/mitigated when the reference_proxy overloads the address-of operator& to return a pointer_proxy?

The pointer-proxy could contain the same data as the reference_proxy in most implementations, namely a pointer into the packed data and a mask to isolate the particular bit inside the block pointed to. Indirection of the pointer_proxy would then yield the reference_proxy. Essentially both proxies are "fat" pointers, which are, however, still rather light-weight compared to disk-based proxy containers.

Instead of T* x = &v[0] one could then do auto x = &v[0], and use x like if(*x) without problems. I would also like to be able to write for(auto b: v) { /* ... */ }

Questions: would such a multi-proxy approach work with the STL's algorithms? Or do some algorithms really rely on the requirement that x needs to be a real bool*? Or are there too many consecutive user-defined conversions required that prevent this to work? I'd like to know any of such obstructions before trying to fully complete the above implementation sketch.

---

UPDATE (based on @HowardHinnant 's answer and this ancient discussion on comp.std.c++)

You can come a long way to almost mimic the builtin types: for any given type T, a pair of proxies (e.g. reference_proxy and iterator_proxy) can be made mutually consistent in the sense that reference_proxy::operator&() and iterator_proxy::operator*() are each other's inverse.

However, at some point one needs to map the proxy objects back to behave like T* or T&. For iterator proxies, one can overload operator->() and access the template T's interface without reimplementing all the functionality. However, for reference proxies, you would need to overload operator.(), and that is not allowed in current C++ (although Sebastian Redl presented such a proposal on BoostCon 2013). You can make a verbose work-around like a .get() member inside the reference proxy, or implement all of T's interface inside the reference (this is what is done for vector::bit_reference), but this will either lose the builtin syntax or introduce user-defined conversions that do not have builtin semantics for type conversions (you can have at most one user-defined conversion per argument).

Poplar

C++11 requires reference_type to be lvalue of T, so you would not suffice the container requirements. – Ruler

@Ruler Thanks, I know that it is part of the requirements. But where and how exactly would proxy references + proxy pointers break down? – Poplar

Answer 1

My question is: can this be remedied/mitigated when the reference_proxy overloads the address-of operator& to return a pointer_proxy?

libc++ actually does this.

#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);
}

It even extends to const_pointer and const_reference in ways that mimic the same types for vector<int>. This is a non-conforming extension for libc++. But it makes writing generic code which might be instantiated on vector<bool> far more likely to compile and behave correctly.

Questions: would such a multi-proxy approach work with the STL's algorithms? Or do some algorithms really rely on the requirement that x needs to be a real bool*? Or are there too many consecutive user-defined conversions required that prevent this to work?

All of libc++'s algorithms work with vector<bool>. Some of them with quite spectacular performance. One algorithm in particular must have special treatment which the standard unfortunately does not mandate:

#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);
}

This is very easy for the implementation to accomplish. One simply needs to make sure swap works for any combination of bool and vector<bool>::reference. But I don't know if any implementation besides libc++ does this, and it is not mandated by C++11.

An array of bits is a wonderful data structure. But unfortunately it is poorly specified in the C++ standard. libc++ has gone somewhat outlaw to demonstrate that this can be a very useful and high performance data structure. The hope is that a future C++ standard may migrate in this direction to the benefit of the C++ programmer.

Whaling

+1 and accepted! I wish I had found the bit_reference header at the libc++ SVN site before... Even more incentives to start compiling the latest Clang/libc++ on Linux (where are those distros that provide packages for Clang >= 3.1??) – Poplar

I wonder if it would make sense to define a proxy_traits<T> template (similar to allocator_traits<T>) that STL containers could use in order to decide on their implementation strategy (disk-based, packed representation, etc.)? – Poplar

Answer 2

Offhand I would say first, that it will actually depend more on the particulars of each individual STL implementation since it doesn't officially conform to the standard requirement that a *reference_type to be lvalue of T*. So regarding potential implementation issues:

The main reason any piece of code would be explicitly dependent on the container's pointer being a real bool* is if the algo was using pointer arithmetic, in which case the size of the pointer type becomes relevant. Pointer arithmetic though would bypass the iterator interface and thus defeat the main purpose of the whole STL container-by-iterator design. std::vector<> itself is guaranteed to be contiguous in C++11, which allows optimized specializations of both STL algos and compiler for(:), both of which may use pointer arithmetic internally. If your type isn't derived from std::vector then that shouldn't be an issue; everything should just assume the iterator method instead.

However! STL code may still take pointers not for the purpose of pointer arithmetic but rather for some other purpose. In this case the problem is C++ syntax. Eg, quoting your own question:

Instead of T* x = &v[0] one could then do auto x = &v[0]

Any templated code in the STL will also have to do the same thing... and that seems entirely unlikely at this point that STL implementations will be making wide use of auto. There may be other situations were the STL attempts to do clever r-value casting tricks that end up failing because it isn't expecting mismatched reference types.

Regarding for(auto b: v) { /* ... */ }: I see no reason that shouldn't work. I think it will generate code that will be far less efficient than the same version you could just roll yourself in 15 mins (or less). I only bring it up since you mention intrinsics in the OP, which imples some consideration for performance. You won't be able to help it out using intrinsics either. There's nothing an intrinsic can do that somehow surpasses a simple bitwise shift for sequentially traversing an array of bits. Most of the added overhead will be from the compiler generating code to update the iterator pointer and mask values, and then reload the mask value on the next iteration. It won't be able to magically deduce what you're trying to do and turn it into a sequential shift op for you. It may at least be able to optimize out the pointer update+writeback stage by caching it into a register outside the loop, though honestly I'd be very skeptical based on my experiences.

Here's one way for going through bits from start to end, just for sake of comparison (a version capable of starting at any arbitrary point in the bitstream would require a little extra setup logic):

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

Cosmopolitan

If I define typdef pointer_proxy pointer; and typedef reference_proxy reference;, wouldn't an STL algorithm use pointer x = &v[0];? Otherwise what is the point of having these nested typedefs inside STL containers? And to get proper pointer arithmetic, I could always overload operator+ for pointer_proxy, right? – Poplar

Regarding hand-rolling stuff in 15 minutes: I know how to iterate using bit-twiddling. But such a bitvector would be an implementation detail and has to conform to more general STL interfaces. Howard Hinnant wrote a recent blog isocpp.org/blog/2012/11/on-vectorbool on how to overload many STL algorithms for bit vector iterators. But since I am not an STL library author, I wonder if I can get some of the bang from using proxy classes. – Poplar

If the STL implementation sticks to using the typedefs, then yes in theory that should work. Since the standard doesn't seem to explicitly require it (eg, by making the statement that the type can be known), an implementation would not be incorrect to bypass the pointer type. So the simple answer regarding the container matching the standard is still "no." This could be viewed as a defect in the standard (there are many). Often the STL implementations hold themselves to a higher standard than even the standard puts forth, and those higher standards sometimes become the official standard. – Cosmopolitan

On pointer arithmetic: Overloading operator+ and everything else too except for mult and div operations, pretty much. I think that should do the trick, so long as nothing attempts to cast the pointer into an integer, use sizeof(T) arithmetic, and then back again. (which I'm quite sure never happens in any STL implementation ever). – Cosmopolitan