On Mon, Feb 22, 2021 at 8:30 AM Jason McKesson via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> On Mon, Feb 22, 2021 at 7:39 AM Shipurian via Std-Proposals
> <std-proposals_at_[hidden]> 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_at_[hidden]
> > https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>