On Mon, Feb 22, 2021 at 8:30 AM Jason McKesson via Std-Proposals <std-proposals@lists.isocpp.org> wrote:
On Mon, Feb 22, 2021 at 7:39 AM Shipurian via Std-Proposals
<std-proposals@lists.isocpp.org> wrote:
>
> Many algorithmic problems and low-level programming rely on a binary solution (TSP, Knapsack problem, etc). Despite the existence of std::bitset<N>, a fixed-size container for manipulating the bits. There is no other way than using a std::vector<bool> to deal with dynamic bit vectors.
>
> However, using std::vector<bool> is really slow compared to other solutions : https://doi.org/10.1145/1899503.1899530.

The article you have linked to is behind a paywall, so it's not easy
to figure out what the methodology was for determining code
performance. Equally importantly, without the paper, we can't tell
whether this is an artifact of the implementations (ie: could
`vector<bool>` be better) or a requirement due to the interface needs
of `vector<bool>`.

Also, it's been 10 years since that paper was published. How much has
changed in that time in terms of implementations.

I don't know what the linked article is about, but here's a public one from Howard Hinnant: https://isocpp.org/blog/2012/11/on-vectorbool, with lots of numbers.
 

> Hence, I would like to propose to implement the boost::dynamic_bitset to work with dynamic binary vectors and use them in dedicated heuristics or in regular problems.

That having been said, having a dynamic_bitset would move us a step
along the path of removing `vector<bool>` entirely, so long as the
interface is a good replacement for it (not needing much if any
changes to existing code besides what type gets used).

> --
> Std-Proposals mailing list
> Std-Proposals@lists.isocpp.org
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals