220 4665 <DBDB593B-7988-4A2E-AD88-0B5D37D136FD@gmail.com> article
Path: news.gmane.org!not-for-mail
From: Howard Hinnant <howard.hinnant@gmail.com>
Newsgroups: gmane.comp.lang.c++.isocpp.proposals
Subject: Re: Remove vector<bool>?
Date: Tue, 28 May 2013 12:43:36 -0400
Lines: 100
Approved: news@gmane.org
Message-ID: <DBDB593B-7988-4A2E-AD88-0B5D37D136FD@gmail.com>
References: <CAGsORuDQdeWAO5yjA6=h0hW9Y0Sj4F1gcHB61udw5JFmtx+g4Q@mail.gmail.com> <CAGg_6+O9XJucMxwEhU+50Dzx0Tz7XRK0cWyrkUHuPSoEz9TqEw@mail.gmail.com>
Reply-To: std-proposals@isocpp.org
NNTP-Posting-Host: plane.gmane.org
Mime-Version: 1.0 (Mac OS X Mail 6.3 \(1503\))
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: ger.gmane.org 1369759426 26210 80.91.229.3 (28 May 2013 16:43:46 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Tue, 28 May 2013 16:43:46 +0000 (UTC)
To: std-proposals@isocpp.org
Original-X-From: std-proposals+bncBCK2HM4L6YERBO55SOGQKGQESJAK4QA@isocpp.org Tue May 28 18:43:47 2013
Return-path: <std-proposals+bncBCK2HM4L6YERBO55SOGQKGQESJAK4QA@isocpp.org>
Envelope-to: gclcip-std-proposals@m.gmane.org
Original-Received: from mail-oa0-f71.google.com ([209.85.219.71])
	by plane.gmane.org with esmtp (Exim 4.69)
	(envelope-from <std-proposals+bncBCK2HM4L6YERBO55SOGQKGQESJAK4QA@isocpp.org>)
	id 1UhMzt-0005QJ-Fv
	for gclcip-std-proposals@m.gmane.org; Tue, 28 May 2013 18:43:41 +0200
Original-Received: by mail-oa0-f71.google.com with SMTP id n12sf42322571oag.6
        for <gclcip-std-proposals@m.gmane.org>; Tue, 28 May 2013 09:43:40 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=x-beenthere:mime-version:subject:from:in-reply-to:date:message-id
         :references:to:x-mailer:x-original-sender
         :x-original-authentication-results:reply-to:precedence:mailing-list
         :list-id:x-google-group-id:list-post:list-help:list-archive
         :list-subscribe:list-unsubscribe:content-type
         :content-transfer-encoding;
        bh=4GvtRn45SmA0vCi6i10StfNVZA74DV73fVl5W9R/sZ8=;
        b=MrPYs2XFzFZ513glowgc8RlD89bmoKhtWhD4xzF70QTvbgDqlQSLxHJz8ioAZzGdOW
         tD2Y7Odr/z504uMn0BR06pj7WXB4tDUYNeZvdKCygZ9cwTEQuSfmPSA0IbIwv3a4x8J9
         L1fFGXLIOx86JBFN9EikjB8OTAxzYqB0AdkqruGQ3YPDj03/62kWyVd0LehIeZMvPde9
         uGyGTZ9MVoJgBRHHQ6VAVk3NBZcyDaRm5zNpRIwDwK/CrLoYNe2h8vEawo/mPvQXnWy5
         AKo9SupPAeDgvjlJnyqROoiGEOAau0rUebuJHhgdws8xPyy/ghDsJ7jMHlfvhmF6DQua
   
X-Received: by 10.182.86.71 with SMTP id n7mr8167877obz.8.1369759420446;
        Tue, 28 May 2013 09:43:40 -0700 (PDT)
X-BeenThere: std-proposals@isocpp.org
Original-Received: by 10.182.105.202 with SMTP id go10ls1232925obb.2.gmail; Tue, 28 May
 2013 09:43:38 -0700 (PDT)
X-Received: by 10.182.226.225 with SMTP id rv1mr21029451obc.61.1369759418489;
        Tue, 28 May 2013 09:43:38 -0700 (PDT)
Original-Received: from mail-ie0-x22c.google.com (mail-ie0-x22c.google.com [2607:f8b0:4001:c03::22c])
        by mx.google.com with ESMTPS id yw5si19947575obb.164.2013.05.28.09.43.38
        for <std-proposals@isocpp.org>
        (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
        Tue, 28 May 2013 09:43:38 -0700 (PDT)
Received-SPF: pass (google.com: domain of howard.hinnant@gmail.com designates 2607:f8b0:4001:c03::22c as permitted sender) client-ip=2607:f8b0:4001:c03::22c;
Original-Received: by mail-ie0-f172.google.com with SMTP id 17so1264430iea.17
        for <std-proposals@isocpp.org>; Tue, 28 May 2013 09:43:38 -0700 (PDT)
X-Received: by 10.50.178.198 with SMTP id da6mr7511628igc.49.1369759418102;
        Tue, 28 May 2013 09:43:38 -0700 (PDT)
Original-Received: from [10.0.1.4] (cpe-24-59-186-27.twcny.res.rr.com. [24.59.186.27])
        by mx.google.com with ESMTPSA id ij6sm18723215igb.1.2013.05.28.09.43.36
        for <std-proposals@isocpp.org>
        (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
        Tue, 28 May 2013 09:43:36 -0700 (PDT)
In-Reply-To: <CAGg_6+O9XJucMxwEhU+50Dzx0Tz7XRK0cWyrkUHuPSoEz9TqEw@mail.gmail.com>
X-Mailer: Apple Mail (2.1503)
X-Original-Sender: howard.hinnant@gmail.com
X-Original-Authentication-Results: mx.google.com;       spf=pass (google.com:
 domain of howard.hinnant@gmail.com designates 2607:f8b0:4001:c03::22c as
 permitted sender) smtp.mail=howard.hinnant@gmail.com;       dkim=pass header.i=@gmail.com
Precedence: list
Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org
List-ID: <std-proposals.isocpp.org>
X-Google-Group-Id: 399137483710
List-Post: <http://groups.google.com/a/isocpp.org/group/std-proposals/post?hl=en>,
 <mailto:std-proposals@isocpp.org>
List-Help: <http://support.google.com/a/isocpp.org/bin/topic.py?hl=en&topic=25838>,
 <mailto:std-proposals+help@isocpp.org>
List-Archive: <http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en>
List-Subscribe: <http://groups.google.com/a/isocpp.org/group/std-proposals/subscribe?hl=en>,
 <mailto:std-proposals+subscribe@isocpp.org>
List-Unsubscribe: <http://groups.google.com/a/isocpp.org/group/std-proposals/subscribe?hl=en>,
 <mailto:googlegroups-manage+399137483710+unsubscribe@googlegroups.com>
Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:4665
Archived-At: <http://permalink.gmane.org/gmane.comp.lang.c++.isocpp.proposals/4665>


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

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

+1

>=20
> If someone were to propose making it deprecated in C++17, I could be for =
that.
>=20
> Because this is a breaking change, I would like to see such a proposal ta=
lk about the practical use cases for having a vector<bool> that was just an=
other 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: d=
ynamic array of bits is a classic and valuable data structure in computer s=
cience:

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<b=
ool> should have to do little more than change the name of the container.

Additionally we could add sweetener to encourage the migration.  For exampl=
e 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, ForwardIte=
rator2 first2);

template <class ForwardIterator>
    ForwardIterator
    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator l=
ast);

template <class InputIterator1, class InputIterator2>
    bool
    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first=
2);

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

--=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/?hl=3Den.



.