Doc. no.   WG21/N2160=J16/07-0020
Date:        2007-01-12
Project:     Programming Language C++
Reply to:   Beman Dawes <bdawes@acm.org>

Library Issue 96: Fixing `vector<bool>`

Library Issue 96, Vector<bool> is not a container, has been open since 1998. It needs to be fixed for C++0x.

See References for details.

In 1998, admitting that the committee made a mistake was controversial. Since then Java has had to deprecate such significant portions of their libraries that the idea C++ would be ridiculed for deprecating a single minor template specialization seems quaint.

To ensure a smooth transition, the dynamic_bitset library is proposed for C++0x (rather than TR2) and explicit guidance is provided for both library implementors and ordinary users.

Deprecate or remove?

Undesirable library features are usually removed only after having been first deprecated in a prior standard. This two step process puts users on notice that the feature is going to later be removed, giving them plenty of time to migrate existing code to the replacement feature. To do otherwise would break existing code without prior warning.

vector<bool> is unusual, however, because it is a template specialization. Other than the flip() member function, most practical functionality is the same as for the primary template. Thus removing the specialization will not necessarily break user code, although it may alter the performance characteristics.

I tried several of the code search engines to get an idea how commonly std::vector<bool>::flip is used, but could not come up with reliable numbers. It was too hard to separate out use of std::vector<bool>::flip from uses of various non-standard bit vector functions of the same name. It did become clear, however, that std::vector<bool>::flip use is rare enough that examples are very difficult to find, and that dynamic bit vectors, both from Boost and elsewhere are in common use, particularly in graphics applications.

I personally think that it would be preferable to remove the vector<bool> specialization rather than deprecate it, since the impact on users is so minimal, and since the sooner vector<bool> goes away, the better. The proposed resolution below specifies removal. The committee can change that to deprecation if preferred.

What we say...

Regardless of the choice of deprecation or removal, a smooth transition path must be provided for both implementors and users. In early discussions of how to fix vector<bool>, the LWG felt that any solution needed to provide clear guidance regarding that transition path to Standard Library implementors, the C++ community as a whole, and to users. The remainder of this section provides that guidance.

Guidance for implementors

During a transition period, Standard Library implementors are encouraged to give users a choice:

// supply default (remove for default of no vector<bool> specialization)
# if !defined( defined(STD_VECTOR_BOOL_SPECIAL) && !defined(STD_VECTOR_BOOL_NOT_SPECIAL)
#   define STD_VECTOR_BOOL_SPECIAL
# endif

// validate user supplied defines
# if defined(STD_VECTOR_BOOL_SPECIAL) && defined(STD_VECTOR_BOOL_NOT_SPECIAL)
#   error Both STD_VECTOR_BOOL_SPECIAL and STD_VECTOR_BOOL_NOT_SPECIAL defined - you must supply one at most
# endif

// supply specialization if called for
# if defined(STD_VECTOR_BOOL_SPECIAL)
  ... specialization here ...
# endif

Implementations should default to STD_VECTOR_BOOL_SPECIAL (by supplying the first four lines of the above code) as long as their users are best served by defaulting to the specialization for vector<bool>. When their users would no longer best be served by defaulting to the specialization for vector<bool>, implementations can change the default to no specialization by removing the first four lines of code. When implementations no longer wish to support specialization for vector<bool>, they can eliminate all of the above code, including the specialization. If implementations wish to issue an error once the specialization choices are removed, they can do something like:

// verify users no long depend on STD_VECTOR_BOOL_SPECIAL
# if defined(STD_VECTOR_BOOL_SPECIAL)
#   error STD_VECTOR_BOOL_SPECIAL no longer supported - use std::dynamic_bitset instead
# endif

Guidance for the C++ community

The 1998 C++ Standard Library's vector<bool> specialization was a mistake - it does not meet the requirements for a container, its iterator does not meet the iterator requirements, and it supplies a sometimes unfortunate optimization. Search the web for "vector<bool> problems" for details.

The C++0x standard removes the C++ Standard Library's vector<bool> specialization. A new library, dynamic_bitset, is provided for those needing efficient bit manipulation. Guidance is given for users to enable a smooth transition path.

Guidance for users with existing code using the `vector<bool>` specialization

If you don't care about vector<bool>'s special features, do nothing. Code that does not expect vector<bool> to have special characteristics will continue to work without change.
If you do want the vector<bool> specialization, define STD_VECTOR_BOOL_SPECIAL. Plan to eventually switch to std::dynamic_bitset since it isn't good practice to depend on removed features.
If you do not want the vector<bool> specialization, define STD_VECTOR_BOOL_NOT_SPECIAL.

Guidance for users writing new code

If you need a container with iterators and don't care about space optimizations or bit twiddling functions, use vector<bool>. Define STD_VECTOR_BOOL_NOT_SPECIAL if you want to be sure you don't get the old specialization.
If you don't need a container with iterators, care about space, or need bit twiddling functions, use std::dynamic_bitset.

Proposed Resolution

Remove 23.2.6 [vector.bool], Class vector<bool>, in its entirety.

Add N2050, "Proposal to Add a Dynamically Sizeable Bitset to the Standard Library Technical Report (Revision 1)" to the C++0x working paper. See www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf.

References

N2130, C++ Standard Library Active Issues List, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2130.html#96

N1185, “vector<bool> Is Nonconforming, and Forces Optimization Choice”, Herb Sutter, 22nd Feb. 1999. Library. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1999/n1185.pdf

N1847, “vector<bool>: More Problems, Better Solutions”, Herb Sutter, 20th Oct. 1999. Library. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1847.pdf

“Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library”, Scott Meyers, 2001, Addison-Wesley. pp79 – 82.

Meaning of "deprecate"

The definition of deprecate is given in appendix D of the standard as "Normative for the current edition of the Standard, but not guaranteed to be part of the Standard in future revisions."

Library Issue 96: Fixing vector<bool>