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/ > -- --- 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_62_22613202.1377466122666 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

I remember in pre-standard days when I started out wi= th C++ that the STL implementation we used had a special bit_vector contain= er 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 opin= ion far to late to revert the specialization, although introducing it was p= robably 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 t= ryinging to create a pointer to a bit and some performance issues. He= re are my comments:

- The pointer creation problem is no= t such an important issue as it is immediately flagged as an error by the c= ompiler. For example VS2012 gives an "illegal indirection" error, as you ca= n'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.

<= div>- The performance of the iterator, and its dereference operator etc. ma= y be better or worse than for instance for a vector<char>, which woul= d 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 o= f 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 t= here is a reasonably small subset of the standard algorithms that make sens= e anyway. To make this possible a "wordwise" access possibility must be add= ed to vector<bool>::iterator, as well as an accessor for the bit offs= et within the current word. This API can be defined by each library impleme= nter (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 un= due slowness of the iterator operations is a big problem, a small problem o= r 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 {

...

type= def X word_type;

static const int bit= s_per_word =3D 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

};<= /div>

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

find

count

search_n

co= py

swap_ranges

reverse

rotate

<= /div>

Most other algorithms, for instance replace, is meaningless for b= ool 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 ve= ctor<bool> despite now about 20 years of C++ so this issue is maybe n= ot extremely important. If I were to use it, however, I would think that in= serting/removing bits in the middle in a high performance way would be a ve= ry 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 star= t 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 pr= oblem here is that many implementations (all?) use a bit mask to make itera= tor accesses faster. Converting this bit to a number is costly on most proc= essors. Maybe the API would be better off if it returned the bit mask inste= ad, as it is less costly to convert from bit number to bit mask (1<<b= it_no).

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

I saw Herb's pa= per:

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

But it's not adopted.

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

--
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 &= quot;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-proposals/<= /a>.
------=_Part_62_22613202.1377466122666-- .