A Specification to deprecate vector<bool>

Document Number: n2204(07-0064)
Alisdair Meredith <alisdair.meredith@uk.renaultf1.com>

The Problem

The 2003 Standard requires a partial specialization of the standard library vector container for bool values. This specification has a number of problems (explained many times over the years) and it has been agreed in principle it should be deprecated (and not removed) in the next Standard, and a replacement provided. See LWG Issue 96 and Beman Dawes paper n2160 for further details if required.

One of the major problems with deprecation is that the existing specification leaves the semantics of all operations completely undefined. However, there is a widespread understanding that the intent was to mandate a space-optimized implementation and that flip operations would switch values from true to false and back again.

This paper provides wording for the missing semantics, so that the specialization can be safely deprecated. It might require a little more attention once the primary template supports concepts and sequence containers, but it is not expected to see revisions for other language features such as rvalue references or const-expressions. It does not support the new data member of the primary template.

The replacement functionality is left to another paper, such as n2050.

Proposed changes to the working paper

Move the whole of clause 23.1.6 [vector.bool] into appendix D.


D? [depr.vector.bool]

-1- To optimize space allocation, a specialization of vector for bool elements is provided:

	namespace std {
	template <class Allocator> class vector<bool, Allocator> {
		// types:
		typedef bool const_reference;
		typedef implementation-defined iterator; // See 23.1
		typedef implementation-defined const_iterator; // See 23.1
		typedef implementation-defined size_type; // See 23.1
		typedef implementation-defined difference_type;// See 23.1
		typedef bool value_type;
		typedef Allocator allocator_type;
		typedef implementation-defined pointer;
		typedef implementation-defined const_pointer;
		typedef std::reverse_iterator<iterator> reverse_iterator;
		typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

		// bit reference:
		class reference {
			friend class vector;
			operator bool() const;
			reference& operator=(const bool x);
			reference& operator=(const reference& x);
			void flip(); // flips the bit

		// construct/copy/destroy:
		explicit vector(const Allocator& = Allocator());
		explicit vector(size_type n, const bool& value = false,
		const Allocator& = Allocator());
		template <class InputIterator>
		vector(InputIterator first, InputIterator last,
		const Allocator& = Allocator());
		vector(const vector<bool,Allocator>& x);
		vector<bool,Allocator>& operator=(const vector<bool,Allocator>& x);
		template <class InputIterator>
		void assign(InputIterator first, InputIterator last);
		void assign(size_type n, const bool& t);
		allocator_type get_allocator() const;

		// iterators:
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;
		reverse_iterator rbegin();
		const_reverse_iterator rbegin() const;
		reverse_iterator rend();
		const_reverse_iterator rend() const;
		const_iterator cbegin() const;
		const_iterator cend() const;
		const_reverse_iterator crbegin() const;
		const_reverse_iterator crend() const;

		// capacity:
		size_type size() const;
		size_type max_size() const;
		void resize(size_type sz, bool c = false);
		size_type capacity() const;
		bool empty() const;
		void reserve(size_type n);

		// element access:
		reference operator[](size_type n);
		const_reference operator[](size_type n) const;
		const_reference at(size_type n) const;
		reference at(size_type n);
		reference front();
		const_reference front() const;
		reference back();
		const_reference back() const;

		// modifiers:
		void push_back(const bool& x);
		void pop_back();
		iterator insert(iterator position, const bool& x);
		void insert (iterator position, size_type n, const bool& x);
		template <class InputIterator>
		void insert(iterator position,
		InputIterator first, InputIterator last);
		iterator erase(iterator position);
		iterator erase(iterator first, iterator last);
		void swap(vector<bool,Allocator>&);
		static void swap(reference x, reference y);
		void flip(); // flips all bits
		void clear();
	// specialized algorithms:
	template <class Allocator>
	void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);

-2- Unless described below, all operations have the same requirements and semantics as the primary vector template, except that operations dealing with the bool value type map to bit values in the container's storage.

-3- There is no requirement that the data is stored as a contiguous allocation of bool values. A space-optimized representation of bits is recommended instead.

-4- reference is a class that simulates the behavior of references of a single bit in vector<bool>. The conversion operator returns true when the bit is set, and false otherwise. The assignment operator sets the bit when the argument is (convertible to) true and clears it otherwise. flip reverses the state of the bit.

-5- flip reverses the state of each bit in the container. It is unspecified if it has any effect on other allocated but unused bits.