[std-proposals] Remove vector<bool>?

[Zhihao Yuan]

I saw Herb's paper:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it. How about to entirely
remove it?

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

[Nevin Liber]

On 28 May 2013 10:50, Zhihao Yuan <lic...@gmail.com> wrote:

I saw Herb's paper:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it.  How about to entirely
remove it?

That could be a silent breaking change to potentially a lot of users; I would be against that.  Export notwithstanding, we don't just pull things out of the standard.

If someone were to propose making it deprecated in C++17, I could be for that.

Because this is a breaking change, I would like to see such a proposal talk about the practical use cases for having a vector<bool> that was just another instance of vector.  What are the useful things that cannot be done / cannot be done efficiently now with vector<bool>.

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Tony V E]

--
 

Yes, the real trick is that we don't really want to remove vector<bool>, we just want to remove its specialization.  A vector<bool> that was a, well, vector of bools, would be great, but how do we get from here to there?

Tony
 

[DeadMG]

I don't believe it could break users- as far as I'm aware, the vector<bool> specialization offers strictly less functionality than a real vector<bool>.

[Marshall Clow]

On May 28, 2013, at 9:33 AM, DeadMG <wolfei...@gmail.com> wrote:

> I don't believe it could break users- as far as I'm aware, the vector<bool> specialization offers strictly less functionality than a real vector<bool>.

Except, of course, for being 1/32nd of the size. ;-)
(which could be observable, for example, if you had a 1 million long vector<bool>)

-- Marshall

Marshall Clow Idio Software <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki

[Nevin Liber]

On 28 May 2013 11:33, DeadMG <wolfei...@gmail.com> wrote:

I don't believe it could break users- as far as I'm aware, the vector<bool> specialization offers strictly less functionality than a real vector<bool>.

It *obviously* breaks users, given 23.3.1 "To optimize space allocation, a specialization of vector for bool elements is provided" (not to mention the need to support "flip()", but at least that breaking change isn't silent).

[Howard Hinnant]

On May 28, 2013, at 12:17 PM, Nevin Liber <ne...@eviloverlord.com> wrote:

> On 28 May 2013 10:50, Zhihao Yuan <lic...@gmail.com> wrote:
>> I saw Herb's paper:
>>
>> http://www.gotw.ca/publications/N1185.pdf
>>
>> But it's not adopted.
>>
>> Anyway, vector<bool> sucks, and we know it. How about to entirely
>> remove it?
>>
> That could be a silent breaking change to potentially a lot of users; I would be against that. Export notwithstanding, we don't just pull things out of the standard.

+1

>
> If someone were to propose making it deprecated in C++17, I could be for that.
>
> Because this is a breaking change, I would like to see such a proposal talk about the practical use cases for having a vector<bool> that was just another instance of vector. What are the useful things that cannot be done / cannot be done efficiently now with vector<bool>.

The premise is wrong: vector<bool> doesn't suck. The functionality vector<bool> provides is good, and could be much improved. The data structure: dynamic array of bits is a classic and valuable data structure in computer science:

http://en.wikipedia.org/wiki/Bit_array

What sucks is that we named this useful data structure vector<bool>.

I will oppose deprecating vector<bool> until we put in place something for clients of vector<bool> to migrate to. That something should have much the same API as vector<bool> to ease said migration. I.e. clients of vector<bool> should have to do little more than change the name of the container.

Additionally we could add sweetener to encourage the migration. For example we could mandate that bit_vector<Allocator> (or whatever the new name is) is hyper efficient when used with std::algorithms such as:

template <class InputIterator, class T>
InputIterator
find(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);

template <class ForwardIterator, class T>
void
fill(ForwardIterator first, ForwardIterator last, const T& value);

template <class InputIterator, class OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result);

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

template <class ForwardIterator>
ForwardIterator
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

template <class InputIterator1, class InputIterator2>
bool
equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

etc.

The potential for *portable* dramatic gains in performance are here. Let's not squander this opportunity. For actual performance numbers that can be realized, see:

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

Howard

[Ville Voutilainen]

On 28 May 2013 19:43, Howard Hinnant <howard....@gmail.com> wrote:

I will oppose deprecating vector<bool> until we put in place something for clients of vector<bool> to migrate to.  That something should have much the same API as vector<bool> to ease said migration.  I.e. clients of vector<bool> should have to do little more than change the name of the container.

Additionally we could add sweetener to encourage the migration.  For example we could mandate that bit_vector<Allocator> (or whatever the new name is) is hyper efficient when used with std::algorithms such as:

Snip. +10. Howard, as usual, has words of wisdom to offer as guidance to us puny mortals. :)

[Zhihao Yuan]

On Tue, May 28, 2013 at 12:43 PM, Howard Hinnant
<howard....@gmail.com> wrote:
> The premise is wrong: vector<bool> doesn't suck. The functionality vector<bool> provides is good, and could be much improved. The data structure: dynamic array of bits is a classic and valuable data structure in computer science:
>
> http://en.wikipedia.org/wiki/Bit_array
>
> What sucks is that we named this useful data structure vector<bool>.

Exactly.

> The potential for *portable* dramatic gains in performance are here. Let's not squander this opportunity. For actual performance numbers that can be realized, see:
>
> http://home.roadrunner.com/~hinnant/onvectorbool.html

I like this. If it's not a STL container, then it's neither named as container
nor looks like a container. Can you propose it?

However, to remove vector<bool> can happen at the same time, IMO.

[Zhihao Yuan]

On Tue, May 28, 2013 at 12:40 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> It *obviously* breaks users, given 23.3.1 "To optimize space allocation, a
> specialization of vector for bool elements is provided" (not to mention the
> need to support "flip()", but at least that breaking change isn't silent).

I see. But:

1. Optimization is not mandatory, let's forget about it;
2. It's OK to backport some special interfaces, like `flip()`, which can be
SFINAEd if T is not bool.

[DeadMG]

There is boost::dynamic_bitset, and we could pull the usual "Just take it from Boost" routine. In addition, a partial spec for vector<bool, alloc> that just adds flip() would be absolutely fine.

[Zhihao Yuan]

On Tue, May 28, 2013 at 1:32 PM, DeadMG <wolfei...@gmail.com> wrote:
> In addition, a partial spec for vector<bool, alloc>
> that just adds flip() would be absolutely fine.

template <typename = typename enable_if<is_same<T, bool>::value>::type>
void flip noexcept;

Same to `clear()`. Of course, a wording wants description, not
implementation.

[Nicol Bolas]

On Tuesday, May 28, 2013 9:33:07 AM UTC-7, DeadMG wrote:

I don't believe it could break users- as far as I'm aware, the vector<bool> specialization offers strictly less functionality than a real vector<bool>.

Ignoring the space optimization issue (and `flip`), there is one place where vector<bool> has substantive differences from vector<T>: `vector<bool>::reference` and `vector<bool>::const_reference`.

For any other type `T`, `vector<T>::const_reference` is required to be a `const T&`. However, the standard requires `vector<bool>::const_reference` to be a `bool`, not a `const bool &`.

Of greater concern is the fact that `vector<bool>::reference` is required to be a specific inner class of `vector<bool>`, with specific behavior like a `flip` member function. If someone relies on being able to do this:

std::vector<bool> bvec{ ... };
bvec[2].flip();

That could be a problem. Especially since this is not an unreasonable use of the `vector<bool>` interface as it currently stands.

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

[Howard Hinnant]

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

> Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1: Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization. /Somehow/ motivate people to migrate.

Step 2: Not to be done for at least 5-10 years after Step 1, remove the vector<bool> specialization.

> how much code will be broken because of this?

After Step 1, none.

After Step 2, as much code as there is that:

A. Failed to migrate during the lengthy period that vector<bool> is deprecated, and
B. As much code that actually cares that vector<bool> was specialized.

Hopefully, little code will be broken. While I wouldn't dream of removing auto_ptr today, I have the impression that the auto_ptr -> unique_ptr migration is going well, thanks to the added sweetener unique_ptr has. Removing auto_ptr for C++17 is a possibility. If not then, then maybe C++2x.

Howard

[Nevin Liber]

On 28 May 2013 15:00, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

There is never any real way to know, but it's been around a long time

The problems with just pulling it are:

