Hi,

According to the plan came up in this thread:

  https://groups.google.com/a/isocpp.org/forum/#!searchin/std-proposals/vector%3Cbool%3E/std-proposals/8kQzWI61ROU/weqzTDLX0MgJ

  TS (or C++17): std::bitvector
  C++17: deprecate vector<bool>
  C++2x: remove vector<bool> the specialization

Here is an initial implementation of the class I propose to
be added to deprecate `vector<bool>`, namely `bitvector`,
for evaluation:

  https://github.com/lichray/bitvector

, where the `bitvector` is actually a specialization of `basic_bitvector`

  typedef basic_bitvector<std::allocator<unsigned long>> bitvector;

Different from `boost::dynamic_bitset`, my design is *not* to let
the storage type become a part of the interface: there is no public
typedef mentioning `block_type`, and there is no member function
mentioning `block_type`, too.  `basic_bitvector` accepts only one
template argument, which is the `allocator_type`, and allocates
whatever the allocator's `value_type` is -- only unsigned integers
can well-formly instantiate the template of course.

The rationale is to pretend we have a class storing "bits", not
`bool`s, not "blocks" either.  Just, since we can not represent
a real "bit", there is no `value_type` defined, like
`boost::dynamic_bitset`.  Furthermore, we want all of the
`basic_vector<allocator<Block>>`s behave in exactly the same
way like the `vector<bit, allocator<bit>>`, two `basic_bitvector`s
with convertible allocator types but different storage types
are implicitly convertible to each other.

Almost all other interfaces follow `std::bitset`, like what
`boost::dynamic_bitset` did.  Some interfaces follow
`vector<bool>`, considering `bitvector`'s variable-length
property.

Comments are welcome.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

On Aug 25, 2013, at 1:25 PM, Zhihao Yuan <zy@miator.net> wrote:

> Hi,
>=20
> According to the plan came up in this thread:
>=20
>  https://groups.google.com/a/isocpp.org/forum/#!searchin/std-proposals/ve=
ctor%3Cbool%3E/std-proposals/8kQzWI61ROU/weqzTDLX0MgJ
>=20
>  TS (or C++17): std::bitvector
>  C++17: deprecate vector<bool>
>  C++2x: remove vector<bool> the specialization
>=20
> Here is an initial implementation of the class I propose to
> be added to deprecate `vector<bool>`, namely `bitvector`,
> for evaluation:
>=20
>  https://github.com/lichray/bitvector
>=20
> , where the `bitvector` is actually a specialization of `basic_bitvector`
>=20
>  typedef basic_bitvector<std::allocator<unsigned long>> bitvector;
>=20
> Different from `boost::dynamic_bitset`, my design is *not* to let
> the storage type become a part of the interface: there is no public
> typedef mentioning `block_type`, and there is no member function
> mentioning `block_type`, too.  `basic_bitvector` accepts only one
> template argument, which is the `allocator_type`, and allocates
> whatever the allocator's `value_type` is -- only unsigned integers
> can well-formly instantiate the template of course.
>=20
> The rationale is to pretend we have a class storing "bits", not
> `bool`s, not "blocks" either.  Just, since we can not represent
> a real "bit", there is no `value_type` defined, like
> `boost::dynamic_bitset`.  Furthermore, we want all of the
> `basic_vector<allocator<Block>>`s behave in exactly the same
> way like the `vector<bit, allocator<bit>>`, two `basic_bitvector`s
> with convertible allocator types but different storage types
> are implicitly convertible to each other.
>=20
> Almost all other interfaces follow `std::bitset`, like what
> `boost::dynamic_bitset` did.  Some interfaces follow
> `vector<bool>`, considering `bitvector`'s variable-length
> property.
>=20
> Comments are welcome.

In general, I like this direction.  A few comments:

*  I don't see any value in allowing the client to specify block size via t=
he allocator::value_type.  There is only one optimal block size for any giv=
en platform, and the implementor knows what that is.  Generally it is unsig=
ned and sizeof(void*).  But whatever it is, the client is bound to de-optim=
ize, possibly even accidentally, by passing in the wrong allocator_type.  I=
 recommend requiring allocator::value_type be bool.

*  I appreciate the general merging of the API of bitset and vector<bool>. =
 Especially important is the API of vector<bool> as you need to ease the mi=
gration effort of vector<bool> clients as much as possible.

Missing are:

insert
erase
front
back

et al.

*  One deviation from vector<bool> I would like to see is a proxy class nam=
ed by bitvector::const_reference which acts like a const bool&.  I.e. it sh=
ould return a non-mutable reference to a bit.

    bitvector v =3D {true, false};
    bitvector::const_reference cr =3D v[1];
    assert(cr =3D=3D false);
    v[1] =3D true;
    assert(cr =3D=3D true);

This would make bitvector behave more like a non-specialized vector<bool>, =
making it more likely to work correctly in generic code.

*  bitvector::value_type must be bool, for both migration and generic purpo=
ses.

*  I would like to see:

   std::swap(bitvector::reference, bitvector::reference);
   std::swap(bitvector::reference, bool&);
   std::swap(bool&, bitvector::reference);


*  I would like to see several of the algorithms in <algorithm> specified t=
o be specialized on bitvector::[const_]iterator, including, but not limited=
 to:

all_of
any_of
none_of
find
count
fill_n
fill
copy
copy_backward
move
move_backward
swap_ranges
rotate
equal

These specializations should have the same API as today when vector<bool>::=
[const_]iterator is used with these algorithms.

This article shows the dramatic potential improvements such algorithmic spe=
cializations can have:

http://home.roadrunner.com/~hinnant/onvectorbool.html

If deprecating vector<bool> is the stick behind getting clients to migrate,=
 these algorithm specializations are the carrot.  Migrate and your existing=
 use of std::count(v.begin(), v.end(), true) may automagically get 75X fast=
er!

Howard

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

On Sun, Aug 25, 2013 at 2:08 PM, Howard Hinnant
<howard.hinnant@gmail.com> wrote:
> *  I don't see any value in allowing the client to specify block size via=
 the allocator::value_type.  There is only one optimal block size for any g=
iven platform, and the implementor knows what that is.  Generally it is uns=
igned and sizeof(void*).  But whatever it is, the client is bound to de-opt=
imize, possibly even accidentally, by passing in the wrong allocator_type. =
 I recommend requiring allocator::value_type be bool.

std::vector<bool>'s idea of rebinding the input allocator to use is
really bad; it makes a stateful allocator impossible to track what it
allocated.  We can discuss whether we should enforce
`allocator::value_type` to be `unsigned long` anyway, while my
concern is that some special purpose allocator may not be able
to allocate an `unsigned long`.  For example, if I write an allocator
to use Berkeley DB as it's backend, then it can only allocate
`unsigned char`.

> *  I appreciate the general merging of the API of bitset and vector<bool>=
..  Especially important is the API of vector<bool> as you need to ease the =
migration effort of vector<bool> clients as much as possible.

Unfortunately, correct me if I'm wrong, with the current iterator
categories, there is no way to use proxy iterator, thus, no interface
mentioning iterator can involve.  For example, insert and erase.
`boost::dynamic_bitset` does not have them, either.

See also: http://www.gotw.ca/publications/N1185.pdf

> front
> back

These are OK, but `std::bitset` don't have them.  I wish the authors
of `boost::dynamic_bitset` can tell me why these interfaces are
excluded.

> This would make bitvector behave more like a non-specialized vector<bool>=
, making it more likely to work correctly in generic code.

Like I said, you can only increase the similarity, but it's impossible
to create a bitvector which can be used as a drop-in replacement
as `vector<bool>`, unless you create another shame.  The purpose
of my version of `bitvector` is to give users a good-enough
variable-length bitset to use, and wait the old code to expire, then
drop `vector<bool>`.

> This article shows the dramatic potential improvements such algorithmic s=
pecializations can have:
>
> http://home.roadrunner.com/~hinnant/onvectorbool.html

I read your article, obviously :)  But, the problem is not about naming,
the problem is about the iterator requirements.  For short, if you
specialized those STL algorithms for proxy iterators, they can no
longer be considered as STL algorithms.

My `hidden` suggestion is to add some useful algorithms as member
functions to both `std::bitset` and `bitvector` later.

Thanks for your kind suggestions!

--=20
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

On Aug 25, 2013, at 3:05 PM, Zhihao Yuan <zy@miator.net> wrote:

> On Sun, Aug 25, 2013 at 2:08 PM, Howard Hinnant
> <howard.hinnant@gmail.com> wrote:
>> *  I don't see any value in allowing the client to specify block size vi=
a the allocator::value_type.  There is only one optimal block size for any =
given platform, and the implementor knows what that is.  Generally it is un=
signed and sizeof(void*).  But whatever it is, the client is bound to de-op=
timize, possibly even accidentally, by passing in the wrong allocator_type.=
  I recommend requiring allocator::value_type be bool.
>=20
> std::vector<bool>'s idea of rebinding the input allocator to use is
> really bad; it makes a stateful allocator impossible to track what it
> allocated.  We can discuss whether we should enforce
> `allocator::value_type` to be `unsigned long` anyway, while my
> concern is that some special purpose allocator may not be able
> to allocate an `unsigned long`.  For example, if I write an allocator
> to use Berkeley DB as it's backend, then it can only allocate
> `unsigned char`.

Presumably such an allocator also could not be used here?

    vector<unsigned long, Alloc<unsigned long>>

>=20
>> *  I appreciate the general merging of the API of bitset and vector<bool=
>.  Especially important is the API of vector<bool> as you need to ease the=
 migration effort of vector<bool> clients as much as possible.
>=20
> Unfortunately, correct me if I'm wrong, with the current iterator
> categories, there is no way to use proxy iterator, thus, no interface
> mentioning iterator can involve.  For example, insert and erase.
> `boost::dynamic_bitset` does not have them, either.
>=20
> See also: http://www.gotw.ca/publications/N1185.pdf

The current vector<bool> has insert/erase and things generally work pretty =
well, despite the broken iterator requirements. We should fix the iterator =
requirements, not break clients of vector<bool> by taking away the only bit=
 container that supports insert/erase.

Sorry, this is a non-starter for me.  I will strongly object to deprecating=
 vector<bool> if there is no way to migrate clients who are doing:

   std::vector<bool> v;
   v.insert(v.begin(), true);

(aside from telling them that they now have to store bools instead of bits)=
..

And I will also strongly object to introducing a dynamically sized vector o=
f bits which does not allow such basic use as it will make it much more dif=
ficult for a future vector<bool> replacement to be introduced so that we co=
uld deprecate vector<bool>.

>=20
>> front
>> back
>=20
> These are OK, but `std::bitset` don't have them.  I wish the authors
> of `boost::dynamic_bitset` can tell me why these interfaces are
> excluded.

The authors of vector<bool> included them.  Therefore we need them.

To stress how strongly I feel about vector<bool> API compatibility:

   I think the flip() interface of vector<bool> is brain-dead.
   But since it is there in vector<bool>, I feel we need it in bitvector
   anyway.  The flip() interface isn't dangerous.  It is just non-generic.

>> This would make bitvector behave more like a non-specialized vector<bool=
>, making it more likely to work correctly in generic code.
>=20
> Like I said, you can only increase the similarity, but it's impossible
> to create a bitvector which can be used as a drop-in replacement
> as `vector<bool>`, unless you create another shame.  The purpose
> of my version of `bitvector` is to give users a good-enough
> variable-length bitset to use, and wait the old code to expire, then
> drop `vector<bool>`.

