Hello,

bitset has a number of interesting functions, but it does not have any
find_{first,next,prev,last}. The dynamic_bitset proposal (N2050) has
them, so it looks like other people find them useful.

In the library issue 1112, I see there is plan to add a limited form
of iterator to bitset. Is the plan to let implementations overload
std::find on this iterator? Or is it just not what bitset is for?

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 3 Sep., 21:09, Marc <marc.gli...@gmail.com> wrote:
> bitset has a number of interesting functions, but it does not have any
> find_{first,next,prev,last}. The dynamic_bitset proposal (N2050) has
> them, so it looks like other people find them useful.

Agreed.

> In the library issue 1112, I see there is plan to add a limited form
> of iterator to bitset. Is the plan to let implementations overload
> std::find on this iterator? Or is it just not what bitset is for?

Why should implementations be required to overload the algorithm
std::find? With the currently suggested resolution of LWG issue
1112 the functionality does exist and you could simply write:

#include <bitset>
#include <algorithm>
#include <cassert>

int main() {
   std::bitset<5> bs("00010");
   auto beg = begin(bs);
   auto it = std::find(beg, end(bs));
   assert(it - beg == 1);
}

If you ask so, because a special implementation that
would take advantage of the internal structure of bitset
could probably be much more efficient using platform-
specific bit operations, I suggest to hope for something
like dynamic_bitset, or to ask for addition of such a
member function to bitset. The latter would match the
usual style the container library handles this:

Container-specific algorithms are typically provided as
member functions of the corresponding container.

HTH & Greetings from Bremen,

Daniel Kr   gler


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Sep 3, 3:07 pm, Daniel Kr   gler <daniel.krueg...@googlemail.com>
wrote:
> On 3 Sep., 21:09, Marc <marc.gli...@gmail.com> wrote:
>
> > bitset has a number of interesting functions, but it does not have any
> > find_{first,next,prev,last}. The dynamic_bitset proposal (N2050) has
> > them, so it looks like other people find them useful.
>
> Agreed.
>
> > In the library issue 1112, I see there is plan to add a limited form
> > of iterator to bitset. Is the plan to let implementations overload
> > std::find on this iterator? Or is it just not what bitset is for?
>
> Why should implementations be required to overload the algorithm
> std::find?

Not required. Just that it would be considered a normal thing to do.

> With the currently suggested resolution of LWG issue
> 1112 the functionality does exist and you could simply write:
>
> #include <bitset>
> #include <algorithm>
> #include <cassert>
>
> int main() {
>    std::bitset<5> bs("00010");
>    auto beg = begin(bs);
>    auto it = std::find(beg, end(bs));
>    assert(it - beg == 1);
>
> }

Since bitset only gets its iterators through the global begin function
and not through begin/cbegin (or even rbegin) member functions, even
though they are regular iterators, I was wondering if we were really
supposed to use them for anything but the new for loops. Thank you for
the precision.

> If you ask so, because a special implementation that
> would take advantage of the internal structure of bitset
> could probably be much more efficient using platform-
> specific bit operations,

Which seems allowed with the current 1112 proposed resolution.

> I suggest to hope for something
> like dynamic_bitset,

I most certainly do :-)

> or to ask for addition of such a
> member function to bitset. The latter would match the
> usual style the container library handles this:
>
> Container-specific algorithms are typically provided as
> member functions of the corresponding container.

Assuming iterators, it is probably easier to leave it as a QOI issue
for std::find (and other related algos), although it would indeed be
better to let it match the usual style, so I may try to ask for it
(once I get some practice asking for the new heap operations discussed
in clc++m today). Without iterators, the functions would have to
return an index instead (good thing that size_t(-1) can never be the
index of a real element and can serve as a not_found answer).

Thank you for your answer.


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 4 Sep., 01:43, Marc <marc.gli...@gmail.com> wrote:
> On Sep 3, 3:07 pm, Daniel Kr   gler <daniel.krueg...@googlemail.com>
> wrote:
>
> > On 3 Sep., 21:09, Marc <marc.gli...@gmail.com> wrote:

[..]

> > > In the library issue 1112, I see there is plan to add a limited form
> > > of iterator to bitset. Is the plan to let implementations overload
> > > std::find on this iterator? Or is it just not what bitset is for?
>
> > Why should implementations be required to overload the algorithm
> > std::find?
>
> Not required. Just that it would be considered a normal thing to do.

OK, I misunderstood your question because of the question
for a plan, which did sound like an obvious miss that needs
to be fixed.

> > With the currently suggested resolution of LWG issue
> > 1112 the functionality does exist and you could simply write:
>
> > #include <bitset>
> > #include <algorithm>
> > #include <cassert>
>
> > int main() {
> >    std::bitset<5> bs("00010");
> >    auto beg = begin(bs);
> >    auto it = std::find(beg, end(bs));
> >    assert(it - beg == 1);
>
> > }
>
> Since bitset only gets its iterators through the global begin function
> and not through begin/cbegin (or even rbegin) member functions, even
> though they are regular iterators, I was wondering if we were really
> supposed to use them for anything but the new for loops.

Yes, the new non-concept range API is explicitly supposed to
be used where-ever you need an iterator-range of a range-like beast.

The free function overloads begin() and end() are just the
counterparts
of the functionality of a language concept Range.

> > If you ask so, because a special implementation that
> > would take advantage of the internal structure of bitset
> > could probably be much more efficient using platform-
> > specific bit operations,
>
> Which seems allowed with the current 1112 proposed resolution.

1112 does only suggest the addition of begin()/end() overloads
accepting std::bitset and returning an iterator range corresponding
to that bitset object. Of course you could simply rely on the
general freedom of library implementors to add machinery
to fall back to specialized algorithm implementations as long
as these satisfy the general library requirements, especially
[global.functions].
It is very probably that in any relevant library implementation the
provided iterators for bitset will already use special platform
support to implement the iterator operations, but these are not
necessarily the same as those used in a platform-supported
find_first function or first_first_not function, which can use
additional
functionality of the hardware.

> > or to ask for addition of such a
> > member function to bitset. The latter would match the
> > usual style the container library handles this:
>
> > Container-specific algorithms are typically provided as
> > member functions of the corresponding container.
>
> Assuming iterators, it is probably easier to leave it as a QOI issue
> for std::find (and other related algos), although it would indeed be
> better to let it match the usual style, so I may try to ask for it
> (once I get some practice asking for the new heap operations discussed
> in clc++m today). Without iterators, the functions would have to
> return an index instead (good thing that size_t(-1) can never be the
> index of a real element and can serve as a not_found answer).

<nod>, I think that if member functions are provided, these would be
/probably/ index-based. Personally I think it would be worth to
consider
to provide them.

Greetings from Bremen,

Daniel Kr   gler


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]