1.  Silent changes really annoy users.
2.  It makes migration harder, as you are required to change your code in a backwards-incompatible way just to get it working under C++17.

For C++17 I think we can deprecate the vector<bool> specialization at the same time (in favor of no specialization for the subsequent release), but I don't see just removing it as something that has any chance of passing the committee.

[Daniel Krügler]

2013/5/28 Howard Hinnant <howard....@gmail.com>:

I completely agree with that approach. Removing std::auto_ptr seems
realistic now (from the pov of the standard). Existing library
implementations will decide individually how long they will conserve
the definition, depending on their customers.

- Daniel

[Nevin Liber]

On 28 May 2013 15:16, Daniel Krügler <daniel....@gmail.com> wrote:

I completely agree with that approach. Removing std::auto_ptr seems
realistic now (from the pov of the standard). Existing library
implementations will decide individually how long they will conserve
the definition, depending on their customers.

Note:  vector<bool> is different in one regard, as (I assume) we are proposing a change in behavior and not just removal of a deprecated library.

[Zhihao Yuan]

On Tue, May 28, 2013 at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> std::vector<bool> bvec{ ... };
> bvec[2].flip();

I noticed that. It's OK to be fixed within `vector<T>`.

> Personally, I agree with Howard; we should add a class that has all of this
> functionality (presumably with some degree of required sizing) that would be
> a drop-in replacement for those who need the sizing features of
> vector<bool>. But the question remains: even with a drop-in replacement, how
> much code will be broken because of this?

I like the idea of providing a replacement, but I don't think a 'drop-in
replacement' is a requirement. `vector<bool>` still works, and users
can rewrite their code if they want.

[Tony V E]

I think (and maybe this was implied) we should also NOT add flip() to the otherwise-non-specialized future vector<bool>.  ie we give users bit_vector with flip(), and do NOT try to help keep their current uses of vector<bool> compiling.  It would be better for their code to stop compiling until they switch to bit_vector.

Tony

[Nicol Bolas]

This isn't like the auto_ptr->unique_ptr thing; there, the idea there was to get people using a new class with a new interface and new behavior (as an aside, I see no point in removing auto_ptr; it does no harm sitting there, since everyone already knows to use unique_ptr where available).

The point of this exercise is not to get a class that does exactly what `vector<bool>` does. The point of this exercise is to be able to actually create a real, legitimate `vector` that contains actual `bool`s. Getting users of `vector<bool>` to use a new class is merely the means to that end.

So a plan that could, maybe get us back `vector<bool>` around 2020 isn't particularly useful. I would much rather find a plan that gets us back `vector<bool>` in fewer than 3 standard revisions.

[Nicol Bolas]

On Tuesday, May 28, 2013 1:28:06 PM UTC-7, Zhihao Yuan wrote:

On Tue, May 28, 2013 at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> std::vector<bool> bvec{ ... };
> bvec[2].flip();

I noticed that.  It's OK to be fixed within `vector<T>`.

> Personally, I agree with Howard; we should add a class that has all of this
> functionality (presumably with some degree of required sizing) that would be
> a drop-in replacement for those who need the sizing features of
> vector<bool>. But the question remains: even with a drop-in replacement, how
> much code will be broken because of this?

I like the idea of providing a replacement, but I don't think a 'drop-in
replacement' is a requirement.  `vector<bool>` still works, and users
can rewrite their code if they want.

When breaking people's code, it is generally advisable to minimize the disruption. And it'd be a lot easier to get through the committee if you can show them that the breaking changes will be noisy and that the changes can be easily repaired.

A drop-in replacement would cover the latter.

[Lawrence Crowl]

On Tuesday, May 28, 2013 1:28:06 PM UTC-7, Zhihao Yuan wrote:
> I like the idea of providing a replacement, but I don't think a
> 'drop-in replacement' is a requirement. `vector<bool>` still
> works, and users can rewrite their code if they want.

It is sometimes difficult to rewrite code. First, the code base
may be very large. Source code bases in excess of 20 million lines
are common. Expect much code bases to exist. Second, sometimes
that code is part of binary libraries. To get a change you need
to go back to the library vendor, request the change, hope they
have time to deal with your legacy platform, and you get the idea.
Third, the author of the code may be long gone. So, a rewrite would
require a programmer to understand the subtleties of that particular
use, which takes time. Now multiply by the code base size.

On 5/28/13, Nicol Bolas <jmck...@gmail.com> wrote:
> When breaking people's code, it is generally advisable to minimize
> the disruption. And it'd be a lot easier to get through the
> committee if you can show them that the breaking changes will be

> noisy *and* that the changes can be easily repaired.

>
> A drop-in replacement would cover the latter.

Agreed. A breaking change should have a migration plan.

For C++11, I argued that we could drop support for the old use of
the auto keyword because we had a simple migration plan.

= Remove all uses of the auto keyword in the code base.
= You now have a program that is both C++98 and C++11 conformant.
= Add the new use of auto when desired.

It certainly helped the argument that two thirds of the uses of auto
I found on code.google.com were in compiler conformance test suites.

--
Lawrence Crowl

[corn...@google.com]

On Tuesday, May 28, 2013 6:43:36 PM UTC+2, Howard Hinnant wrote:

I will oppose deprecating vector<bool> until we put in place something for clients of vector<bool> to migrate to.  That something should have much the same API as vector<bool> to ease said migration.  I.e. clients of vector<bool> should have to do little more than change the name of the container.

Additionally we could add sweetener to encourage the migration.  For example we could mandate that bit_vector<Allocator> (or whatever the new name is) is hyper efficient when used with std::algorithms such as:

And we should add an interface that allows 3rd-party or user-defined algorithms to exploit the packed representation of bit_vector. It's all nice for standard algorithms to be optimized for vector<bool>, but as a user of the library, I can't optimize my own algorithms without reaching into the implementation details, such as __bit_reference. So not only would I have to optimize my algorithm for packed bits, I'd have to do it for many different standard libraries.

Sebastian 

[Howard Hinnant]

I like this direction. And standardizing count-lead/trailing-zero-bits and population-count algorithms would help in this department too.

http://en.wikipedia.org/wiki/Count_leading_zeros#Hardware_support
http://en.wikipedia.org/wiki/Hamming_weight#Processor_support

C started out as a "portable assembly", but except for the recent atomic additions, hasn't kept up with additions to the popular set of machine instructions. Instead non-portable compiler intrinsics have risen to fill the gap. C++ should give us portable access to those compiler intrinsics.

Howard

[Gabriel Dos Reis]

Howard Hinnant <howard....@gmail.com> writes:

[...]

| C++ should give us portable access to those compiler intrinsics.

+1.
Brownie points if you make them constexpr (as appropriate).

-- Gaby

[Vicente J. Botet Escriba]

Le 28/05/13 22:12, Howard Hinnant a écrit :

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1:  Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization.  /Somehow/ motivate people to migrate.

I think that we will need also to add a std::new_vector<T> that behaves like std::vector<T> but doesn't have the bool specialization and deprecate std::vector :->
The name of the class and the namespace could have their importance. Maybe if we had a multi-vector that  was as efficient as a vector the name could be multi_vector<T>. Just an idea.

Step 2:  Not to be done for at least 5-10 years after Step 1, remove the vector<bool> specialization.

Remove the std::vector<T> from the standard.

how much code will be broken because of this?

After Step 1, none.

After Step 2, as much code as there is that:

   A.  Failed to migrate during the lengthy period that vector<bool> is deprecated, and
   B.  As much code that actually cares that vector<bool> was specialized.

Maybe a lot of, but, not silently.

Hopefully, little code will be broken.  While I wouldn't dream of removing auto_ptr today, I have the impression that the auto_ptr -> unique_ptr migration is going well, thanks to the added sweetener unique_ptr has.  Removing auto_ptr for C++17 is a possibility.  If not then, then maybe C++2x.

Howard

Yes, this could seem heretical, but this is the only path I see that could allow a smooth migration and a non silent drop of the unwanted std::vector<bool>.

Best,
Vicente

[Nevin Liber]

On 29 May 2013 12:20, Vicente J. Botet Escriba <vicent...@wanadoo.fr> wrote:

Le 28/05/13 22:12, Howard Hinnant a écrit :

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1:  Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization.  /Somehow/ motivate people to migrate.

I think that we will need also to add a std::new_vector<T> that behaves like std::vector<T> but doesn't have the bool specialization and deprecate std::vector :->

-100.

* Annoying 99% of all C++ users is a horrible, horrible idea.

* I'd hate to use a code base that had two different, unrelated types for doing the exact same thing, since ultimately these things end up interfaces.  Actually, I already have that, as people are trying to migrate from Boost over to std (such as shared_ptr), and it is anything but easy (because we are dependent on libraries developed for/by other groups, and changing those interfaces is a scheduling nightmare).

I like Howard's plan, as we not only don't leave current users of vector<bool> out in the cold but we give them incentive to move, as well as "fixing up" vector (although I'd still like to see some actual use cases for the non-specialized vector<bool>).

The part I disagree with is the timeframe; we only have to wait one standard cycle of having the current vector<bool> deprecated before removing the specialization.  The only promise we make to users about deprecated features is in n3690 Dp2: "These are deprecated features, where deprecated is defined as: Normative for the current edition of the Standard, but having been identified as a candidate for removal from future revisions."  Of course, getting the Committee to actually remove deprecated libraries is a whole different issue...

(And auto_ptr needs to go, even if library vendors decide to keep it around forever, because it appears in other interfaces in the Standard.)

[Nicol Bolas]

On Tuesday, May 28, 2013 8:50:23 AM UTC-7, Zhihao Yuan wrote:

I saw Herb's paper:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it.  How about to entirely
remove it?

I think I may have a solution to this problem. The goal is to have a `vector` class that contains actual `bool`s, right? Well, who says that it actually needs to be called "vector<bool>"?

We simply add another specialization to `vector` called "vector<std::real_bool, Allocator>". If you create a `vector` with the `std::real_bool` type, then you get exactly what you would have gotten if `vector<bool>` weren't a specialization: an actual `vector` that contains actual `bool`s. The `value_type` of `vector<std::real_bool>` would be `bool`, and so forth.

We don't have to get rid of `vector<bool>` to get what we want. We just have to call it something else. And since this `std::real_bool` type can't be used in existing code (defining new things in the `std` namespace is undefined behavior), it can't conflict with anything now.

The downside is that a template function that takes a `vector<T>`, where `T` is some type, may assume that `T` is the `value_type` of the `vector`, which it would not be in the case of `std::real_bool`.

[Nicol Bolas]

On Wednesday, May 29, 2013 10:20:15 AM UTC-7, Vicente J. Botet Escriba wrote:

Le 28/05/13 22:12, Howard Hinnant a écrit :

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1:  Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization.  /Somehow/ motivate people to migrate.

I think that we will need also to add a std::new_vector<T> that behaves like std::vector<T> but doesn't have the bool specialization and deprecate std::vector :->

So your solution to this significant-yet-relatively-minor-problem... is to rip out the entire class?

I'm going to go with "no" on that.

[Nevin Liber]

On 29 May 2013 12:42, Nicol Bolas <jmck...@gmail.com> wrote:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it.  How about to entirely
remove it?

We simply add another specialization to `vector` called "vector<std::real_bool, Allocator>". If you create a `vector` with the `std::real_bool` type, then you get exactly what you would have gotten if `vector<bool>` weren't a specialization: an actual `vector` that contains actual `bool`s. The `value_type` of `vector<std::real_bool>` would be `bool`, and so forth.

We don't have to get rid of `vector<bool>` to get what we want. We just have to call it something else. And since this `std::real_bool` type can't be used in existing code (defining new things in the `std` namespace is undefined behavior), it can't conflict with anything now.

The downside is that a template function that takes a `vector<T>`, where `T` is some type, may assume that `T` is the `value_type` of the `vector`, which it would not be in the case of `std::real_bool`.

-1.

The primary argument (so far) for removing the vector<bool> specialization is uniformity with the rest of vector.  As you point out, your solution still doesn't achieve it.

While the standard strives for high levels of backwards compatibility, it need not be 100% (heck, C++11 vector is not 100% backwards compatible with C++03 vector), and we shouldn't be adding more warts.  The standard is the right place to fix this, and we should fix it and not just put a band aid on it.

[Lawrence Crowl]

Some discussion has happened in SG6, but not enough.

--
Lawrence Crowl

[Nicol Bolas]

On Wednesday, May 29, 2013 10:51:42 AM UTC-7, Nevin ":-)" Liber wrote:

On 29 May 2013 12:42, Nicol Bolas <jmck...@gmail.com> wrote:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it.  How about to entirely
remove it?

We simply add another specialization to `vector` called "vector<std::real_bool, Allocator>". If you create a `vector` with the `std::real_bool` type, then you get exactly what you would have gotten if `vector<bool>` weren't a specialization: an actual `vector` that contains actual `bool`s. The `value_type` of `vector<std::real_bool>` would be `bool`, and so forth.

We don't have to get rid of `vector<bool>` to get what we want. We just have to call it something else. And since this `std::real_bool` type can't be used in existing code (defining new things in the `std` namespace is undefined behavior), it can't conflict with anything now.

The downside is that a template function that takes a `vector<T>`, where `T` is some type, may assume that `T` is the `value_type` of the `vector`, which it would not be in the case of `std::real_bool`.

-1.

The primary argument (so far) for removing the vector<bool> specialization is uniformity with the rest of vector.

I thought the primary argument was to be able to create a `vector` of `bool`s. I don't care about "uniformity"; what I care about is making a `vector` that actually contains `bool`s.

As you point out, your solution still doesn't achieve it.

While the standard strives for high levels of backwards compatibility, it need not be 100% (heck, C++11 vector is not 100% backwards compatible with C++03 vector), and we shouldn't be adding more warts.  The standard is the right place to fix this, and we should fix it and not just put a band aid on it.

And how long will that take? C++14 is closed for new stuff, and the whole "deprecation/removal" process will require at least 2 revisions. So it would be C++20 at least before we can finally create a real `vector` of real `bool`s.

[Zhihao Yuan]

On Wed, May 29, 2013 at 3:21 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> I thought the primary argument was to be able to create a `vector` of
> `bool`s. I don't care about "uniformity"; what I care about is making a
> `vector` that actually contains `bool`s.

I care about the interfaces, and how people think what the
interfaces mean.

> And how long will that take? C++14 is closed for new stuff, and the whole
> "deprecation/removal" process will require at least 2 revisions. So it would
> be C++20 at least before we can finally create a real `vector` of real
> `bool`s.

The "removal" touches no working interfaces -- very
important -- this is not a removal (from some degree).

I'm going to draft a simple proposal anyway, and see if it's OK
for a TS/C++17. Considering the implementation and adoption
period, the users (are there any?) should have enough time to
switch to a boost::dynamic_bitset, or even some replacement
we are going to provide in the standard.

[Nevin Liber]

On 29 May 2013 14:21, Nicol Bolas <jmck...@gmail.com> wrote:

I thought the primary argument was to be able to create a `vector` of `bool`s. I don't care about "uniformity"; what I care about is making a `vector` that actually contains `bool`s.

Then why bother spelling it "vector<bool>", if not to be used in a generic and uniform context?  It is unlikely the committee is willing to swap one specialization of vector<bool> for another.  I am well aware that there are other ways to hack in std::real_bool (such as by using a traits class), but it's still a hack.  If it is that important, propose a different class to do this not spelled "vector<bool>".

 

And how long will that take? C++14 is closed for new stuff, and the whole "deprecation/removal" process will require at least 2 revisions. So it would be C++20 at least before we can finally create a real `vector` of real `bool`s.

For better or worse, that is the process.

[Ville Voutilainen]

On 29 May 2013 22:36, Nevin Liber <ne...@eviloverlord.com> wrote:

On 29 May 2013 14:21, Nicol Bolas <jmck...@gmail.com> wrote:

I thought the primary argument was to be able to create a `vector` of `bool`s. I don't care about "uniformity"; what I care about is making a `vector` that actually contains `bool`s.

Then why bother spelling it "vector<bool>", if not to be used in a generic and uniform context?  It is unlikely the committee is willing to swap one specialization of vector<bool> for another.  I am well aware that there are other ways to hack in std::real_bool (such as by using a traits class), but it's still a hack.  If it is that important, propose a different class to do this not spelled "vector<bool>".

Well, I suppose it would be a different type of hack, but those who care about having a vector of bools

could just write a bool-wrapping struct and put that into a vector.

[Joel Falcou]

On 29/05/2013 21:39, Ville Voutilainen wrote:
> Well, I suppose it would be a different type of hack, but those who
> care about having a vector of bools could just write a bool-wrapping
> struct and put that into a vector.

Separation of concern. Container contains, values "value". I like this
approach
Then we can have a packed_bool stuff int he standard, but that's
basically having
the contrapose of the real_bool idea.

[Lawrence Crowl]

I don't think that works because v[i] has a different type and
selects different overload sets and instantiations.

--
Lawrence Crowl

[Nevin Liber]

On 29 May 2013 14:33, Zhihao Yuan <lic...@gmail.com> wrote:

> And how long will that take? C++14 is closed for new stuff, and the whole
> "deprecation/removal" process will require at least 2 revisions. So it would
> be C++20 at least before we can finally create a real `vector` of real
> `bool`s.

The "removal" touches no working interfaces -- very
important -- this is not a removal (from some degree).

I'm going to draft a simple proposal anyway, and see if it's OK
for a TS/C++17.

Until it is a proposal, it's your time to waste, but so far every committee member who has spoken in this thread is against just removing it from C++17 on the technicality that the space optimization is not required by the standard.  I'm pretty sure such a proposal will not take up much committee time.
 

 Considering the implementation and adoption
period, the users (are there any?) should have enough time to
switch to a boost::dynamic_bitset, or even some replacement
we are going to provide in the standard.

Removing useful functionality that users depend on without providing a suitable replacement is very unlikely to pass. (And much as I like Boost, pointing users to Boost is not an acceptable substitute.)

[Vicente J. Botet Escriba]

Le 29/05/13 19:44, Nicol Bolas a écrit :

Yes, the suggestion was not only heretical but unrealistic. vector<T> is one of the most used containers.

I'm going to go with "no" on that.

I understand. Not deprecating vector<T> at all could surely help.

Vicente

[Ville Voutilainen]

On 29 May 2013 23:03, Lawrence Crowl <cr...@googlers.com> wrote:

>
> Well, I suppose it would be a different type of hack, but those
> who care about having a vector of bools could just write a
> bool-wrapping struct and put that into a vector.

I don't think that works because v[i] has a different type and
selects different overload sets and instantiations.

Correct. That's a downside of every case of a wrapper type. Whether that is a concern

is left as an exercise for the designer. :)

[Ville Voutilainen]

On 29 May 2013 23:17, Nevin Liber <ne...@eviloverlord.com> wrote:

The "removal" touches no working interfaces -- very

important -- this is not a removal (from some degree).

I'm going to draft a simple proposal anyway, and see if it's OK
for a TS/C++17.

Until it is a proposal, it's your time to waste, but so far every committee member who has spoken in this thread is against just removing it from C++17 on the technicality that the space optimization is not required by the standard.  I'm pretty sure such a proposal will not take up much committee time.

I am fairly sure I'm opposed to just removing vector<bool>. Having a superior type to migrate to and deprecating vector<bool>

would be much preferred. I have no preference between that solution and leaving vector<bool> alone.
 

Removing useful functionality that users depend on without providing a suitable replacement is very unlikely to pass. (And much as I like Boost, pointing users to Boost is not an acceptable substitute.)

Agreed on both counts.

[Vicente J. Botet Escriba]

Le 29/05/13 19:37, Nevin Liber a écrit :

On 29 May 2013 12:20, Vicente J. Botet Escriba <vicent...@wanadoo.fr> wrote:

Le 28/05/13 22:12, Howard Hinnant a écrit :

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1:  Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization.  /Somehow/ motivate people to migrate.

I think that we will need also to add a std::new_vector<T> that behaves like std::vector<T> but doesn't have the bool specialization and deprecate std::vector :->

-100.

* Annoying 99% of all C++ users is a horrible, horrible idea.

Right. Forget the last sentence.

* I'd hate to use a code base that had two different, unrelated types for doing the exact same thing, since ultimately these things end up interfaces.  Actually, I already have that, as people are trying to migrate from Boost over to std (such as shared_ptr), and it is anything but easy (because we are dependent on libraries developed for/by other groups, and changing those interfaces is a scheduling nightmare).

You are right. What we would need is 'single' type that behaves as the current vector<T> except for bool and that behaves as vector<bool> if vector was not specialized. I don't know if we can specialize an alias and if the following is correct

template <typename T, typename Allocator>
class new_vector { the same definition as vector<T, Allocator> now };

template <typename T, typename Allocator>
alias vector= new_vector<T, Allocator> ;

template < typename Allocator>
class vector<bool, Allocator> { the same definition as now } ;

If this is correct, users of vector would get the same behavior. Users of new_vector would get the behavior without the bool specialization.
Any function expecting a vector<T> work with new_vector<T> except for bool. The same is valid for function expecting new_vector<T> you can use it with vector<T> except for bool.

Of course we need a bit_vector class that replace the vector<bool> specialization as Howard suggested.
After the deprecation period, new_vector and vector would have the same behavior and new_vector could be deprecated at his turn.


Vicente

[Zhihao Yuan]

On Wed, May 29, 2013 at 4:17 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> Until it is a proposal, it's your time to waste, but so far every committee
> member who has spoken in this thread is against just removing it from C++17
> on the technicality that the space optimization is not required by the
> standard. I'm pretty sure such a proposal will not take up much committee
> time.

What I don't understand it, what is the difference between removing
the optimization words and removing the specialization +
supporting vector<bool>'s extra interfaces in vector<T> when T == bool.
The interfaces of the standard are reminded the same, exactly
the same.

>> Considering the implementation and adoption
>> period, the users (are there any?) should have enough time to
>> switch to a boost::dynamic_bitset, or even some replacement
>> we are going to provide in the standard.
>
>
> Removing useful functionality that users depend on without providing a
> suitable replacement is very unlikely to pass. (And much as I like Boost,
> pointing users to Boost is not an acceptable substitute.)

Removing the performance words also makes vector<bool>
not functional, what's the differences?

[Nevin Liber]

On 29 May 2013 16:21, Zhihao Yuan <lic...@gmail.com> wrote:

What I don't understand it, what is the difference between removing
the optimization words and removing the specialization +
supporting vector<bool>'s extra interfaces in vector<T> when T == bool.

Because real users, and in all likelihood the majority of current users of vector<bool>, count on the space optimization even though it isn't normative, since that was most certainly the intent of the specialization.  We don't live in an ivory tower.

IMO, the correct "fix" is (1) address current users who need the space optimization that vector<bool> provides, and (2) vector (and generic code using vector) should neither know nor care that it is being instantiated with a bool.  If that isn't where we are heading, I see no reason to mess with either vector or vector<bool>.

[Zhihao Yuan]

On Wed, May 29, 2013 at 5:47 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> Because real users, and in all likelihood the majority of current users of
> vector<bool>, count on the space optimization even though it isn't
> normative, since that was most certainly the intent of the specialization.
> We don't live in an ivory tower.

When I say "optimization words" I mean the words those break the
container natural to allow the optimization. If you remove the those words,
the optimization is disabled. The real users can longer count on it.

> IMO, the correct "fix" is (1) address current users who need the space
> optimization that vector<bool> provides, and (2) vector (and generic code
> using vector) should neither know nor care that it is being instantiated
> with a bool. If that isn't where we are heading, I see no reason to mess
> with either vector or vector<bool>.

That's my initial thought. I don't like to bother vector<T>, either (
although it does not pollute the actual interfaces). But the problem
is, how to address the "current users"?

[Nevin Liber]

On 29 May 2013 17:07, Zhihao Yuan <lic...@gmail.com> wrote:

When I say "optimization words" I mean the words those break the
container natural to allow the optimization.  If you remove the those words,
the optimization is disabled.  The real users can longer count on it.

If this breaks users of C++14 vector<bool>, then it is a non-starter for C++17.
 

That's my initial thought.  I don't like to bother vector<T>, either (

although it does not pollute the actual interfaces).  But the problem
is, how to address the "current users"?

With a new class that has the optimizations Howard talked about, as well as a transition period of (at least) one standard cycle where the old behavior of vector<bool> is deprecated but doesn't change.

[Zhihao Yuan]