The shame of vector<bool> is not that it has iterators.  The shame of vecto=
r<bool> is its name.  It does not behave exactly like a non-specialized vec=
tor<bool>, nor can it be made to.  And a non-specialized vector<bool> would=
 also be a useful data structure with obvious and well-defined behavior.  H=
owever the vector<bool> specialization works well enough that it has surviv=
ed standardization for 15 years.  vector<bool> is a good container with a b=
ad name.  We just need to change its name.

>=20
>> This article shows the dramatic potential improvements such algorithmic =
specializations can have:
>>=20
>> http://home.roadrunner.com/~hinnant/onvectorbool.html
>=20
> I read your article, obviously :)  But, the problem is not about naming,
> the problem is about the iterator requirements.  For short, if you
> specialized those STL algorithms for proxy iterators, they can no
> longer be considered as STL algorithms.
>=20
> My `hidden` suggestion is to add some useful algorithms as member
> functions to both `std::bitset` and `bitvector` later.

That destroys the fundamental design of the STL.  You go from N algorithms =
for M containers to N*M algorithms for M containers.  Generic code is no lo=
nger useful for vectors of bits.

There is nothing fundamentally incorrect about:

    vector<bool> v =3D ...;
    auto i =3D std::count(v.begin(), v.end(), true);

It even compiles and works with every implementation today.  Switching from=
 the typical implementation today, to a non-specialized vector<bool> implem=
entation will continue to work, and give you a 2% performance increase (har=
dly worth the bother).  Switching to a bitvector which has optimized

    auto i =3D std::count(v.begin(), v.end(), true);

gives you a 20X speed up over both the typical implementation today, and th=
e performance of the non-specialized vector<bool>.  That is worth fighting =
for!  And the syntax remains generic so that code such as:

template <class C>
auto
foo(const C& c)
{
     ...
     auto count =3D std::count(std::next(c.begin()), c.end(), *c.begin());
     ...

}

Will work, with the highest possible performance, and the highest possible =
compatibility with the maximum number of containers C.

Howard

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

On Sun, Aug 25, 2013 at 3:39 PM, Howard Hinnant
<howard.hinnant@gmail.com> wrote:
> Presumably such an allocator also could not be used here?
>
>     vector<unsigned long, Alloc<unsigned long>>

It does not have to be, right?  It's just simple and correct to
let allocators to allocate the thing they want.

> Sorry, this is a non-starter for me.  I will strongly object to deprecating vector<bool> if there is no way to migrate clients who are doing:
>
>    std::vector<bool> v;
>    v.insert(v.begin(), true);

Truly speaking, I don't think a variable-length bitset should
support the iterator interfaces.  Imaging a bitset as a large
integer, just we only care about its bit-wise operations instead
of the mathematical operations.  Inserting a bit in the middle
is pretty much useless.

> vector<bool> is a good container with a bad name.  We just need to change its name.

Unfortunately, `vector<bool>` is not a container.

>> My `hidden` suggestion is to add some useful algorithms as member
>> functions to both `std::bitset` and `bitvector` later.
>
> That destroys the fundamental design of the STL.  You go from N algorithms for M containers to N*M algorithms for M containers.  Generic code is no longer useful for vectors of bits.

Actually, the most useful bitset operations are already addressed
by `std::bitset`: `any`, `all`, (pop)`count`.  `boost::dynamic_bitset` has
`find_first_of`, but I'm not sure whether `std::bitset` should has it as
well.  Other things, like `fill`, `copy`, `rotate` are meaningless to a
bitset; those operations are only meaningful when you want a
container of bools, while the procedure of deprecating `vector<bool>`
can give a *real* STL container of bool back to the users.

To sum them up: currently, neither `bitvector` nor `vector<bool>` is a
container.  Only deprecating the later one can give you a container.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

On Sun, Aug 25, 2013 at 3:39 PM, Howard Hinnant
<howard.hinnant@gmail.com> wrote:
> To stress how strongly I feel about vector<bool> API compatibility:
>
>    I think the flip() interface of vector<bool> is brain-dead.
>    But since it is there in vector<bool>, I feel we need it in bitvector
>    anyway.  The flip() interface isn't dangerous.  It is just non-generic.

I strongly agree, but for a different reason.  My point is that the
maximum generic can only be gained when a `vector<bool>` is
nothing but a `vector` storing variables of type bool.  Optimizing
the size already made the class become a non-container, and
if you optimize the STL algorithms, then those algorithms become
non-STL algorithms.  New iterator architecture?  If we have them
in the future, please add them to `bitvector`, not `vector<bool>`.
We must stop the disaster by removing this specialization instead
of adding more glitches.

Then what `bitvector` does here?  It fulfilled the bitset half of
`vector<bool>`.  My hope is to let the users of `vector<bool>`
to be split into two groups: one use `vector<bool>` as a
container of bool, which is wrong -- many C++ books suggest
them to use `deque<bool>` instead; one use `vector<bool>`
as a variable-length bitset -- the potential or existing users of
`boost::dynamic_bitset`.  Then, let the later group switch to
`bitvector`, and let the first group silently wait `vector<bool>`
to be de-specialized.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

FWIW, Howard's nearly always right, especially on this topic. If he
says something about how this container should be designed, that's the
direction I, and probably several other people, are going to vote.

I could correct a couple specific things you've said here, but it'll
probably save time if you double-check all your conclusions under the
assumption that Howard's right, and come back with the things you're
still confused about.

Jeffrey

On Sun, Aug 25, 2013 at 1:20 PM, Zhihao Yuan <zy@miator.net> wrote:
> On Sun, Aug 25, 2013 at 3:39 PM, Howard Hinnant
> <howard.hinnant@gmail.com> wrote:
>> Presumably such an allocator also could not be used here?
>>
>>     vector<unsigned long, Alloc<unsigned long>>
>
> It does not have to be, right?  It's just simple and correct to
> let allocators to allocate the thing they want.
>
>> Sorry, this is a non-starter for me.  I will strongly object to deprecating vector<bool> if there is no way to migrate clients who are doing:
>>
>>    std::vector<bool> v;
>>    v.insert(v.begin(), true);
>
> Truly speaking, I don't think a variable-length bitset should
> support the iterator interfaces.  Imaging a bitset as a large
> integer, just we only care about its bit-wise operations instead
> of the mathematical operations.  Inserting a bit in the middle
> is pretty much useless.
>
>> vector<bool> is a good container with a bad name.  We just need to change its name.
>
> Unfortunately, `vector<bool>` is not a container.
>
>>> My `hidden` suggestion is to add some useful algorithms as member
>>> functions to both `std::bitset` and `bitvector` later.
>>
>> That destroys the fundamental design of the STL.  You go from N algorithms for M containers to N*M algorithms for M containers.  Generic code is no longer useful for vectors of bits.
>
> Actually, the most useful bitset operations are already addressed
> by `std::bitset`: `any`, `all`, (pop)`count`.  `boost::dynamic_bitset` has
> `find_first_of`, but I'm not sure whether `std::bitset` should has it as
> well.  Other things, like `fill`, `copy`, `rotate` are meaningless to a
> bitset; those operations are only meaningful when you want a
> container of bools, while the procedure of deprecating `vector<bool>`
> can give a *real* STL container of bool back to the users.
>
> To sum them up: currently, neither `bitvector` nor `vector<bool>` is a
> container.  Only deprecating the later one can give you a container.
>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

On Sun, Aug 25, 2013 at 7:01 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
> I could correct a couple specific things you've said here, but it'll
> probably save time if you double-check all your conclusions under the
> assumption that Howard's right, and come back with the things you're
> still confused about.

Then I have to give up.  Because in my and`boost::dynamic_bitset`'s
designs, a variable-length bitset just don't interfere with iterators --
like integers, like `bitset`.  Assume those interfaces are useful, the
only thing I can think of is to let them to be addressed by the
de-specialized `vector<bool>`.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

------=_Part_932_30310268.1377528680946
Content-Type: text/plain; charset=ISO-8859-1



