96. Vector<bool> is not a container

Section: 23.3.11 [vector] Status: NAD Submitter: AFNOR Opened: 1998-10-07 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [vector].

View all issues with NAD status.

Discussion:

vector<bool> is not a container as its reference and pointer types are not references and pointers.

Also it forces everyone to have a space optimization instead of a speed one.

See also: 99-0008 == N1185 Vector<bool> is Nonconforming, Forces Optimization Choice.

[In Santa Cruz the LWG felt that this was Not A Defect.]

[In Dublin many present felt that failure to meet Container requirements was a defect. There was disagreement as to whether or not the optimization requirements constituted a defect.]

[The LWG looked at the following resolutions in some detail:
     * Not A Defect.
     * Add a note explaining that vector<bool> does not meet Container requirements.
     * Remove vector<bool>.
     * Add a new category of container requirements which vector<bool> would meet.
     * Rename vector<bool>.

No alternative had strong, wide-spread, support and every alternative had at least one "over my dead body" response.

There was also mention of a transition scheme something like (1) add vector_bool and deprecate vector<bool> in the next standard. (2) Remove vector<bool> in the following standard.]

[Modifying container requirements to permit returning proxies (thus allowing container requirements conforming vector<bool>) was also discussed.]

[It was also noted that there is a partial but ugly workaround in that vector<bool> may be further specialized with a customer allocator.]

[Kona: Herb Sutter presented his paper J16/99-0035==WG21/N1211, vector<bool>: More Problems, Better Solutions. Much discussion of a two step approach: a) deprecate, b) provide replacement under a new name. LWG straw vote on that: 1-favor, 11-could live with, 2-over my dead body. This resolution was mentioned in the LWG report to the full committee, where several additional committee members indicated over-my-dead-body positions.]

Discussed at Lillehammer. General agreement that we should deprecate vector<bool> and introduce this functionality under a different name, e.g. bit_vector. This might make it possible to remove the vector<bool> specialization in the standard that comes after C++0x. There was also a suggestion that in C++0x we could additional say that it's implementation defined whether vector<bool> refers to the specialization or to the primary template, but there wasn't general agreement that this was a good idea.

We need a paper for the new bit_vector class.

[ Batavia: ]

The LWG feels we need something closer to SGI's bitvector to ease migration from vector<bool>. Although some of the funcitonality from N2050 could well be used in such a template. The concern is easing the API migration for those users who want to continue using a bit-packed container. Alan and Beman to work.

[ Post Summit Alisdair adds: ]

vector<bool> is now a conforming container under the revised terms of C++0x, which supports containers of proxies.

Recommend NAD.

Two issues remain:

i/ premature optimization in the specification. There is still some sentiment that deprecation is the correct way to go, although it is still not clear what it would mean to deprecate a single specialization of a template.

Recommend: Create a new issue for the discussion, leave as Open.

ii/ Request for a new bitvector class to guarantee the optimization, perhaps with a better tuned interface.

This is a clear extension request that may be handled via a future TR.

[ Batavia (2009-05): ]

We note that most of this issue has become moot over time, and agree with Alisdair's recommendations. Move to NAD Future for reconsideration of part (ii).

[ 2009-07-29 Alisdair reopens: ]

This infamous issue was closed as NAD Future when concepts introduced support for proxy iterators, so the only remaining requirement was to provide a better type to support bitsets of dynamic length. I fear we must re-open this issue until the post-concept form of iterators is available, and hopefully will support the necessary proxy functionality to allow us to close this issue as NAD.

I recommend we spawn a separate issue (1184) requesting a dynamic length bitset and pre-emptively file it as NAD Future. It is difficult to resolve #96 when it effectively contains two separate sub-issues.

[ 2009-10 Santa Cruz: ]

Mark as NAD, and give rationale.

Proposed resolution:

We now have: N2050 and N2160.

Rationale:

We want to support proxy iterators but that is going to be separate work. Don't want to see this issue come back in these kinds of terms. We're interested in a separate container, and proxy iterators, but both of those are separate issues.

We've looked at a lot of ways to fix this that would be close to this, but those things would break existing code. Attempts to fix this directly have not been tractable, and removing it has not been tractable. Therefore we are closing.