On Wed, May 29, 2013 at 6:15 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
>> When I say "optimization words" I mean the words those break the
>> container natural to allow the optimization. If you remove the those
>> words,
>> the optimization is disabled. The real users can longer count on it.
>
>
> If this breaks users of C++14 vector<bool>, then it is a non-starter for
> C++17.

If the non-mandatory optimization is required to be kept, then I'm
pretty sure we can make no useful changes to C++14 vector<bool>.

> With a new class that has the optimizations Howard talked about, as well as
> a transition period of (at least) one standard cycle where the old behavior
> of vector<bool> is deprecated but doesn't change.

TS: std::bit_vector
C++17: deprecation
C++2x: removal (completely)

You mean this? OMG...

[Zhihao Yuan]

On Wed, May 29, 2013 at 7:03 PM, Zhihao Yuan <lic...@gmail.com> wrote:
>> With a new class that has the optimizations Howard talked about, as well as
>> a transition period of (at least) one standard cycle where the old behavior
>> of vector<bool> is deprecated but doesn't change.
>
> TS: std::bit_vector
> C++17: deprecation
> C++2x: removal (completely)

After some thoughts, I tend to agree with this approach. The final result
looks more clean, and it gives the proposers more time to refine the
essential std::bit_vector proposal (the addition can happens at the same
time as the deprecation, in C++17), and bothers no people.

[Vicente J. Botet Escriba]

Le 29/05/13 23:19, Vicente J. Botet Escriba a écrit :

Le 29/05/13 19:37, Nevin Liber a écrit :

On 29 May 2013 12:20, Vicente J. Botet Escriba <vicent...@wanadoo.fr> wrote:

Le 28/05/13 22:12, Howard Hinnant a écrit :

On May 28, 2013, at 4:00 PM, Nicol Bolas <jmck...@gmail.com> wrote:

Personally, I agree with Howard; we should add a class that has all of this functionality (presumably with some degree of required sizing) that would be a drop-in replacement for those who need the sizing features of vector<bool>. But the question remains: even with a drop-in replacement, how much code will be broken because of this?

Model this after the auto_ptr -> unique_ptr transition:

Step 1:  Introduce bit_vector (or whatever) and deprecate the vector<bool> specialization.  /Somehow/ motivate people to migrate.

I think that we will need also to add a std::new_vector<T> that behaves like std::vector<T> but doesn't have the bool specialization and

* I'd hate to use a code base that had two different, unrelated types for doing the exact same thing, since ultimately these things end up interfaces.  Actually, I already have that, as people are trying to migrate from Boost over to std (such as shared_ptr), and it is anything but easy (because we are dependent on libraries developed for/by other groups, and changing those interfaces is a scheduling nightmare).

You are right. What we would need is 'single' type that behaves as the current vector<T> except for bool and that behaves as vector<bool> if vector was not specialized. I don't know if we can specialize an alias and if the following is correct

template <typename T, typename Allocator>
class new_vector { the same definition as vector<T, Allocator> now };

template <typename T, typename Allocator>
alias vector= new_vector<T, Allocator> ;

template < typename Allocator>
class vector<bool, Allocator> { the same definition as now } ;

If this is correct,

Hrr, It seems that we can not specialize alias templates.

Vicente

[Daniel Krügler]

2013/5/30 Vicente J. Botet Escriba <vicent...@wanadoo.fr>:

This is by design. If you need that feature, use a class template to
realize that and use an alias to refer to the class template.

- Daniel

[Bengt Gustafsson]

I remember in pre-standard days when I started out with C++ that the STL implementation we used had a special bit_vector container on the side from vector<bool> which was not in any way specialized. Now that the standard is there and has been set for long it is in my opinion far to late to revert the specialization, although introducing it was probably not so smart in the first place.

Going back to the original paper we are discussing here I noticed that the objectives for the suggested removal of the vector<bool> specialization was mostly due to formalistic reasons. The exception is the well known problems with tryinging to  create a pointer to a bit and some performance issues. Here are my comments:

- The pointer creation problem is not such an important issue as it is immediately flagged as an error by the compiler. For example VS2012 gives an "illegal indirection" error, as you can't take the address of the by value return of &. It would of course be good if the diagnostic was easier to understand but I don't see that it is significantly worse than other error messages. 

- The performance of the iterator, and its dereference operator etc. may be better or worse than for instance for a vector<char>, which would be the logical "benchmark". With today's computer hardware the CPU itself is usually much faster than memory accesses so the reduced number of cache misses (by a factor of 8 or more) would seem likely to outweigh the cost of more bitwise operations, at least for larger vectors.

- Thanks to the vector<bool> iterators being special classes it should be possible for the caring library implementer to specialize select algortihms such as find. As bool itself has a very limited set of values there is a reasonably small subset of the standard algorithms that make sense anyway. To make this possible a "wordwise" access possibility must be added to vector<bool>::iterator, as well as an accessor for the bit offset within the current word. This API can be defined by each library implementer (possibly using friend declarations to the algorithm specializations) or it could be standardized so that new user defined algorithms working on vector<bool> can use them in a well defined and portable way.

Thus, I would suggest to:

- Run a couple of benchmarks for regular usage to verify if the concerns about undue slowness of the iterator operations is a big problem, a small problem or not a problem.

- Define that vector<bool>::iterator has an API to access more than one bit at a time, a quick sketch would be:

    class iterator {

        ...

        typedef X word_type;

        static const int bits_per_word = sizeof(word_type) * 8;

        

        size_t bit_now() const;        // bit within the word that the iterator points at now*

        word_type& word_now();   // reference would be const for a const_iterator

    };

- Specialize some algorithms using the above API (this would be at the discretion of library implementors I guess, but a reference implementation would hint at attainable performance gain levels). Most important algorithms from <algorithm> would be:

find

count

search

search_n

copy

swap_ranges

reverse

rotate

Most other algorithms, for instance replace, is meaningless for bool values (the only thing you can do with replace is to make all values 0 or 1!).

By the way I can't remember having used vector<bool> despite now about 20 years of C++ so this issue is maybe not extremely important. If I were to use it, however, I would think that inserting/removing bits in the middle in a high performance way would be a very desirable feature in many applications. I say this because the use case when you don't is relatively easy to roll your own, but as soon as you start moving the bits around you want someone else to iron out the wrinkles for you, and that's exactly what we have a standard library for!

* A problem here is that many implementations (all?) use a bit mask to make iterator accesses faster. Converting this bit to a number is costly on most processors. Maybe the API would be better off if it returned the bit mask instead, as it is less costly to convert from bit number to bit mask (1<<bit_no).

Den tisdagen den 28:e maj 2013 kl. 17:50:23 UTC+2 skrev Zhihao Yuan:

I saw Herb's paper:

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

But it's not adopted.

Anyway, vector<bool> sucks, and we know it.  How about to entirely
remove it?

[Nevin Liber]

On 25 August 2013 16:28, Bengt Gustafsson <bengt.gu...@beamways.com> wrote:

- Define that vector<bool>::iterator has an API to access more than one bit at a time,

I do not believe the solution to the vector<bool> issue is to make it even more special and different.  -1.

If you really think this functionality is needed in the standard, (a) create a different class with that functionality, (b) get a lot of real world usage experience with that class and (c) then propose such a class for standardization.

Just my humble opinion,

-- 

[Bengt Gustafsson]

I was just trying to be pragmatic about solving the actual problems we are discussing, which should be problems that are of interest to real programmer's use of the language. I freely admit that the vector<bool> specialization is a wart but I don't see that this actually creates a lot of problems in the real world. Could anyone exemplify a reasonable usage that fails in a hard to detect way?

The real problems I could detect with vector<bool> were that the performance of algorithms like count() is significantly less than it could be. I suggested how this could be solved in a way that is totally invisible to the programmer. I also suggested that the API required could be standardized to allow user-defined algorithms to take advantage of the speedup.

From a practical programmer's standpoint I think it is very neat that vector<bool> hides the fact that there is a special implementation underneath. If another very similar but different class is introduced I can't see that this would make the language easier to understand or use.

If bit_vector is introduced all template code that uses vector<T> and would benefit from a packed structure would need to be specialized for bool. Is that really better?

In short I think that the formal drawbacks of vector<bool> such as "it not being a proper sequence" has very little practical consequence. The advantages of the packed storage is large in some applications, many of which have already been written assuming that storage use will be on par with a packed implementation.

