D????R1
vector<bool> as an underlying container in flat adaptors

1. Introduction

[flat.map.defn] defines flat_map as:

template<class Key, class T, class Compare = less<Key>,         class KeyContainer = vector<Key>, class MappedContainer = vector<T>>class flat_map {

[flat.map.overview]/7 requires that KeyContainer and MappedContainer be sequence containers. Notably, vector<bool> is not a sequence container.

Because KeyContainer and MappedContainer both default to vector, the following code is ill-formed:

std::flat_map<int, bool> my_map;

To use bool as a mapped type, the user must specify an alternative sequence container, such as deque:

std::flat_map<int, bool, std::less<int>, std::vector<int>, std::deque<bool>> my_map;

This formulation is verbose and requires the user to know exactly which alternative sequence container to drop in. Additionally, the compilation errors generated when a user fails to override the container are difficult to understand, especially for new C++ developers.

A similar issue exists for flat_multimap, flat_set, and flat_multiset.

This paper proposes changes to flat_map, flat_multimap, flat_set, and flat_multiset so that vector<bool> is usable as an underlying container without affecting any other conforming instantiations.

2. Details

Before covering the proposed wording changes, it is important to understand why vector<bool> cannot be used as the container in the flat_ adaptors. We will center the discussion on flat_map, but the same concepts apply to the other three flat adaptors.

There are two problems:

1. Incompatible Reference Types: reference, const_reference and the return types of flat_map::operator[] and flat_map::at are spelled in terms of mapped_type and value_type (see [flat.map.defn]). The reference type for vector<bool> is not bool&. It is a proxy class that simulates a direct reference to a bool.

2. Sequence Container Requirement: The sequence container requirement explicitly excludes vector<bool> (see [flat.map.overview]/7).

The fix for the first problem is to replace T& as the reference type with whatever reference type the underlying container’s iterators produce (via iter_reference_t).

For every container that is valid today this is a no-op. iter_reference_t<C::iterator> is T& and iter_reference_t<C::const_iterator> is const T&, so the typedefs and signatures remain unchanged for all currently-supported containers.

For vector<bool>, iter_reference_t<C::iterator> is the proxy class type and iter_reference_t<C::const_iterator> is bool. These resolutions make the declarations well-formed, allowing code like my_map[1] = true.

The fix for the second problem is to admit vector<bool> by name. vector<bool> does not meet the sequence container requirements. As just one example, vector<bool> violates the X::reference equal T& container requirement. Other than the wording change, no other changes are required to address the second problem.

3. Other Container Adaptors

stack, queue, and priority_queue do not suffer from this problem because their reference and const_reference typedefs are defined in terms of the underlying container. As an example, consider [priority.queue]:

namespace std {  template<class T, class Container = vector<T>,           class Compare = less<typename Container::value_type>>  class priority_queue {  public:    using value_type      = Container::value_type;    using reference       = Container::reference;    using const_reference = Container::const_reference;    using size_type       = Container::size_type;    using container_type  = Container;    using value_compare   = Compare;    // ...

In these cases, the adaptors expose whatever reference type the underlying container provides. In the case of vector<bool>, reference resolves to vector<bool>::reference, which is the proxy class.

4. bool Keys and Sets

The case that motivates this proposal is flat_map<K, bool>. The same change also makes bool work as a key (flat_map<bool, V>, flat_multimap<bool, V>, flat_set<bool>, flat_multiset<bool>).

flat_map<bool, V> and flat_set<bool> hold at most two entries. flat_multimap<bool, V> and flat_multiset<bool> hold at most two distinct keys. These instantiations are not particularly useful, and we don’t expect people to use them often. However, it’s more consistent to support them. Additionally, once vector<bool> is permitted on the mapped side, allowing it on the key side is trivial.

5. Proposed Wording

Insertions are shown as green text and deletions as red strike-through text .

5.1. [flat.map]

Modify [flat.map.overview]/7 as follows:

Any type C that meets the sequence container requirements ([sequence.reqmts]) , or vector<bool> ([vector.bool]), can be used to instantiate flat_map, as long as C::iterator meets the Cpp17RandomAccessIterator requirements and invocations of member functions C::size and C::max_size do not exit via an exception. In particular, vector ([vector]) , vector<bool>, and deque ([deque]) can be used.

[Note 3: vector<bool> is not a sequence container. While vector<bool> is not a sequence container, it provides the necessary interface and proxy iterators to be supported here. — end note]

Modify [flat.map.defn] as follows:

namespace std {
  template<class Key, class T, class Compare = less<Key>,
           class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
  class flat_map {
  public:
    // types
    using key_type                = Key;
    using mapped_type             = T;
    using value_type              = pair<key_type, mapped_type>;
    using key_compare             = Compare;
    using value_compare           = unspecified;
    using reference              = pair<const key_type&, mapped_type&>;
    using const_reference        = pair<const key_type&, const mapped_type&>;
    using key-const-reference    = iter_reference_t<typename KeyContainer::const_iterator>;     // exposition only
    using mapped-reference       = iter_reference_t<typename MappedContainer::iterator>;        // exposition only
    using mapped-const-reference = iter_reference_t<typename MappedContainer::const_iterator>;  // exposition only
    using reference              = pair<key-const-reference, mapped-reference>;
    using const_reference        = pair<key-const-reference, mapped-const-reference>;
    using size_type               = size_t;
    using difference_type         = ptrdiff_t;
    using iterator                = implementation-defined;     // see [container.requirements]
    using const_iterator          = implementation-defined;     // see [container.requirements]
    using reverse_iterator        = std::reverse_iterator<iterator>;
    using const_reverse_iterator  = std::reverse_iterator<const_iterator>;

    using key_container_type      = KeyContainer;
    using mapped_container_type   = MappedContainer;

    // ...

    class value_compare {
      private:
        key_compare comp;                                    // exposition only
        constexpr value_compare(key_compare c) : comp(c) {}  // exposition only

      public:
        bool operator()(const_reference x, const_reference y) const {
        bool operator()(pair<const key_type&, const mapped_type&> x, pair<const key_type&, const mapped_type&> y) const {
          return comp(x.first, y.first);
        }
    };

    // ...
  };
}

Modify [flat.map.access] as follows:

mapped_type& operator[](const key_type& x);
iter_reference_t<typename MappedContainer::iterator> operator[](const key_type& x);

mapped_type& operator[](key_type&& x);
iter_reference_t<typename MappedContainer::iterator> operator[](key_type&& x);

template<class K>
  mapped_type& operator[](K&& x);
  iter_reference_t<typename MappedContainer::iterator> operator[](K&& x);

mapped_type& at(const key_type& x);
iter_reference_t<typename MappedContainer::iterator> at(const key_type& x);

const mapped_type& at(const key_type& x) const;
iter_reference_t<typename MappedContainer::const_iterator> at(const key_type& x) const;

template<class K>
  mapped_type& at(const K& x);
  iter_reference_t<typename MappedContainer::iterator> at(const K& x);

template<class K>
  const mapped_type& at(const K& x) const;
  iter_reference_t<typename MappedContainer::const_iterator> at(const K& x) const;

5.2. [flat.multimap]

Modify [flat.multimap.overview]/7 as follows:

Any type C that meets the sequence container requirements ([sequence.reqmts]) , or vector<bool> ([vector.bool]), can be used to instantiate flat_multimap, as long as C::iterator meets the Cpp17RandomAccessIterator requirements and invocations of member functions C::size and C::max_size do not exit via an exception. In particular, vector ([vector]) , vector<bool>, and deque ([deque]) can be used.

[Note 3: vector<bool> is not a sequence container. While vector<bool> is not a sequence container, it provides the necessary interface and proxy iterators to be supported here. — end note]

Modify [flat.multimap.defn] as follows:

namespace std {
  template<class Key, class T, class Compare = less<Key>,
           class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
  class flat_multimap {
  public:
    // types
    using key_type                = Key;
    using mapped_type             = T;
    using value_type              = pair<key_type, mapped_type>;
    using key_compare             = Compare;
    using value_compare           = unspecified;
    using reference              = pair<const key_type&, mapped_type&>;
    using const_reference        = pair<const key_type&, const mapped_type&>;
    using key-const-reference    = iter_reference_t<typename KeyContainer::const_iterator>;     // exposition only
    using mapped-reference       = iter_reference_t<typename MappedContainer::iterator>;        // exposition only
    using mapped-const-reference = iter_reference_t<typename MappedContainer::const_iterator>;  // exposition only
    using reference              = pair<key-const-reference, mapped-reference>;
    using const_reference        = pair<key-const-reference, mapped-const-reference>;
    using size_type               = size_t;
    using difference_type         = ptrdiff_t;
    using iterator                = implementation-defined;     // see [container.requirements]
    using const_iterator          = implementation-defined;     // see [container.requirements]
    using reverse_iterator        = std::reverse_iterator<iterator>;
    using const_reverse_iterator  = std::reverse_iterator<const_iterator>;

    using key_container_type      = KeyContainer;
    using mapped_container_type   = MappedContainer;

    // ...

    class value_compare {
      private:
        key_compare comp;                                    // exposition only
        constexpr value_compare(key_compare c) : comp(c) {}  // exposition only

      public:
        bool operator()(const_reference x, const_reference y) const {
        bool operator()(pair<const key_type&, const mapped_type&> x, pair<const key_type&, const mapped_type&> y) const {
          return comp(x.first, y.first);
        }
    };

    // ...
  };
}

5.3. [flat.set]

Modify [flat.set.overview]/7 as follows:

Any sequence container ([sequence.reqmts]) supporting Cpp17RandomAccessIterator , or vector<bool> ([vector.bool]), can be used to instantiate flat_set. In particular, vector ([vector]) , vector<bool>, and deque ([deque]) can be used.

[Note 3: vector<bool> is not a sequence container. While vector<bool> is not a sequence container, it provides the necessary interface and proxy iterators to be supported here. — end note]

Modify [flat.set.defn] as follows:

namespace std {
  template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
  class flat_set {
  public:
    // types
    using key_type                = Key;
    using value_type              = Key;
    using key_compare             = Compare;
    using value_compare           = Compare;
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using reference              = iter_reference_t<typename KeyContainer::iterator>;
    using const_reference        = iter_reference_t<typename KeyContainer::const_iterator>;
    using size_type               = typename KeyContainer::size_type;
    using difference_type         = typename KeyContainer::difference_type;
    using iterator                = implementation-defined;     // see [container.requirements]
    using const_iterator          = iterator;
    using reverse_iterator        = std::reverse_iterator<iterator>;
    using const_reverse_iterator  = std::reverse_iterator<const_iterator>;
    using container_type          = KeyContainer;
    // ...
  };
}

5.4. [flat.multiset]

Modify [flat.multiset.overview]/7 as follows:

Any sequence container ([sequence.reqmts]) supporting Cpp17RandomAccessIterator , or vector<bool> ([vector.bool]), can be used to instantiate flat_multiset. In particular, vector ([vector]) , vector<bool>, and deque ([deque]) can be used.

[Note 3: vector<bool> is not a sequence container. While vector<bool> is not a sequence container, it provides the necessary interface and proxy iterators to be supported here. — end note]

Modify [flat.multiset.defn] as follows:

namespace std {
  template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>>
  class flat_multiset {
  public:
    // types
    using key_type                = Key;
    using value_type              = Key;
    using key_compare             = Compare;
    using value_compare           = Compare;
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using reference              = iter_reference_t<typename KeyContainer::iterator>;
    using const_reference        = iter_reference_t<typename KeyContainer::const_iterator>;
    using size_type               = typename KeyContainer::size_type;
    using difference_type         = typename KeyContainer::difference_type;
    using iterator                = implementation-defined;     // see [container.requirements]
    using const_iterator          = iterator;
    using reverse_iterator        = std::reverse_iterator<iterator>;
    using const_reverse_iterator  = std::reverse_iterator<const_iterator>;
    using container_type          = KeyContainer;
    // ...
  };
}

6. Implementation Experience

The proposed wording has been implemented in libc++ on the flatbool branch in github.com/aryann/llvm-project. The existing flat adaptors test suite passes against it. A new bool.pass.cpp test for each of the four flat adaptors exercises vector<bool> as an underlying container.

7. Acknowledgements

Thanks to Arthur O’Dwyer, whose std-proposals post outlined the implementation approach this paper builds on.