C++ Logo

STD-PROPOSALS

Advanced search

Subject: Re: [std-proposals] Include boost::dynamic_bitset into the standard library
From: blaoi_at_[hidden]
Date: 2021-02-22 11:47:14


I would like to share the article that was behind the paywall (see the attached pdf file).

However, you're right about the implementation changes for std::vector<bool> that occurred since the release of the article.

22 févr. 2021 à 18:26 de std-proposals_at_[hidden]:

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





STD-PROPOSALS list run by std-proposals-owner@lists.isocpp.org

Standard Proposals Archives on Google Groups