I must also correct myself, I was too quick when testing the error message. There is no error message if you do &* on a vector<bool>::iterator. This is a real practical problem that can puzzle a programmer, although doing things that would fail like size_t length = &*vec.end() - &*vec.begin() seems rather odd... Most other uses of the pointer actually work as the reference class is intended to mimic what a bool does.

Overloading vector<bool>::reference::operator&() to do a static_assert(false) could be a solution. Of course there will be a few programs out there that correctly use this operator, but my guess is that such a overload would discover 10 times more bugs than it will break existing, meaningful code. A regular method could be added to do the work of the unoverloaded operator:

class reference {
    ....
    reference* operator&() { static_assert(false, "you can no longer take the address of a vector<bool>::reference, instead use make_pointer()"); }
    reference* make_pointer() { return this; }
};

An alternative solution would be to let operator& return an iterator again. This could be confusing as the main use of &* on an iterator is to convert it to a plain pointer, so personally I would prefer to outlaw operator&, if anything really must be changed.

--
 
---
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-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

-- 
Bengt Gustafsson
CEO, Beamways AB
Westmansgatan 37A
582 16 Linköping, Sweden
+46 13 465 10 85
www.beamways.com

[Nicol Bolas]

On Monday, August 26, 2013 12:46:26 AM UTC-7, Bengt Gustafsson wrote:

I was just trying to be pragmatic about solving the actual problems we are discussing, which should be problems that are of interest to real programmer's use of the language. I freely admit that the vector<bool> specialization is a wart but I don't see that this actually creates a lot of problems in the real world. Could anyone exemplify a reasonable usage that fails in a hard to detect way?

It's not that it fails in a "hard to detect" way. Generally speaking, when vector<bool> fails to act like a `vector` of `bool`s, it's pretty noisy about it. The problem is that, silent or not, if you really needed an honest-to-God `vector` that contains `bool`s, you can't get one.
 

The real problems I could detect with vector<bool> were that the performance of algorithms like count() is significantly less than it could be. I suggested how this could be solved in a way that is totally invisible to the programmer. I also suggested that the API required could be standardized to allow user-defined algorithms to take advantage of the speedup.

 

From a practical programmer's standpoint I think it is very neat that vector<bool> hides the fact that there is a special implementation underneath.

If it actually hid the fact, that might be true. But it doesn't. Consider the following:

void OperateOnBoolArray(const bool *array, size_t count);

vector<bool> stuff = {...};
OperateOnBoolArray(stuff.data(), stuff.size());

If the types here were anything besides `bool`, this would be perfectly legitimate code. But it's not..

Nothing is being hidden here; `vector<bool>` is not a `vector`. It doesn't provide the interface for a vector. And if you think this is too theoretical, consider some template code:

template<class T>
void Proc()
{
  vector<T> arr = {...};
  OperateOnArray(arr.data(), arr.size());
}

By all rights, this code ought to work with any type T. But it doesn't; if you stick `bool` in there, the compiler will fail, since `vector<bool>` doesn't have a `data` member. Because `vector<bool>` isn't a `vector` of `bool`s.
 

If another very similar but different class is introduced I can't see that this would make the language easier to understand or use.

 

If bit_vector is introduced all template code that uses vector<T> and would benefit from a packed structure would need to be specialized for bool. Is that really better?

No, it's not. The only way "bit_vector" is better is that it provides us a pathway whereby we can get rid of `vector<bool>`. That's the only reason we want it: so that people who currently use `vector<bool>` have a type that they can use. They can do a find-replace on "vector<bool>" with "bit_vector", and their code should immediately work as before. It needs to be a drop-in replacement so that they can stop using `vector<bool>`.

That way, C++17 can deprecate the `vector<bool>` specialization, and C++20 can remove it. Then, we will have what we should have had 20 years before: a real `vector` that can contain real `bool`s, and a type that is a space-optimized pseudo-container that has `bool`-like stuff in it. We can even add new interfaces to that container, the way boost::dynamic_bitset has some useful functions on it.

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 9:22 AM, Nicol Bolas <jmck...@gmail.com> wrote:
> They can do a find-replace on "vector<bool>" with
> "bit_vector", and their code should immediately work as before. It needs to
> be a drop-in replacement so that they can stop using `vector<bool>`.

What I don't understand is why all of you think a drop-in replacement
of `vector<bool>` is possible. `vector<bool>` is already proven to
be wrong. Its iterator does not even meet the ForwardIterator
requirement. Change the whole iterator categories just to unblock
proxy iterator? Dave already tried -- not accepted. `vector<bool>`
is just a mistake, a drop-in replacement of an mistake is also wrong.

[Daniel Krügler]

2013/8/26 Zhihao Yuan <z...@miator.net>:

>`vector<bool>` is already proven to
> be wrong. Its iterator does not even meet the ForwardIterator
> requirement. Change the whole iterator categories just to unblock
> proxy iterator? Dave already tried -- not accepted.

IMO the only reasonable choice is to retry that step - the current
iterator categories *are* broken.

- Daniel

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 10:23 AM, Daniel Krügler
<daniel....@gmail.com> wrote:
> IMO the only reasonable choice is to retry that step - the current
> iterator categories *are* broken.

Then the next problem comes. After the iterator requirements are
fixed, bit iterators are still slow. Yes, we can specialized known
STL algorithms for the bit iterators, like what libc++ did. But --
user can not create their own algorithms to benefit from those.
Then Bengt comes and says, we need to open the APIs for
bit iterators...

Worth? Maybe it's just "easier" to let all C++ books criticize
`vector<bool>` years after years.

I prefer to use `std::basic_string`'s approach: index-based
operations as member functions -- without iterators -- just
make the things possible into things working.

[Nicol Bolas]

On Monday, August 26, 2013 7:21:04 AM UTC-7, Zhihao Yuan wrote:

On Mon, Aug 26, 2013 at 9:22 AM, Nicol Bolas <jmck...@gmail.com> wrote:
> They can do a find-replace on "vector<bool>" with
> "bit_vector", and their code should immediately work as before. It needs to
> be a drop-in replacement so that they can stop using `vector<bool>`.

What I don't understand is why all of you think a drop-in replacement
of `vector<bool>` is possible.  `vector<bool>` is already proven to
be wrong.  Its iterator does not even meet the ForwardIterator
requirement.  Change the whole iterator categories just to unblock
proxy iterator?  Dave already tried -- not accepted.  `vector<bool>`
is just a mistake, a drop-in replacement of an mistake is also wrong.

But it is possible. The problem with `vector<bool>` is that it's called a vector, and therefore is expected to actually produce iterators that follow the iterator concepts and so forth.

`bit_vector` can do whatever it wants, because it's not a real vector. It can spit out "pseudo-iterators". It can do whatever. It can have the interface it has, and nobody has any explicit expectations that this interface matches that of the containers as defined by chapter 23.

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 7:10 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> `bit_vector` can do whatever it wants, because it's not a real vector. It
> can spit out "pseudo-iterators". It can do whatever. It can have the
> interface it has, and nobody has any explicit expectations that this
> interface matches that of the containers as defined by chapter 23.

So you mean it's Okey for bitvector's begin() to produce an
object which can be used in any STL algorithms but such an object
fits into no iterator categories? Don't you think that's an anti-pattern
of STL design?

[Howard Hinnant]

On Aug 26, 2013, at 7:18 PM, Zhihao Yuan <z...@miator.net> wrote:

> So you mean it's Okey for bitvector's begin() to produce an
> object which can be used in any STL algorithms but such an object
> fits into no iterator categories? Don't you think that's an anti-pattern
> of STL design?

Question for Zhihao:

Why does forward iterator's operator*() have to return a value_type& ?

I'm well aware that this is what C++98/03/11 requires. That's not what I'm asking. I'm asking what is the benefit of this requirement in the C++1y context? What problem does this requirement solve?

Howard

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 7:22 PM, Howard Hinnant
<howard....@gmail.com> wrote:
> Question for Zhihao:
>
> Why does forward iterator's operator*() have to return a value_type& ?
>
> I'm well aware that this is what C++98/03/11 requires. That's not what I'm asking. I'm asking what is the benefit of this requirement in the C++1y context? What problem does this requirement solve?