On Sunday, August 25, 2013 8:08:22 PM UTC+2, Howard Hinnant wrote:
>
>
>
> *  I would like to see several of the algorithms in <algorithm> specified
> to be specialized on bitvector::[const_]iterator, including, but not
> limited to:
>
> all_of
> any_of
> none_of
> find
> count
> fill_n
> fill
> copy
> copy_backward
> move
> move_backward
> swap_ranges
> rotate
> equal
>

Also mismatch, search, search_n, find_end, and possibly generate and
reverse.


>
> These specializations should have the same API as today when
> vector<bool>::[const_]iterator is used with these algorithms.
>
> This article shows the dramatic potential improvements such algorithmic
> specializations can have:
>
> http://home.roadrunner.com/~hinnant/onvectorbool.html
>
> If deprecating vector<bool> is the stick behind getting clients to
> migrate, these algorithm specializations are the carrot.  Migrate and your
> existing use of std::count(v.begin(), v.end(), true) may automagically get
> 75X faster!
>
>
I still think we should not just specialize the standard algorithms, but
also provide an interface for other people to specialize their algorithms.
Something along the lines of segmented iterators[1] would be an option,
where the segment_iterator can be dereferenced to the underlying integer
type. Another would be something like SIMD iterators[2, best thing I could
find], which makes a lot of sense because operating on an unsigned integer
for bit manipulation *is* SIMD.

[1] http://lafstern.org/matt/segmented.pdf
[2] http://lists.boost.org/Archives/boost/2010/10/171755.php

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_932_30310268.1377528680946
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Sunday, August 25, 2013 8:08:22 PM UTC+2, Howar=
d Hinnant wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br><br>* &nbsp;I would like to see several of the algorithms in &lt;algori=
thm&gt; specified to be specialized on bitvector::[const_]iterator, includi=
ng, but not limited to:
<br>
<br>all_of
<br>any_of
<br>none_of
<br>find
<br>count
<br>fill_n
<br>fill
<br>copy
<br>copy_backward
<br>move
<br>move_backward
<br>swap_ranges
<br>rotate
<br>equal
<br></blockquote><div><br></div><div>Also mismatch, search, search_n, find_=
end, and possibly generate and reverse.</div><div>&nbsp;</div><blockquote c=
lass=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px=
 #ccc solid;padding-left: 1ex;">
<br>These specializations should have the same API as today when vector&lt;=
bool&gt;::[const_]iterator is used with these algorithms.
<br>
<br>This article shows the dramatic potential improvements such algorithmic=
 specializations can have:
<br>
<br><a href=3D"http://home.roadrunner.com/~hinnant/onvectorbool.html" targe=
t=3D"_blank">http://home.roadrunner.com/~<wbr>hinnant/onvectorbool.html</a>
<br>
<br>If deprecating vector&lt;bool&gt; is the stick behind getting clients t=
o migrate, these algorithm specializations are the carrot. &nbsp;Migrate an=
d your existing use of std::count(v.begin(), v.end(), true) may automagical=
ly get 75X faster!
<br><br></blockquote><div><br></div><div>I still think we should not just s=
pecialize the standard algorithms, but also provide an interface for other =
people to specialize their algorithms. Something along the lines of segment=
ed iterators[1] would be an option, where the segment_iterator can be deref=
erenced to the underlying integer type. Another would be something like SIM=
D iterators[2, best thing I could find], which makes a lot of sense because=
 operating on an unsigned integer for bit manipulation *is* SIMD.</div><div=
><br></div><div>[1]&nbsp;<a href=3D"http://lafstern.org/matt/segmented.pdf"=
>http://lafstern.org/matt/segmented.pdf</a></div><div>[2]&nbsp;<a href=3D"h=
ttp://lists.boost.org/Archives/boost/2010/10/171755.php">http://lists.boost=
..org/Archives/boost/2010/10/171755.php</a></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_932_30310268.1377528680946--

.