p2158 - Deprecate std::vector<bool>, promote std::tr2::dynamic_bitset and map a timeline for C++29

[ThePhD]

Not the paper we deserve,

but the paper we need.

[ThePhD]

Wording, for free from the TR2 release. Handled by Alisdair, apparently!

[ThePhD]

std::vector subverts expectation and we deserve not to violate vector's invariants. We can have equivalent functionality without destroying user expectation and typical C and C++ code that works with booleans in a non-bitpacked fashion.

The migration path is class std::vector<bool> : dynamic_bitset in C++23 with a deprecation warning attached to the class instance. Then, it should be removed + replaced proper in C++2z.

As a side note, we should also make sure to have a thorough discussion of specialization of iter_move and iter_swap for bit iterators, their benefits, and if its possible to have the begin/end for dynamic_bitset be considered a Random Access Range.

[Morwenn]

Motivation for free in a legendary post by Howard: https://isocpp.org/blog/2012/11/on-vectorbool

Previous deprecation proposal from 2007: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html

Corresponding NAD LWG issue that mentions wanting proxy iterators to fix std::vector<bool> but also wanting another container: https://cplusplus.github.io/LWG/issue96

That issue is actually interesting because it mentions previous attempts, mentions N1211 for which I've only found dead links, and also gives the vote results for the deprecation. Also it mentions that the SGI STL had a dedicated container for that, bitvector.

[Morwenn]

As for iter_move and iter_swap for std::vector<bool> iterators, I think it was intended by the Ranges TS, and if the wording isn't enough, it can probably solved as a library DR, or if we really need as a national body comment against C++20. Having the guarantee that it mostly does the right thing for range algorithms is clearly something we want sooner rather than later. And C++20 with the introduction of Ranges seem sto be the right time for that.

Here is the original motivation for proxy iterators from Eric Niebler, mentioning std::vector<bool>: http://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/

[Morwenn]

Also, while the original std::dynamic_bitset proposal from TR2 mentions that iterators are a future concern, we can surely address those concern right now by mandating that they use the bit iterators from P0237. It offers a few advantages:

• Using standard bit iterators for std::dynamic_bitset encourages such bit containers to do the same and provide a unifrom interface.
• If several containers do the same, it ends up with less template bloat and more chances that algorithms on such iterators are properly optimized because of more usage and thus more people asking for them to be fast.
• We can even mandate that every standard library algorithm works with bit iterators and throw the stone to implementers when there is a problem.

When it comes to implementation, dynamic_bitset has lived for years in Boost, and there's a TR2 era implementation in std::tr2:: in libstdc++. When it comes to bitset iterators themselves, they are already implemented in libc++ where several standard library algorithms have already been optimized for them.

[ThePhD]

We have support from the <bit> author to beef up some shiny new utilities. I'll be meeting him in Kona, to go over some of his work and see how we can help him out in pushing things towards C++23 directly rather than dumping things into the Library Fundamentals TS.

Until then, we continue to research and wait...

[ThePhD]

The avalanche of change has been set in motion: https://github.com/ThePhD/gsoc-2019-bit/blob/master/proposal/gsoc-2019.pdf

[ThePhD]

GSoC is underway for p0237 plus these containers. After implementation ships in GCC, will create a public implementation to compete with boost::dynamic_bitset...

[ThePhD]

Lost paper number.

[ThePhD]

Working with p0237 author Dr. Reverdy to create these containers and working with FSF in GSoC to get these into __gnu_cxx:: namespace by August.

[ThePhD]

The plan is set in motion.

https://twitter.com/thephantomderp/status/1144264236803198976

[ThePhD]

Use this place to mark down things that will be useful for the eventual paper:

GriwesToday at 9:55 AM
@ThePhD ...they either own their own iterators, or pass them verbatim to the underlying container

ThePhDToday at 9:56 AM
I can't pass them verbatim; I need to fill up the bits.

GriwesToday at 9:55 AM
I don't see a useful case where it's not one or the other

ThePhDToday at 9:57 AM
If I'm not at the edge of the underlying container's value_type, I need to insert bits into the current underlying container's position until I am.

GriwesToday at 9:58 AM
But... You need your own iterator type anyway, no?
Some sort of a combination of the iterator of the underlying storage and bit_iterator

ThePhDToday at 9:58 AM
If I get a const_iterator that is just bit_iterator<__gnu_cxx::normal_iterator<const unsigned long long*>>, even if I access .base() that base iterator is still const-ified.

GriwesToday at 9:58 AM
That's fine
You're writing a stdlib type
You have access to the guts of the bit iterator
But as I said, I'd probably wrap that into a dedicated class

ThePhDToday at 9:59 AM
My problem isn't that my iterator is non-const: my problem is the core iterator is const.

GriwesToday at 10:00 AM
But again, even if you don't, you have access to bit_iterator insides
Also
I'm pretty sure you can construct this in a way where the issue of the core iterator being const isn't even there

ThePhDToday at 10:02 AM
I could just use non-const iterators inside of a const_bit_iterator<regular_iterator>
Oh.
So what I can do is take a value_type& out.
Save the value_type& of the last thing I am going to- no wait nevermind that's stupid.
Yeah I have no way around this one, honestly.

GriwesToday at 10:05 AM
So yeah, you don't need to end up with a const iterator of the underlying storage
Because you can always get the begin and end iterators, nonconst, whenever you modify
And do const bit iterators of those in const qualified functions
Eats slightly more storage? Sure. I don't think that matters at all though.
Implementations that care could optimize for iterator types they know

[ThePhD]

It's done: https://github.com/ThePhD/itsy_bitsy

Now it's time for the papers.

[ThePhD]

Need papers for 3 things:

• Bit Utilities (std::bit_iterator<Iterator>, std::bit_pointer<Iterator>, std::bit_reference<Reference, Mask>)
• Bit Container Adapter and Range Adapter (std::bit_sequence<Container>, std::bit_view<Range, Bounds>)
• (Optionally SBO) Optimized Bit Container (std::small_bit_vector<T, N, Allocator>)