Afaics, it makes the pointed object modifiable. And move_iterator
significantly benefits from it. (Here is something I'm not sure:
move_iterator requires only InputIterator, while dereferencing an
InputIterator may return anything convertible to T -- is there anything
broken here?)

[Howard Hinnant]

On Aug 26, 2013, at 7:57 PM, Zhihao Yuan <z...@miator.net> wrote:

> On Mon, Aug 26, 2013 at 7:22 PM, Howard Hinnant
> <howard....@gmail.com> wrote:
>> Question for Zhihao:
>>
>> Why does forward iterator's operator*() have to return a value_type& ?
>>
>> I'm well aware that this is what C++98/03/11 requires. That's not what I'm asking. I'm asking what is the benefit of this requirement in the C++1y context? What problem does this requirement solve?
>
> Afaics, it makes the pointed object modifiable.

But today, I can do:

std::vector<boo> v(1);
*v.begin() = true;

And yet vector<bool>::iterator::operator*() isn't returning a bool&. But I am still modifying the referenced object.

> And move_iterator
> significantly benefits from it. (Here is something I'm not sure:
> move_iterator requires only InputIterator, while dereferencing an
> InputIterator may return anything convertible to T -- is there anything
> broken here?)

Yes.

http://cplusplus.github.io/LWG/lwg-active.html#2106

Howard

[Geoffrey Romer]

I'm not Zhihao, but...

One problem this solves is that code like this is guaranteed to work:

template <typename iter_t>

value_type& GetValue(iter_t iter) {

  return *iter;

}

If operator* can return a proxy with an implicit conversion to value_type, GetValue is at serious risk of undefined behavior. I've seen multiple real bugs in the wild arising from this problem, and they are truly heinous to diagnose (they've led to a concerted effort to purge Boost.ptr_container, a repeat offender in this respect, from our codebase).

This is not a knock-down objection, but it's an important cost to bear in mind.

Howard

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 8:16 PM, Geoffrey Romer <gro...@google.com> wrote:
> template <typename iter_t>
> value_type& GetValue(iter_t iter) {
> return *iter;
> }

I think this can be "corrected" by just replacing the return type
with `auto` :(

[Howard Hinnant]

On Aug 26, 2013, at 8:28 PM, Zhihao Yuan <z...@miator.net> wrote:

> On Mon, Aug 26, 2013 at 8:16 PM, Geoffrey Romer <gro...@google.com> wrote:
>> template <typename iter_t>
>> value_type& GetValue(iter_t iter) {
>> return *iter;
>> }
>
> I think this can be "corrected" by just replacing the return type
> with `auto` :(

I was going to suggest:

typename std::iterator_traits<iter_t>::reference

but I like Zhihao's suggestion a lot better. Unless you need the iterator_traits dance for SFINAE purposes.

Bottom line: All we have to do is stop assuming that *iter returns a value_type&. We already can not assume that for input iterators, do this does not seem like a big stretch. And we already can not assume it for output iterators, even though we can use output iterators to modify values.

Howard

[Howard Hinnant]

On Aug 26, 2013, at 8:16 PM, Geoffrey Romer <gro...@google.com> wrote:

> One problem this solves is that code like this is guaranteed to work:
>
> template <typename iter_t>
> value_type& GetValue(iter_t iter) {
> return *iter;
> }

Oops, I just realized this code is pretty dangerous even neglecting proxy iterators:

There's no enforced connection between iter_t and value_type. So what happens when value_type is const int and:

double d;
double* dp = &d;
const int& cr = GetValue(dp);

You've got a dangling reference. And I didn't even have to use proxies to crash this one. To make this safer one could (use auto, or):

template <typename iter_t>
typename std::iterator_traits<iter_t>::value_type&
GetValue(iter_t iter)
{
return *iter;
}

But by the time you've gone this far...

template <typename iter_t>

typename std::iterator_traits<iter_t>::reference

GetValue(iter_t iter)
{
return *iter;
}

Howard

[Zhihao Yuan]

On Mon, Aug 26, 2013 at 8:36 PM, Howard Hinnant
<howard....@gmail.com> wrote:
> Bottom line: All we have to do is stop assuming that *iter returns a value_type&.

Conceptually agree. And Stepanov's "Elements of Programming" 9.1
has the same thought: Writability as an assignment to _sink_(x), while
_sink_(x) is not necessarily a "real" reference to `x`.

Ah, I see... We should be able to specialize iterator_traits to unblock
proxy iterators...

[Howard Hinnant]

On Aug 26, 2013, at 8:58 PM, Zhihao Yuan <z...@miator.net> wrote:

> On Mon, Aug 26, 2013 at 8:36 PM, Howard Hinnant
> <howard....@gmail.com> wrote:
>> Bottom line: All we have to do is stop assuming that *iter returns a value_type&.
>
> Conceptually agree. And Stepanov's "Elements of Programming" 9.1
> has the same thought: Writability as an assignment to _sink_(x), while
> _sink_(x) is not necessarily a "real" reference to `x`.
>
> Ah, I see... We should be able to specialize iterator_traits to unblock
> proxy iterators...

And actually we already have done this for input iterators and output iterators. We just have this legacy requirement hanging around that forward iterators (and bi and rand) must return a value_type& from operator*() (const value_type& for non-mutable variants). The T& return from forward iterator operator*() is kind of like dandelions. It kind of looks pretty. And it is very hard to get rid of. :-) But I think we should make an effort to do so.

libc++ is a working implementation where vector<bool>::[const_]iterator works with everything in <algorithm>; some, but not enough of the algorithms at greatly increased performance. I.e. there is shipping implementation practice to back up all of my hot air. And we still need to deal with the fact that vector<bool> has a terrible name.

Howard

[David Krauss]

On Tuesday, August 27, 2013 9:06:37 AM UTC+8, Howard Hinnant wrote:

On Aug 26, 2013, at 8:58 PM, Zhihao Yuan <z...@miator.net> wrote:

> Ah, I see... We should be able to specialize iterator_traits to unblock
> proxy iterators...

And actually we already have done this for input iterators and output iterators.  We just have this legacy requirement hanging around that forward iterators (and bi and rand) must return a value_type& from operator*() (const value_type& for non-mutable variants).  The T& return from forward iterator operator*() is kind of like dandelions.  It kind of looks pretty.  And it is very hard to get rid of. :-)  But I think we should make an effort to do so.

Amen brother. Fleshing out the generic semantics will clean a mess that trying to scrub out details will only worsen. And progress forward rather than trip over trying to run backwards.

But the cleanup should extend into allocators as well. The allocator supplies the mapping (Allocator::address) from Iterator::reference to Iterator::pointer.

Conceptually, packing bits is an optimization of allocation. Aside from special functions like vector<bool>::flip, vector<bool> shouldn't need to be a specialization at all. With appropriately generic address arithmetic, and concepts to enable the special members, std::vector<bool> could be the generic instantiation of std::vector< bool, bitpacking_allocator >. Then std::deque could benefit from the same optimized algorithms, because its node and iterator classes would have internal bit-pointers.

The default allocator type argument of std::vector would be an alias template to select either std::allocator<T> or std::bitpacking_allocator. Users who want the non-packed functionality would explicitly specify std::allocator<T>. Migration would be reduced to deprecating that alias template.

Properly generic iterators/allocators should also allow range access to files, or if you prefer, user-space virtual memory. Interleaved arrays would be another application. I think we're missing out on a lot.

[Nicol Bolas]

On Monday, August 26, 2013 4:18:07 PM UTC-7, Zhihao Yuan wrote:

On Mon, Aug 26, 2013 at 7:10 PM, Nicol Bolas <jmck...@gmail.com> wrote:
> `bit_vector` can do whatever it wants, because it's not a real vector. It
> can spit out "pseudo-iterators". It can do whatever. It can have the
> interface it has, and nobody has any explicit expectations that this
> interface matches that of the containers as defined by chapter 23.

So you mean it's Okey for bitvector's begin() to produce an
object which can be used in any STL algorithms but such an object
fits into no iterator categories?  Don't you think that's an anti-pattern
of STL design?

No. Because it is not defined in accord with the requirements of the container concepts, it can do whatever it wants. Including look enough like a container to pass as one. Sometimes.

If you want to go through and change the iterator concepts to make it actually be a legitimate container, fine. But that shouldn't be a requirement for starting us the process of getting a real `vector<bool>` that's a real `vector` of real `bool`. And that process requires us to provide a drop-in replacement of the current class.

[Bengt Gustafsson]

Zhihao Yuan skrev 2013-08-27 01:57:
> On Mon, Aug 26, 2013 at 7:22 PM, Howard Hinnant
> <howard....@gmail.com> wrote:
>> Question for Zhihao:
>>
>> Why does forward iterator's operator*() have to return a value_type& ?
>>
>> I'm well aware that this is what C++98/03/11 requires. That's not what I'm asking. I'm asking what is the benefit of this requirement in the C++1y context? What problem does this requirement solve?
> Afaics, it makes the pointed object modifiable. And move_iterator
> significantly benefits from it. (Here is something I'm not sure:
> move_iterator requires only InputIterator, while dereferencing an
> InputIterator may return anything convertible to T -- is there anything
> broken here?)
>

No, he must be refering to something else, as the return value of
vector<bool>::iterator::operator* does indeed make the pointed object
modifiable.

I don't like when people speak in riddles to make other people feel like
idiots! Please instead try to explain the issue at hand as clearly as
you can.

The prime example I have been given of the badness of the vector<bool>
specialization is that it does not have a .data() method. So be it, but
in what case is using .data() preferred to using iterators?

The other problem was that some stl algorithms are very slow when the
input iterators are for vector<bool>, but when I suggest a simple
solution that would instead make them faster than their counterparts it
is immediately shot down for not being orthogonal enough.

I don't really see the relevance of the argument that "anyone who needs
a denser vector<bool> than the unspecialized one can always use
bit_vector". This ASSUMES that programmers that make very simple use of
a vector of bits aware of this new, later added class. At the same time
the reason for getting rid of the specialized vector<bool> seems to be
that we CAN'T ASSUME that programmers who are doing rather more complex
programming know that vector<bool> is special, even though this is
already pointed out in current textbooks.

I do think that the specialization was a mistake from the beginning, but
I think that we should move on with an apology and concentrate on making
it perform as expected from a packed representation, which requires the
API I mentioned before. Also I think that the suggestion to remove it
would never pass the committe scrutinization.

[Nevin Liber]

On 27 August 2013 04:43, Bengt Gustafsson <bengt.gu...@beamways.com> wrote:

I do think that the specialization was a mistake from the beginning, but I think that we should move on with an apology and concentrate on making it perform as expected from a packed representation, which requires the API I mentioned before. Also I think that the suggestion to remove it would never pass the committe scrutinization.

Looking at the people involved in this discussion, it seems more likely to me that the committee would be willing to remove it in the future than expand the incompatibility.  Note:  we are all individuals, and while some of us are on the committee, none of us speak for the committee.

[Geoffrey Romer]

Yes, it's _possible_ to rewrite that code so that it works with a proxy. I'm just saying that it's _harder_ to write correct code against a proxying iterator than against a non-proxying one. It's true that "all we have to do is stop assuming that *iter returns a value_type&", but the "we" here refers to all C++ programmers, so this is not a small thing, and undefined behavior is a pretty harsh punishment for those who fail to update themselves appropriately.

Now, sometimes you need a proxying iterator, because returning value_type& just isn't possible. That being the case, it's certainly preferable for such iterators to be a supported part of the iterator framework, and it's certainly desirable for them to be able to describe themselves accurately (e.g. vector<bool>::iterator supports random access, but can't return a value_type&), so I am wholly in favor of decomposing the iterator categories to describe value-access separately from traversal (along the lines of n1640), and relaxing the iterator requirements of the standard algorithms as much as possible.

What I don't want is for the STL container requirements to allow proxying iterators or, still worse, for the standard iterator concepts to permit proxying unconditionally. This would render some existing code incorrect, and worse, it would be incorrect in a subtle way that would probably work most of the time, because in practice the STL containers are unlikely to use proxying, so there may be a long lag between when the bug is written and when it is discovered.

[Nicol Bolas]

On Tuesday, August 27, 2013 2:43:33 AM UTC-7, Bengt Gustafsson wrote:

Zhihao Yuan skrev 2013-08-27 01:57:
> On Mon, Aug 26, 2013 at 7:22 PM, Howard Hinnant
> <howard....@gmail.com> wrote:
>> Question for Zhihao:
>>
>> Why does forward iterator's operator*() have to return a value_type& ?
>>
>> I'm well aware that this is what C++98/03/11 requires.  That's not what I'm asking.  I'm asking what is the benefit of this requirement in the C++1y context?  What problem does this requirement solve?
> Afaics, it makes the pointed object modifiable.  And move_iterator
> significantly benefits from it.  (Here is something I'm not sure:
> move_iterator requires only InputIterator, while dereferencing an
> InputIterator may return anything convertible to T -- is there anything
> broken here?)
>
No, he must be refering to something else, as the return value of
vector<bool>::iterator::operator* does indeed make the pointed object
modifiable.

I don't like when people speak in riddles to make other people feel like
idiots! Please instead try to explain the issue at hand as clearly as
you can.

The prime example I have been given of the badness of the vector<bool>
specialization is that it does not have a .data() method. So be it, but
in what case is using .data() preferred to using iterators?

Because it's part of std::vector's interface. std::vector *requires* that this code works:

vector<T> t{...};
T* tp = &t[0];
tp += 3;
*tp == t[3];

And that will work for all T... so long as T is not `bool`.

It is not for you to decide whether this is good code or not. That's the interface that `vector` provides by the standard, and that is the interface that we should expect to have. And we do... as long as T is not `bool`.

There is no reason why this should be the case. A space-optimized object can be used separately.

[Nevin Liber]

On 27 August 2013 18:17, Nicol Bolas <jmck...@gmail.com> wrote:

Because it's part of std::vector's interface. std::vector *requires* that this code works:

vector<T> t{...};
T* tp = &t[0];
tp += 3;
*tp == t[3];

And that will work for all T... so long as T is not `bool`.

It is not for you to decide whether this is good code or not.

And even of people don't like that code, surely the following is reasonable:

void DoSomething(bool& flag) { /* ... */ }

DoSomething(t[3]);

-- 

[Bengt Gustafsson]

No, the standard says exactly what the standard says: The code above should work for all T except bool. There is a special clause in the standard detailing that vector<bool> is to be specialized to NOT work as you claim. That's what we are discussing here, isn't it? You can claim that we should change the standard because it is inconsistent or confusing but can NOT claim that we should change the standard because it contradicts itself!

Personally I am indifferent, as I don't use vector<bool>. But I don't want the standard to be changed under the feet of people, and I dislike that more than it being clumsy as it is. In addition I think that C++ should focus on being an outstanding performer, which is why I suggested to include APIs to allow fast implementations of algorithms in a portable way.

There is no reason why this should be the case. A space-optimized object can be used separately.

--
 
---
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-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Nevin Liber]

On 28 August 2013 02:27, Bengt Gustafsson <bengt.gu...@beamways.com> wrote:

Personally I am indifferent, as I don't use vector<bool>. But I don't want the standard to be changed under the feet of people,

So we should never deprecate and remove anything?  It isn't like it would go away before C++20 (at least).

  In addition I think that C++ should focus on being an outstanding performer, which is why I suggested to include APIs to allow fast implementations of algorithms in a portable way.

Even if you get your wish, there is still no need to make vector<bool> diverge more than it already does from vector<T>.  The even better bit-packed data structure does not have to be called vector<bool>.

[Nicol Bolas]

Which is good because I never said anything about contradicting itself. You asked for someone to "explain the issue at hand", and I did. `vector<bool>` does not behave like a `vector` and it should. That's the issue at hand.

Personally I am indifferent, as I don't use vector<bool>. But I don't want the standard to be changed under the feet of people, and I dislike that more than it being clumsy as it is.

Have you read anything in this thread? The plan for changing this is to add a drop-in class that provides the same interface, so that people can simply find/replace within their code. Then we deprecate the `vector<bool>` specialization. It will still be there for at least one version alongside the stand-alone class. That way, everyone has several years and version releases to do that find/replace within their code to use the new class rather than `vector<bool>`.

And then we cut out the `vector<bool>` specialization. Nobody is suggesting that it be changed "under the feet of people".