P2767R0: flat_map/flat

1. Changelog

R0 (pre-Varna 2023):
- Initial draft.

2. Introduction

Arthur has implemented all of [P0429] flat_map and [P1222] flat_set for libc++. As he implemented them, he and Louis Dionne collected issues that libc++ would like to see resolved by LWG. This paper presents all of these issues together in one place, along with Arthur’s proposed solutions for each one.

Some of the proposed solutions are LEWG-level design changes. Contrariwise, some of the issues collected here don’t have "solutions" at all, but are recorded merely For Your Information (for other vendors/implementors) to document the design choices libc++ has made.

Arthur also proposes a major editorial change to the presentation order of [flat.foo.cons], to collect the allocator-extended constructors in one place, consistent with [priqueue.cons.alloc], [queue.cons.alloc], and [stack.cons.alloc].

3. Editorial introduction of [flat.foo.cons.alloc]

This editorial change was originally submitted as #5923 (October 2022). It bit-rotted after the resolutions of LWG 3802/3803. Here is a clean rebased copy, with easier-to-review formatting.

This wording trivially merge-conflicts with the resolution of [LWG3884] (which adds new allocator-extended constructors). I’m happy to rebase LWG3884 on top of this, or vice versa.

The only changes happening in this part, and their rationales, are:

Move all of the allocator-extended constructors down to the end of [flat.foo.cons].
- Ease of reading.
- Consistency with priority_queue, queue, stack.
Introduce a new subsection, [flat.foo.cons.alloc], to hold just those constructors.
- Consistency with [priqueue.cons.alloc], [queue.cons.alloc], [stack.cons.alloc].
Rename the template parameter Allocator to Alloc, in every case.
- Consistency with priority_queue, queue, stack; all of which use the name Alloc.
- This parameter could be an allocator (e.g. std::pmr::polymorphic_allocator<int>, or it could be a non-allocator (e.g. std::pmr::memory_resource*) which is nevertheless convertible to an allocator type. The uses_allocator_v constraint makes this work.
- No blanket wording is activated nor deactivated by this name change.

Text is marked as ~~deleted~~ , inserted , or moved moved .

3.1. [flat.map]

Change [flat.map.defn] as follows:

24.6.9.2 Definition [flat.map.defn]

[...]
    struct containers {
      key_container_type keys;
      mapped_container_type values;
    };

    // [flat.map.cons], construct/copy/destroy constructors
    flat_map() : flat_map(key_compare()) { }

    flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
             const key_compare& comp = key_compare());
    template<class Allocator>
      flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
               const Allocator& a);
    template<class Allocator>
      flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
               const key_compare& comp, const Allocator& a);

    flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
             const key_compare& comp = key_compare());
    template<class Allocator>
      flat_map(sorted_unique_t, const key_container_type& key_cont,
               const mapped_container_type& mapped_cont, const Allocator& a);
    template<class Allocator>
      flat_map(sorted_unique_t, const key_container_type& key_cont,
               const mapped_container_type& mapped_cont,
               const key_compare& comp, const Allocator& a);

    explicit flat_map(const key_compare& comp)
      : c(), compare(comp) { }
    template<class Allocator>
      flat_map(const key_compare& comp, const Allocator& a);
    template<class Allocator>
      explicit flat_map(const Allocator& a);

    template<class InputIterator>
      flat_map(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
        : c(), compare(comp) { insert(first, last); }
    template<class InputIterator, class Allocator>
      flat_map(InputIterator first, InputIterator last,
               const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_map(InputIterator first, InputIterator last, const Allocator& a);

    template<container-compatible-range<value_type> R>
      flat_map(from_range_t fr, R&& rg)
        : flat_map(fr, std::forward<R>(rg), key_compare()) { }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_map(from_range_t, R&& rg, const Allocator& a);
    template<container-compatible-range<value_type> R>
      flat_map(from_range_t, R&& rg, const key_compare& comp)
        : flat_map(comp) { insert_range(std::forward<R>(rg)); }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);

    template<class InputIterator>
      flat_map(sorted_unique_t s, InputIterator first, InputIterator last,
               const key_compare& comp = key_compare())
        : c(), compare(comp) { insert(s, first, last); }
    template<class InputIterator, class Allocator>
      flat_map(sorted_unique_t, InputIterator first, InputIterator last,
               const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);

    flat_map(initializer_list<value_type> il, const key_compare& comp = key_compare())
        : flat_map(il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_map(initializer_list<value_type> il, const Allocator& a);

    flat_map(sorted_unique_t s, initializer_list<value_type> il,
             const key_compare& comp = key_compare())
        : flat_map(s, il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_map(sorted_unique_t, initializer_list<value_type> il,
               const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);

    // [flat.map.cons.alloc], constructors with allocators

    template<class Alloc>
      flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
               const Alloc& a);  
    template<class Alloc>
      flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
               const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_map(sorted_unique_t, const key_container_type& key_cont,
               const mapped_container_type& mapped_cont, const Alloc& a);
    template<class Alloc>
      flat_map(sorted_unique_t, const key_container_type& key_cont,
               const mapped_container_type& mapped_cont,
               const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_map(const key_compare& comp, const Alloc& a);
    template<class Alloc>
      explicit flat_map(const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_map(InputIterator first, InputIterator last,
               const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_map(InputIterator first, InputIterator last, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_map(from_range_t, R&& rg, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_map(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_map(sorted_unique_t, InputIterator first, InputIterator last,
               const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
    template<class Alloc>
      flat_map(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_map(initializer_list<value_type> il, const Alloc& a);
    template<class Alloc>
      flat_map(sorted_unique_t, initializer_list<value_type> il,
               const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_map(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);

    flat_map& operator=(initializer_list<value_type> il);

    // iterators
[...]

24.6.9.3 Constructors [flat.map.cons]

flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
         const key_compare& comp = key_compare());

1․ Effects: Initializes c.keys with std::move(key_cont), c.values with std::move(mapped_cont), and compare with comp; sorts the range [begin(), end()) with respect to value_comp(); and finally erases the duplicate elements as if by:

auto zv = ranges::zip_view(c.keys, c.values);
auto it = ranges::unique(zv, key_equiv(compare)).begin();
auto dist = distance(zv.begin(), it);
c.keys.erase(c.keys.begin() + dist, c.keys.end());
c.values.erase(c.values.begin() + dist, c.values.end());

2․ Complexity: Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.

template<class Allocator>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const Allocator& a);
template<class Allocator>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const key_compare& comp, const Allocator& a);

~~3․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

4․ Effects: Equivalent to flat_map(key_cont, mapped_cont) and flat_map(key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

5․ Complexity: Same as flat_map(key_cont, mapped_cont) and flat_map(key_cont, mapped_cont, comp), respectively.

flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
         const key_compare& comp = key_compare());

6․ Effects: Initializes c.keys with std::move(key_cont), c.values with std::move(mapped_cont), and compare with comp.

7․ Complexity: Constant.

24.6.9.x Constructors with allocators [flat.map.cons.alloc]

x․ The constructors in this subclause shall not participate in overload resolution unless uses_allocator_v<key_container_type, Alloc> is true and uses_allocator_v<mapped_container_type, Alloc> is true.

template<class Alloc>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);

5․ Complexity: Same as flat_map(key_cont, mapped_cont) and flat_map(key_cont, mapped_cont, comp), respectively.

template<class Allocator>
  flat_map(sorted_unique_t s, const key_container_type& key_cont,
           const mapped_container_type& mapped_cont, const Allocator& a);
template<class Allocator>
  flat_map(sorted_unique_t s, const key_container_type& key_cont,
           const mapped_container_type& mapped_cont, const key_compare& comp,
           const Allocator& a);

~~8․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

9․ Effects: Equivalent to flat_map(s, key_cont, mapped_cont) and flat_map(s, key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

10․ Complexity: Linear.

template<class Allocator>
  flat_map(const key_compare& comp, const Allocator& a);
template<class Allocator>
  explicit flat_map(const Allocator& a);
template<class InputIterator, class Allocator>
  flat_map(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_map(InputIterator first, InputIterator last, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_map(from_range_t, R&& rg, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_map(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_map(sorted_unique_t, InputIterator first, InputIterator last,
           const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
template<class Allocator>
  flat_map(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_map(initializer_list<value_type> il, const Allocator& a);
template<class Allocator>
  flat_map(sorted_unique_t, initializer_list<value_type> il,
           const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_map(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);

~~11․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

12․ Effects: Equivalent to the corresponding non-allocator constructors except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

3.2. [flat.multimap]

Change [flat.multimap.defn] as follows:

24.6.10.2 Definition [flat.multimap.defn]

[...]
    struct containers {
      key_container_type keys;
      mapped_container_type values;
    };

    // [flat.multimap.cons], construct/copy/destroy constructors
    flat_multimap() : flat_multimap(key_compare()) { }

    flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
                  const key_compare& comp = key_compare());
    template<class Allocator>
      flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                    const Allocator& a);
    template<class Allocator>
      flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                    const key_compare& comp, const Allocator& a);

    flat_multimap(sorted_equivalent_t,
                  key_container_type key_cont, mapped_container_type mapped_cont,
                  const key_compare& comp = key_compare());
    template<class Allocator>
      flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                    const mapped_container_type& mapped_cont, const Allocator& a);
    template<class Allocator>
      flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                    const mapped_container_type& mapped_cont,
                    const key_compare& comp, const Allocator& a);

    explicit flat_multimap(const key_compare& comp)
      : c(), compare(comp) { }
    template<class Allocator>
      flat_multimap(const key_compare& comp, const Allocator& a);
    template<class Allocator>
      explicit flat_multimap(const Allocator& a);

    template<class InputIterator>
      flat_multimap(InputIterator first, InputIterator last,
                    const key_compare& comp = key_compare())
        : c(), compare(comp)
        { insert(first, last); }
    template<class InputIterator, class Allocator>
      flat_multimap(InputIterator first, InputIterator last,
                    const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_multimap(InputIterator first, InputIterator last, const Allocator& a);

    template<container-compatible-range<value_type> R>
      flat_multimap(from_range_t fr, R&& rg)
        : flat_multimap(fr, std::forward<R>(rg), key_compare()) { }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_multimap(from_range_t, R&& rg, const Allocator& a);
    template<container-compatible-range<value_type> R>
      flat_multimap(from_range_t, R&& rg, const key_compare& comp)
        : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);

    template<class InputIterator>
      flat_multimap(sorted_equivalent_t s, InputIterator first, InputIterator last,
                    const key_compare& comp = key_compare())
        : c(), compare(comp) { insert(s, first, last); }
    template<class InputIterator, class Allocator>
      flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const Allocator& a);

    flat_multimap(initializer_list<value_type> il, const key_compare& comp = key_compare())
        : flat_multimap(il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_multimap(initializer_list<value_type> il, const key_compare& comp,
                    const Allocator& a);
    template<class Allocator>
      flat_multimap(initializer_list<value_type> il, const Allocator& a);

    flat_multimap(sorted_equivalent_t s, initializer_list<value_type> il,
                  const key_compare& comp = key_compare())
        : flat_multimap(s, il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
                    const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);

    // [flat.multimap.cons.alloc], constructors with allocators

    template<class Alloc>
      flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                    const Alloc& a);
    template<class Alloc>
      flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                    const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                    const mapped_container_type& mapped_cont, const Alloc& a);
    template<class Alloc>
      flat_multimap(sorted_equivalent_t, const key_container_type& key_cont,
                    const mapped_container_type& mapped_cont,
                    const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multimap(const key_compare& comp, const Alloc& a);
    template<class Alloc>
      explicit flat_multimap(const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multimap(InputIterator first, InputIterator last,
                    const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multimap(InputIterator first, InputIterator last, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_multimap(from_range_t, R&& rg, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const Alloc& a);
    template<class Alloc>
      flat_multimap(initializer_list<value_type> il, const key_compare& comp,
                    const Alloc& a);
    template<class Alloc>
      flat_multimap(initializer_list<value_type> il, const Alloc& a);
    template<class Alloc>
      flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
                    const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);

    flat_multimap& operator=(initializer_list<value_type> il);

    // iterators
[...]

24.6.10.3 Constructors [flat.multimap.cons]

flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
              const key_compare& comp = key_compare());

2․ Complexity: Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.

template<class Allocator>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                const Allocator& a);
template<class Allocator>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                const key_compare& comp, const Allocator& a);

~~3․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

4․ Effects: Equivalent to flat_multimap(key_cont, mapped_cont) and flat_multimap(key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

5․ Complexity: Same as flat_multimap(key_cont, mapped_cont) and flat_multimap(key_cont, mapped_cont, comp), respectively.

flat_multimap(sorted_equivalent_t, key_container_type key_cont, mapped_container_type mapped_cont,
              const key_compare& comp = key_compare());

6․ Effects: Initializes c.keys with std::move(key_cont), c.values with std::move(mapped_cont), and compare with comp.

7․ Complexity: Constant.

24.6.10.x Constructors with allocators [flat.multimap.cons.alloc]

template<class Alloc>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);

5․ Complexity: Same as flat_multimap(key_cont, mapped_cont) and flat_multimap(key_cont, mapped_cont, comp), respectively.

template<class Allocator>
  flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
                const mapped_container_type& mapped_cont, const Allocator& a);
template<class Allocator>
  flat_multimap(sorted_equivalent_t s, const key_container_type& key_cont,
                const mapped_container_type& mapped_cont, const key_compare& comp,
                const Allocator& a);

~~8․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

9․ Effects: Equivalent to flat_multimap(s, key_cont, mapped_cont) and flat_multimap(s, key_cont, mapped_cont, comp), respectively, except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

10․ Complexity: Linear.

template<class Allocator>
  flat_multimap(const key_compare& comp, const Allocator& a);
template<class Allocator>
  explicit flat_multimap(const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multimap(InputIterator first, InputIterator last, const key_compare& comp,
                const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multimap(InputIterator first, InputIterator last, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_multimap(from_range_t, R&& rg, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_multimap(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multimap(sorted_equivalent_t, InputIterator first, InputIterator last,
                const Allocator& a);
template<class Allocator>
  flat_multimap(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_multimap(initializer_list<value_type> il, const Allocator& a);
template<class Allocator>
  flat_multimap(sorted_equivalent_t, initializer_list<value_type> il,
                const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_multimap(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);

~~11․ Constraints: uses_allocator_v<key_container_type, Allocator> is true and uses_allocator_v<mapped_container_type, Allocator> is true.~~

12․ Effects: Equivalent to the corresponding non-allocator constructors except that c.keys and c.values are constructed with uses-allocator construction ([allocator.uses.construction]).

3.3. [flat.multiset]

Change [flat.multiset.defn] as follows:

24.6.12.2 Definition [flat.multiset.defn]

[...]
using container_type            = KeyContainer;

    // [flat.multiset.cons], constructors
    flat_multiset() : flat_multiset(key_compare()) { }

    explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
    template<class Allocator>
      flat_multiset(const container_type& cont, const Allocator& a);
    template<class Allocator>
      flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);

    flat_multiset(sorted_equivalent_t, container_type cont,
                  const key_compare& comp = key_compare())
      : c(std::move(cont)), compare(comp) { }
    template<class Allocator>
      flat_multiset(sorted_equivalent_t, const container_type&, const Allocator& a);
    template<class Allocator>
      flat_multiset(sorted_equivalent_t, const container_type& cont,
                    const key_compare& comp, const Allocator& a);

    explicit flat_multiset(const key_compare& comp)
      : c(), compare(comp) { }
    template<class Allocator>
      flat_multiset(const key_compare& comp, const Allocator& a);
    template<class Allocator>
      explicit flat_multiset(const Allocator& a);

    template<class InputIterator>
      flat_multiset(InputIterator first, InputIterator last,
                    const key_compare& comp = key_compare())
        : c(), compare(comp)
        { insert(first, last); }
    template<class InputIterator, class Allocator>
      flat_multiset(InputIterator first, InputIterator last,
                    const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_multiset(InputIterator first, InputIterator last, const Allocator& a);

    template<container-compatible-range<value_type> R>
      flat_multiset(from_range_t fr, R&& rg)
        : flat_multiset(fr, std::forward<R>(rg), key_compare()) { }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_multiset(from_range_t, R&& rg, const Allocator& a);
    template<container-compatible-range<value_type> R>
      flat_multiset(from_range_t, R&& rg, const key_compare& comp)
        : flat_multiset(comp)
        { insert_range(std::forward<R>(rg)); }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);

    template<class InputIterator>
      flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const key_compare& comp = key_compare())
        : c(first, last), compare(comp) { }
    template<class InputIterator, class Allocator>
      flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const Allocator& a);

    flat_multiset(initializer_list<value_type> il, const key_compare& comp = key_compare())
      : flat_multiset(il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_multiset(initializer_list<value_type> il, const key_compare& comp,
                    const Allocator& a);
    template<class Allocator>
      flat_multiset(initializer_list<value_type> il, const Allocator& a);

    flat_multiset(sorted_equivalent_t s, initializer_list<value_type> il,
                  const key_compare& comp = key_compare())
        : flat_multiset(s, il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
                    const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);

    // [flat.multiset.cons.alloc], constructors with allocators

    template<class Alloc>
      flat_multiset(const container_type& cont, const Alloc& a);
    template<class Alloc>
      flat_multiset(const container_type& cont, const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multiset(sorted_equivalent_t, const container_type&, const Alloc& a);
    template<class Alloc>
      flat_multiset(sorted_equivalent_t, const container_type& cont,
                    const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multiset(const key_compare& comp, const Alloc& a);
    template<class Alloc>
      explicit flat_multiset(const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multiset(InputIterator first, InputIterator last,
                    const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multiset(InputIterator first, InputIterator last, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_multiset(from_range_t, R&& rg, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                    const Alloc& a);
    template<class Alloc>
      flat_multiset(initializer_list<value_type> il, const key_compare& comp,
                    const Alloc& a);
    template<class Alloc>
      flat_multiset(initializer_list<value_type> il, const Alloc& a);
    template<class Alloc>
      flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
                    const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Alloc& a);

    flat_multiset& operator=(initializer_list<value_type>);

    // iterators
[...]

24.6.12.3 Constructors [flat.multiset.cons]

explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());

1․ Effects: Initializes c with std::move(cont) and compare with comp, and sorts the range [begin(), end()) with respect to compare.

2․ Complexity: Linear in N if cont is already sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.

24.6.12.x Constructors with allocators [flat.multiset.cons.alloc]

x․ The constructors in this subclause shall not participate in overload resolution unless uses_allocator_v<container_type, Alloc> is true.

template<class Allocator>
  flat_multiset(const container_type& cont, const Allocator& a);
template<class Allocator>
  flat_multiset(const container_type& cont, const key_compare& comp, const Allocator& a);

~~3․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

4․ Effects: Equivalent to flat_multiset(cont) and flat_multiset(cont, comp), respectively, except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

5․ Complexity: Same as flat_multiset(cont) and flat_multiset(cont, comp), respectively.

template<class Allocator>
  flat_multiset(sorted_equivalent_t s, const container_type& cont, const Allocator& a);
template<class Allocator>
  flat_multiset(sorted_equivalent_t s, const container_type& cont,
                const key_compare& comp, const Allocator& a);

~~6․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

7․ Effects: Equivalent to flat_multiset(s, cont) and flat_multiset(s, cont, comp), respectively, except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

8․ Complexity: Linear.

template<class Allocator>
  flat_multiset(const key_compare& comp, const Allocator& a);
template<class Allocator>
  explicit flat_multiset(const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multiset(InputIterator first, InputIterator last,
                const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multiset(InputIterator first, InputIterator last, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_multiset(from_range_t, R&& rg, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_multiset(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last, const Allocator& a);
template<class Allocator>
  flat_multiset(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_multiset(initializer_list<value_type> il, const Allocator& a);
template<class Allocator>
  flat_multiset(sorted_equivalent_t, initializer_list<value_type> il,
                const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_multiset(sorted_equivalent_t, initializer_list<value_type> il, const Allocator& a);

~~9․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

10․ Effects: Equivalent to the corresponding non-allocator constructors except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

3.4. [flat.set]

Change [flat.set.defn] as follows:

24.6.11.2 Definition [flat.set.defn]

[...]
    using container_type            = KeyContainer;

    // [flat.set.cons], constructors
    flat_set() : flat_set(key_compare()) { }

    explicit flat_set(container_type cont, const key_compare& comp = key_compare());
    template<class Allocator>
      flat_set(const container_type& cont, const Allocator& a);
    template<class Allocator>
      flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);

    flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare())
      : c(std::move(cont)), compare(comp) { }
    template<class Allocator>
      flat_set(sorted_unique_t, const container_type& cont, const Allocator& a);
    template<class Allocator>
      flat_set(sorted_unique_t, const container_type& cont,
               const key_compare& comp, const Allocator& a);

    explicit flat_set(const key_compare& comp)
      : c(), compare(comp) { }
    template<class Allocator>
      flat_set(const key_compare& comp, const Allocator& a);
    template<class Allocator>
      explicit flat_set(const Allocator& a);

    template<class InputIterator>
      flat_set(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
        : c(), compare(comp)
        { insert(first, last); }
    template<class InputIterator, class Allocator>
      flat_set(InputIterator first, InputIterator last,
               const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_set(InputIterator first, InputIterator last, const Allocator& a);

    template<container-compatible-range<value_type> R>
      flat_set(from_range_t fr, R&& rg)
        : flat_set(fr, std::forward<R>(rg), key_compare()) { }
    template<container-compatible-range<value_type> R, class Allocator>
      flat_set(from_range_t, R&& rg, const Allocator& a);
    template<container-compatible-range<value_type> R>
      flat_set(from_range_t, R&& rg, const key_compare& comp)
        : flat_set(comp)
        { insert_range(std::forward<R>(rg)); }
    template<container-compatible-range<value_type> R, class Allocator>
       flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);

    template<class InputIterator>
      flat_set(sorted_unique_t, InputIterator first, InputIterator last,
               const key_compare& comp = key_compare())
        : c(first, last), compare(comp) { }
    template<class InputIterator, class Allocator>
      flat_set(sorted_unique_t, InputIterator first, InputIterator last,
               const key_compare& comp, const Allocator& a);
    template<class InputIterator, class Allocator>
      flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);

    flat_set(initializer_list<value_type> il, const key_compare& comp = key_compare())
        : flat_set(il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_set(initializer_list<value_type> il, const Allocator& a);

    flat_set(sorted_unique_t s, initializer_list<value_type> il,
             const key_compare& comp = key_compare())
        : flat_set(s, il.begin(), il.end(), comp) { }
    template<class Allocator>
      flat_set(sorted_unique_t, initializer_list<value_type> il,
               const key_compare& comp, const Allocator& a);
    template<class Allocator>
      flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);

    // [flat.set.cons.alloc], constructors with allocators

    template<class Alloc>
      flat_set(const container_type& cont, const Alloc& a);
    template<class Alloc>
      flat_set(const container_type& cont, const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_set(sorted_unique_t, const container_type& cont, const Alloc& a);
    template<class Alloc>
      flat_set(sorted_unique_t, const container_type& cont,
               const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_set(const key_compare& comp, const Alloc& a);
    template<class Alloc>
      explicit flat_set(const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_set(InputIterator first, InputIterator last,
               const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_set(InputIterator first, InputIterator last, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
      flat_set(from_range_t, R&& rg, const Alloc& a);
    template<container-compatible-range<value_type> R, class Alloc>
       flat_set(from_range_t, R&& rg, const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_set(sorted_unique_t, InputIterator first, InputIterator last,
               const key_compare& comp, const Alloc& a);
    template<class InputIterator, class Alloc>
      flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Alloc& a);
    template<class Alloc>
      flat_set(initializer_list<value_type> il, const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_set(initializer_list<value_type> il, const Alloc& a);
    template<class Alloc>
      flat_set(sorted_unique_t, initializer_list<value_type> il,
               const key_compare& comp, const Alloc& a);
    template<class Alloc>
      flat_set(sorted_unique_t, initializer_list<value_type> il, const Alloc& a);

    flat_set& operator=(initializer_list<value_type>);

    // iterators
[...]

24.6.11.3 Constructors [flat.set.cons]

explicit flat_set(container_type cont, const key_compare& comp = key_compare());

1․ Effects: Initializes c with std::move(cont) and compare with comp, sorts the range [begin(), end()) with respect to compare, and finally erases all but the first element from each group of consecutive equivalent elements.

2․ Complexity: Linear in N if cont is already sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.

24.6.11.x Constructors with allocators [flat.set.cons.alloc]

x․ The constructors in this subclause shall not participate in overload resolution unless uses_allocator_v<container_type, Alloc> is true.

template<class Allocator>
  flat_set(const container_type& cont, const Allocator& a);
template<class Allocator>
  flat_set(const container_type& cont, const key_compare& comp, const Allocator& a);

~~3․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

4․ Effects: Equivalent to flat_set(cont) and flat_set(cont, comp), respectively, except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

5․ Complexity: Same as flat_set(cont) and flat_set(cont, comp), respectively.

template<class Allocator>
  flat_set(sorted_unique_t s, const container_type& cont, const Allocator& a);
template<class Allocator>
  flat_set(sorted_unique_t s, const container_type& cont,
           const key_compare& comp, const Allocator& a);

~~6․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

7․ Effects: Equivalent to flat_set(s, cont) and flat_set(s, cont, comp), respectively, except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

8․ Complexity: Linear.

template<class Allocator>
  flat_set(const key_compare& comp, const Allocator& a);
template<class Allocator>
  explicit flat_set(const Allocator& a);
template<class InputIterator, class Allocator>
  flat_set(InputIterator first, InputIterator last, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_set(InputIterator first, InputIterator last, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_set(from_range_t, R&& rg, const Allocator& a);
template<container-compatible-range<value_type> R, class Allocator>
  flat_set(from_range_t, R&& rg, const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_set(sorted_unique_t, InputIterator first, InputIterator last,
           const key_compare& comp, const Allocator& a);
template<class InputIterator, class Allocator>
  flat_set(sorted_unique_t, InputIterator first, InputIterator last, const Allocator& a);
template<class Allocator>
  flat_set(initializer_list<value_type> il, const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_set(initializer_list<value_type> il, const Allocator& a);
template<class Allocator>
  flat_set(sorted_unique_t, initializer_list<value_type> il,
           const key_compare& comp, const Allocator& a);
template<class Allocator>
  flat_set(sorted_unique_t, initializer_list<value_type> il, const Allocator& a);

~~9․ Constraints: uses_allocator_v<container_type, Allocator> is true.~~

10․ Effects: Equivalent to the corresponding non-allocator constructors except that c is constructed with uses-allocator construction ([allocator.uses.construction]).

4. Accidentally explicit constructor

STL style is that multi-argument constructors should be non-explicit; see [P1163]. This change is non-editorial, but should be non-controversial, unless anyone objects to the delegating constructor’s doing an extra move of cont. In practice, libc++ doesn’t actually move cont twice; we consider the delegating constructor merely a tool to shorten the spec.

std::vector<int> v;
std::flat_set s = { v, std::less(), std::allocator<int>() };
  // OK
std::flat_set s = { v, std::less() };
  // Before: Ill-formed
  // After: OK

4.1. Wording

Change [flat.multiset.defn] as follows:

// [flat.multiset.cons], constructors
flat_multiset() : flat_multiset(key_compare()) { }

explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
explicit flat_multiset(container_type cont)
  : flat_multiset(std::move(cont), key_compare()) { }
flat_multiset(container_type cont, const key_compare& comp);

Change [flat.multiset.cons] as follows:

explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());

Change [flat.set.defn] as follows:

// [flat.set.cons], constructors
flat_set() : flat_set(key_compare()) { }

explicit flat_set(container_type cont, const key_compare& comp = key_compare());
explicit flat_set(container_type cont)
  : flat_set(std::move(cont), key_compare()) { }
flat_set(container_type cont, const key_compare& comp);

Change [flat.set.cons] as follows:

explicit flat_set(container_type cont, const key_compare& comp = key_compare());

5. Add move semantics to `flat_set::insert_range`

std::flat_set<std::string> fs1;
std::vector<std::string> v1 = {"hello", "world"};
fs1.insert_range(std::views::as_rvalue(v1));
  // Before: Copies the strings.
  // After: Moves the strings.

std::flat_set<std::unique_ptr<int>> fs2;
std::vector<std::unique_ptr<int>> v2;
fs2.insert_range(std::views::as_rvalue(v2));
  // Before: Ill-formed.
  // After: Moves the unique_ptrs.

5.1. Wording

Change [flat.set.modifiers]/10 as follows:

template<container-compatible-range<value_type> R> void insert_range(R&& rg);

10․ Effects: Adds elements to c as if by:

for (~~const auto&~~ auto&& e : rg) { c.insert(c.end(), std::forward<decltype(e)>(e)); }
Then, sorts the range of newly inserted elements with respect to compare; merges the resulting sorted range and the sorted range of pre-existing elements into a single sorted range; and finally erases all but the first element from each group of consecutive equivalent elements.

11․ Complexity: N + M log M, where N is size() before the operation and M is ranges::distance(rg).

12․ Remarks: Since this operation performs an in-place merge, it may allocate memory.

Add a new section to [flat.multiset.modifiers] explaining the semantics of flat_multiset::insert_range.

template<container-compatible-range<value_type> R> void insert_range(R&& rg);

x․ Effects: Adds elements to c as if by:
for (auto&& e : rg) { c.insert(c.end(), std::forward<decltype(e)>(e)); }
Then, sorts the range of newly inserted elements with respect to compare, and merges the resulting sorted range and the sorted range of pre-existing elements into a single sorted range.
x․ Complexity: N + M log M, where N is size() before the operation and M is ranges::distance(rg).
x․ Remarks: Since this operation performs an in-place merge, it may allocate memory.

6. Add move semantics to `flat_map::insert_range`

flat_map's insert_range has the same issue as flat_set's, at least on paper.

std::flat_map<int, std::unique_ptr<int>> fs2;
std::vector<std::pair<int, std::unique_ptr<int>>> v2;
fs2.insert_range(std::views::as_rvalue(v2));
  // Before: Ill-formed.
  // After: Moves the unique_ptrs.

However, libc++'s implementation of flat_map and flat_multimap didn’t need to change — we already "accidentally" support move semantics in the maps' insert_range methods, because we factor out a helper method __append_pairs that is used by all three of insert(first, last), insert(sorted_unique, first, last), and insert_range(rg). It looks very similar to the specification proposed below.

The current specification says:

for (const auto& e : rg) {
  c.keys.insert(c.keys.end(), e.first);
  c.values.insert(c.values.end(), e.second);
}

The insert_range method is constrained on container-compatible-range<value_type>, i.e. convertible_to<range_reference_t<R>, value_type>. But in fact the current spec’s algorithm never attempts to convert range_reference_t<R> to value_type. Instead, it implicitly requires that range_reference_t<R>::first be convertible to key_type and range_reference_t<R>::second be convertible to mapped_type. If range_reference_t<R> is something without first and second members, the current spec doesn’t work at all.

std::pair<int, int> p1 = {1,2};
std::reference_wrapper<std::pair<int, int>> a[] = { p1 };
std::flat_map<int, int> fm;
fm.insert_range(a);
  // Before: Ill-formed: reference_wrapper has no .first member
  // After: OK

6.1. Wording

We don’t need to touch [flat.multimap.modifiers]; in fact it does not currently exist; because of [flat.multimap.overview]/4:

4․ Except as otherwise noted, operations on flat_multimap are equivalent to those of flat_map, except that flat_multimap operations do not remove or replace elements with equal keys.

Change [flat.map.modifiers]/12 as follows:

template<container-compatible-range<value_type> R> void insert_range(R&& rg);

12․ Effects: Adds elements to c as if by:

for (~~const auto&~~ value_type e : rg) { c.keys.insert(c.keys.end(), std::move(e.first)); c.values.insert(c.values.end(), std::move(e.second)); }
Then, sorts the range of newly inserted elements with respect to value_comp(); merges the resulting sorted range and the sorted range of pre-existing elements into a single sorted range; and finally erases the duplicate elements as if by:

auto zv = ~~ranges::zip_view~~ views::zip(c.keys, c.values); auto it = ranges::unique(zv, key_equiv(compare)).begin(); auto dist = distance(zv.begin(), it); c.keys.erase(c.keys.begin() + dist, c.keys.end()); c.values.erase(c.values.begin() + dist, c.values.end());

13․ Complexity: N + M log M, where N is size() before the operation and M is ranges::distance(rg).

14․ Remarks: Since this operation performs an in-place merge, it may allocate memory.

7. `insert` is more primitive than `emplace`

std::pmr::set_default_resource(std::pmr::null_memory_resource());
std::pmr::monotonic_buffer_resource mr(1’000’000);

auto fm = PmrFlatSet<std::pmr::string>(&mr);
std::pmr::string ps("too long to fit in the small string buffer", &mr);
fm.insert(ps);
  // Before: runtime abort, cannot default-allocate t
  // After: OK

Whenever we insert or emplace into a set or multiset, we have two tasks:

Construct the new value_type object.
Find the correct insertion point for the new object.

emplace receives a bag of constructor arguments, so it has no choice: it must do "construct t, find insertion point for t, move-insert t into the container" exactly as specified above.

But insert receives an already-constructed value_type! It shouldn’t discard that valuable information; it should use the given value_type to find the appropriate insertion point, and then construct the new object directly in place. There is no reason to construct t on the stack first.

7.1. Heterogeneous `multiset::insert`

[P2363] explains why the node-based multiset still lacks a heterogeneous insert(K&&):

Adding heterogeneous insert overload makes no sense for associative containers with non-unique keys (std::multimap, std::multiset, std::unordered_multimap and std::unordered_multiset) because the insertion will be successful in any case and the key would be always constructed. All additional overheads introduced by insert can be mitigated by using emplace.

For flat_multiset, the last sentence is false; generic emplace is unusable for PMR allocators, because it must first construct t using the default allocator. Therefore we also propose to add a heterogeneous-comparison overload of flat_multiset::insert.

template<class T, class C = std::less<T>>
using PmrFlatMultiset = std::flat_multiset<T, C, std::pmr::vector<T>>;
 
std::pmr::monotonic_buffer_resource mr(1’000’000);
std::pmr::set_default_resource(std::pmr::null_memory_resource());
const char s[] = "too long to fit in the small string buffer";

auto m = std::pmr::multiset<std::pmr::string>(&mr);
m.emplace(s); // OK
m.insert(s); // runtime abort, cannot default-allocate x

auto fm = PmrFlatMultiset<std::pmr::string>(&mr);
fm.emplace(s); // runtime abort, cannot default-allocate t
fm.insert(s); // runtime abort, cannot default-allocate x

auto m2 = std::pmr::multiset<std::pmr::string, std::less<>>(&mr);
m2.emplace(s); // OK
m2.insert(s); // runtime abort, cannot default-allocate x

auto fm2 = PmrFlatMultiset<std::pmr::string, std::less<>>(&mr);
fm2.emplace(s); // runtime abort, cannot default-allocate t
fm2.insert(s);
  // Before: runtime abort, cannot default-allocate x
  // After: OK

Notice the asymmetry between fm2.insert(s) and m2.insert(s). Arthur thinks it would be nice to support heterogeneous insert for node-based multiset and unordered_multiset (contra P2363’s reasoning), but that’s out of scope for this particular paper P2767. For P2767’s purposes, we’re satisfied once there exists some way of inserting s into fm2. We don’t mind that the working approaches use different spellings: m2.emplace(s) versus fm2.insert(s).

7.2. "Initializes" phrasing

The proposed wording below changes [flat.map.modifiers]/2 as follows, in line with e.g. [variant.ctor]/21 and [forward.list.modifiers]/23:

2․ Effects: ~~Initializes~~ Direct-non-list-initializes an object t of type pair<key_type, mapped_type> with std::forward<Args>(args)...; if the map already contains an element whose key is equivalent to t.first, *this is unchanged. [...]

However, could we eliminate the jargon entirely by doing something like this instead? As written I don’t think this is proper standardese, but maybe LWG can fix it up:

2․ Effects: ~~Initializes an object t of type pair<key_type, mapped_type> with std::forward<Args>(args)...; if~~ Let t be pair<key_type, mapped_type>(std::forward<Args>(args)...). If the map already contains an element whose key is equivalent to t.first, *this is unchanged. [...]

7.3. Unusual constraints

The usual pattern in [containers] is that x.emplace(args...) has a precondition ([sequence.reqmts], [associative.reqmts.general]) but no Constraints element. That is, emplace is not SFINAE-friendly. And it has only the one overload, so it doesn’t need a constraint for purposes of overload resolution.

No Constraints on emplace: deque, list, vector, containers, associative containers, unordered containers, priority_queue, optional.

Constraints on emplace: flat_map, flat_multiset, any, expected, variant.

I believe a Constraints element was accidentally copy-pasted from the spec of flat_map::insert(P&&) —which does need the constraint because it’s part of insert's large overload set — to flat_map::emplace, and then from there to flat_multiset::emplace. The constraint is already (correctly) absent from flat_set::emplace.

Therefore, the proposed wording for this section simply deletes those Constraints elements.

7.4. Ambiguity with `insert(first, last)`

struct Address {
  const char *p_ = nullptr;
  Address(auto p) : p_((const char*)&*p) {}
  auto operator<=>(const Address&) const = default;
};
std::flat_set<Address> m, n;
m.insert(n.begin(), n.end());
  // Before: Ambiguous with insert(pos, K&&)
  // After: Unambiguously insert(first, last)

We simply need to copy the usual wording "Constraints: For the second overload, is_convertible_v<K&&, const_iterator> and is_convertible_v<K&&, iterator> are both false" from [P2363] or flat_map::try_emplace.

This is a problem only for the sets, where const_iterator can be convertible to value_type. It’s not a problem for the maps, so they don’t need to change.

7.5. Wording

We don’t need to touch [flat.multimap.modifiers]; in fact it does not currently exist; because of [flat.multimap.overview]/4:

4․ Except as otherwise noted, operations on flat_multimap are equivalent to those of flat_map, except that flat_multimap operations do not remove or replace elements with equal keys.

Change [flat.map.defn] as follows:

// [flat.map.modifiers], modifiers
template<class... Args> pair<iterator, bool> emplace(Args&&... args);
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);

pair<iterator, bool> insert(const value_type& x);
  { return emplace(x); }
pair<iterator, bool> insert(value_type&& x);
  { return emplace(std::move(x)); }
iterator insert(const_iterator position, const value_type& x);
  { return emplace_hint(position, x); }
iterator insert(const_iterator position, value_type&& x);
  { return emplace_hint(position, std::move(x)); }

template<class P> pair<iterator, bool> insert(P&& x);
template<class P>
  iterator insert(const_iterator position, P&&);

Change [flat.map.modifiers] as follows:

template<class... Args> pair<iterator, bool> emplace(Args&&... args);
~~1․ Constraints: is_constructible_v<pair<key_type, mapped_type>, Args...> is true.~~
2․ Effects: ~~Initializes~~ Direct-non-list-initializes an object t of type pair<key_type, mapped_type> with std::forward<Args>(args)...; if the map already contains an element whose key is equivalent to t.first, *this is unchanged. Otherwise, equivalent to:
auto key_it = ranges::upper_bound(c.keys, t.first, compare); auto value_it = c.values.begin() + distance(c.keys.begin(), key_it); c.keys.insert(key_it, std::move(t.first)); c.values.insert(value_it, std::move(t.second));

3․ Returns: The bool component of the returned pair is true if and only if the insertion took place, and the iterator component of the pair points to the element with key equivalent to t.first.

pair<iterator, bool> insert(const value_type& x); pair<iterator, bool> insert(value_type&& x);
x․ Effects: If the map already contains an element whose key is equivalent to x.first, *this and x are unchanged. Otherwise, equivalent to:
auto key_it = ranges::upper_bound(c.keys, x.first, compare); auto value_it = c.values.begin() + distance(c.keys.begin(), key_it); c.keys.insert(key_it, x.first); c.values.insert(value_it, x.second);
for the first overload and
auto key_it = ranges::upper_bound(c.keys, x.first, compare); auto value_it = c.values.begin() + distance(c.keys.begin(), key_it); c.keys.insert(key_it, std::move(x.first)); c.values.insert(value_it, std::move(x.second));
for the second overload.
template pair<iterator, bool> insert(P&& x); template iterator insert(const_iterator position, P&& x);
4․ Constraints: is_constructible_v<pair<key_type, mapped_type>, P> is true. For the second overload, is_convertible_v<P&&, const_iterator> and is_convertible_v<P&&, iterator> are both false.

5․ Effects: The first form is equivalent to return emplace(std::forward<P>(x));. The second form is equivalent to return emplace_hint(position, std::forward<P>(x));.

Change [flat.multimap.defn] as follows:

// modifiers
template<class... Args> iterator emplace(Args&&... args);
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);

iterator insert(const value_type& x);
  { return emplace(x); }
iterator insert(value_type&& x);
  { return emplace(std::move(x)); }
iterator insert(const_iterator position, const value_type& x);
  { return emplace_hint(position, x); }
iterator insert(const_iterator position, value_type&& x);
  { return emplace_hint(position, std::move(x)); }

template<class P> iterator insert(P&& x);
template<class P>
  iterator insert(const_iterator position, P&&);

Change [flat.multiset.defn] as follows:

// [flat.multiset.modifiers], modifiers
template<class... Args> iterator emplace(Args&&... args);
  { return insert(value_type(std::forward<Args>(args)...)); }
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);
    { return insert(position, value_type(std::forward<Args>(args)...)); }

iterator insert(const value_type& x);
  { return emplace(x); }
iterator insert(value_type&& x);
  { return emplace(std::move(x)); }
template<class K> iterator insert(K&& x);
iterator insert(const_iterator position, const value_type& x);
  { return emplace_hint(position, x); }
iterator insert(const_iterator position, value_type&& x);
  { return emplace_hint(position, std::move(x)); }
template<class K> iterator insert(const_iterator hint, K&& x);

Change [flat.multiset.modifiers] as follows:

~~template<class... Args> iterator emplace(Args&&... args);~~
~~1․ Constraints: is_constructible_v<value_type, Args...> is true.~~
~~2․ Effects: First, initializes an object t of type value_type with std::forward<Args>(args)..., then inserts t as if by:~~
~~auto it = ranges::upper_bound(c, t, compare);~~ ~~c.insert(it, std::move(t));~~
~~3․ Returns: An iterator that points to the inserted element.~~
iterator insert(const value_type& x); iterator insert(value_type&& x);
x․ Effects: Inserts a new element as if by:
auto it = ranges::upper_bound(c, x, compare); c.insert(it, x);
for the first overload or
auto it = ranges::upper_bound(c, x, compare); c.insert(it, std::move(x));
for the second overload.
x․ Returns: An iterator that points to the inserted element.
template<class K> iterator insert(K&& x); template<class K> iterator insert(const_iterator hint, K&& x);
x․ Constraints: The qualified-id Compare::is_transparent is valid and denotes a type. is_constructible_v<value_type, K> is true. For the second overload, is_convertible_v<K&&, const_iterator> and is_convertible_v<K&&, iterator> are both false.
x․ Preconditions: The conversion from x into value_type constructs an object u for which find(x) == find(u) is true.
x․ Effects: If the set already contains an element equivalent to x, *this and x are unchanged. Otherwise, inserts a new element as if by emplace(std::forward<K>(x)).
x․ Returns: An iterator that points to the inserted element.

Change [flat.set.defn] as follows:

// [flat.set.modifiers], modifiers
template<class... Args> pair<iterator, bool> emplace(Args&&... args);
  { return insert(value_type(std::forward<Args>(args)...)); }
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);
    { return insert(position, value_type(std::forward<Args>(args)...)); }

pair<iterator, bool> insert(const value_type& x);
  { return emplace(x); }
pair<iterator, bool> insert(value_type&& x);
  { return emplace(std::move(x)); }
template<class K> pair<iterator, bool> insert(K&& x);
iterator insert(const_iterator position, const value_type& x);
  { return emplace_hint(position, x); }
iterator insert(const_iterator position, value_type&& x);
  { return emplace_hint(position, std::move(x)); }
template<class K> iterator insert(const_iterator hint, K&& x);

Change [flat.set.modifiers] as follows:

pair<iterator, bool> insert(const value_type& x); pair<iterator, bool> insert(value_type&& x);
x․ Effects: If the set already contains an element equivalent to x, *this and x are unchanged. Otherwise, inserts a new element as if by:
auto it = ranges::upper_bound(c, x, compare); c.insert(it, x);
for the first overload or
auto it = ranges::upper_bound(c, x, compare); c.insert(it, std::move(x));
for the second overload.
x․ Returns: The bool component of the returned pair is true if and only if the insertion took place. The returned iterator points to the element whose key is equivalent to x.
template<class K> pair<iterator, bool> insert(K&& x); template<class K> iterator insert(const_iterator hint, K&& x);
1․ Constraints: The qualified-id Compare::is_transparent is valid and denotes a type. is_constructible_v<value_type, K> is true. For the second overload, is_convertible_v<K&&, const_iterator> and is_convertible_v<K&&, iterator> are both false.

2․ Preconditions: The conversion from x into value_type constructs an object u, for which find(x) == find(u) is true.

3․ Effects: If the set already contains an element equivalent to x, *this and x are unchanged. Otherwise, inserts a new element as if by emplace(std::forward<K>(x)).

4․ Returns: In the first overload, the bool component of the returned pair is true if and only if the insertion took place. The returned iterator points to the element whose key is equivalent to x.

8. `insert_range(sorted_unique, rg)`

The multi-element insertion API consists of these overloads:

insert(first, last);
insert(il);
insert_range(rg);

insert(sorted_unique, first, last);
insert(sorted_unique, il);

An overload of insert_range(sorted_unique, rg) is conspicuously missing.

auto rg = std::views::iota(0, 100) | std::take_while(lessThan50);
assert(!std::ranges::common_range<decltype(rg)>);
assert(std::ranges::is_sorted(rg));

std::flat_set<int> fs;

fs.insert_range(rg);
  // OK, but unnecessarily re-sorts the input

if (auto cv = rg | std::views::common; true) {
  fs.insert(std::sorted_unique, cv.begin(), cv.end());
    // OK, doesn’t re-sort, but arcane
}

fs.insert_range(std::sorted_unique, rg);
  // Before: Ill-formed
  // After: OK

Now, we’re also conspicuously missing a constructor overload flat_set(sorted_unique, from_range, rg). There we have a real API-design conflict: Which of sorted_unique and from_range should come first? This is enough of a reason to simply give up on that constructor. But insert_range has no such API-design problem. We could add this overload easily.

8.1. Wording

Change [flat.map.defn] as follows:

template<class InputIterator>
  void insert(InputIterator first, InputIterator last);
template<class InputIterator>
  void insert(sorted_unique_t, InputIterator first, InputIterator last);
template<container-compatible-range<value_type> R>
  void insert_range(R&& rg);
template<container-compatible-range<value_type> R>
  void insert_range(sorted_unique_t, R&& rg);
void insert(initializer_list<value_type> il)
  { insert(il.begin(), il.end()); }
void insert(sorted_unique_t s, initializer_list<value_type> il)
  { insert(s, il.begin(), il.end()); }

Add a new entry to [flat.map.modifiers] as follows:

template<container-compatible-range<value_type> R> void insert_range(sorted_unique_t, R&& rg);

x․ Effects: Equivalent to insert_range(std::forward<R>(rg)).
x․ Complexity: Linear in N, where N is size() after the operation.

Change [flat.multimap.defn] as follows:

template<class InputIterator>
  void insert(InputIterator first, InputIterator last);
template<class InputIterator>
  void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
template<container-compatible-range<value_type> R>
  void insert_range(R&& rg);
template<container-compatible-range<value_type> R>
  void insert_range(sorted_equivalent_t, R&& rg);
void insert(initializer_list<value_type> il)
  { insert(il.begin(), il.end()); }
void insert(sorted_equivalent_t s, initializer_list<value_type> il)
  { insert(s, il.begin(), il.end()); }

Change [flat.multiset.defn] as follows:

template<class InputIterator>
  void insert(InputIterator first, InputIterator last);
template<class InputIterator>
  void insert(sorted_equivalent_t, InputIterator first, InputIterator last);
template<container-compatible-range<value_type> R>
  void insert_range(R&& rg);
template<container-compatible-range<value_type> R>
  void insert_range(sorted_equivalent_t, R&& rg);
void insert(initializer_list<value_type> il)
  { insert(il.begin(), il.end()); }
void insert(sorted_equivalent_t s, initializer_list<value_type> il)
  { insert(s, il.begin(), il.end()); }

Add a new entry to [flat.multiset.modifiers] as follows:

template<container-compatible-range<value_type> R> void insert_range(sorted_equivalent_t, R&& rg);

x․ Effects: Equivalent to insert_range(std::forward<R>(rg)).
x․ Complexity: Linear in N, where N is size() after the operation.

Change [flat.set.defn] as follows:

template<class InputIterator>
  void insert(InputIterator first, InputIterator last);
template<class InputIterator>
  void insert(sorted_unique_t, InputIterator first, InputIterator last);
template<container-compatible-range<value_type> R>
  void insert_range(R&& rg);
template<container-compatible-range<value_type> R>
  void insert_range(sorted_unique_t, R&& rg);
void insert(initializer_list<value_type> il)
  { insert(il.begin(), il.end()); }
void insert(sorted_unique_t s, initializer_list<value_type> il)
  { insert(s, il.begin(), il.end()); }

Add a new entry to [flat.set.modifiers] as follows:

template<container-compatible-range<value_type> R> void insert_range(sorted_unique_t, R&& rg);

x․ Effects: Equivalent to insert_range(std::forward<R>(rg)).
x․ Complexity: Linear in N, where N is size() after the operation.

9. Sorting complexity

Most operations that require sorting come in sorted_unique and non-sorted_unique flavors; the sorted_unique flavor is rightly specified not to sort, which means it can be O(N) instead of O(N + M log M). That’s fine. But some non-sorted_unique constructors have Complexity clauses that mandate O(N) performance on input that happens to be sorted at runtime. The vendor has three ways to deal with this:

Guarantee that std::sort (or std::stable_sort if § 12.1 Stable sorting in insert is adopted) will always run in O(N) time on sorted input. This is not currently mandated by [alg.sort], so no vendor is likely to know off the top of their heads that they really guarantee this for all possible sorted inputs. libc++ certainly doesn’t know this for sure.
Add a linear-time pass on the front, e.g. if (!std::is_sorted(first, last)) std::sort(first, last). This wastes O(N) cycles in every case: it might improve the asymptotic performance in the rare case that the input happens to be sorted at runtime, but only at the cost of slowing down the expected case where the input is not sorted. libc++ doesn’t want to slow down the average caller.
Ignore the spec’s Complexity requirement. libc++ also doesn’t want to do this.

Louis Dionne would be happy with a resolution that requires all vendors to implement this optimization in std::sort itself, for ranges that happen to be sorted. I.e., change [sort]/5 as follows:

5․ Complexity: Let N be last - first. If the input is already sorted with respect to comp and proj, O(N) comparisons and projections. Otherwise, O(N log N) comparisons and projections. In either case, twice as many projections as comparisons.

and change [stable.sort]/5 as follows:

5․ Complexity: Let N be last - first. If the input is already sorted with respect to comp and proj, O(N) comparisons. If enough extra memory is available, O(N log(N)) comparisons. Otherwise, ~~at most~~ O(N log²(N)) comparisons. In ~~either~~ any case, twice as many projections as ~~the number of~~ comparisons.

If we changed [alg.sort], then we’d get [flat.foo]'s unusual complexity guarantees for free, and the following changes in [flat.foo] would be no-ops, just a bit of editorial cleanup. However, Louis and Arthur would prefer to leave [alg.sort] alone for now, making the following changes in [flat.foo] significant and non-editorial.

9.1. Wording

If these changes are not adopted wholesale, we still propose editorially to replace zip_view with zip and "if the container arguments are already sorted with respect to value_comp()" with "if key_cont is already sorted with respect to compare."

Change [flat.map.cons] as follows:

flat_map(key_container_type key_cont, mapped_container_type mapped_cont, const key_compare& comp = key_compare());
1․ Effects: Initializes c.keys with std::move(key_cont), c.values with std::move(mapped_cont), and compare with comp; sorts the range [begin(), end()) with respect to value_comp(); and finally erases the duplicate elements as if by:

auto zv = ~~ranges::zip_view~~ views::zip(c.keys, c.values); auto it = ranges::unique(zv, key_equiv(compare)).begin(); auto dist = distance(zv.begin(), it); c.keys.erase(c.keys.begin() + dist, c.keys.end()); c.values.erase(c.values.begin() + dist, c.values.end());

2․ Complexity: ~~Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.~~ Same as ranges::sort(ranges::zip(c.keys, c.values), value_comp()).

Change [flat.multimap.cons] as follows:

flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont, const key_compare& comp = key_compare());
1․ Effects: Initializes c.keys with std::move(key_cont), c.values with std::move(mapped_cont), and compare with comp; sorts the range [begin(), end()) with respect to value_comp().

2․ Complexity: ~~Linear in N if the container arguments are already sorted with respect to value_comp() and otherwise N log N, where N is the value of key_cont.size() before this call.~~ Same as ranges::sort(ranges::zip(c.keys, c.values), value_comp()).

Change [flat.multiset.cons] as follows:

explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());

1․ Effects: Initializes c with std::move(cont) and compare with comp~~, and~~ ; sorts the range [begin(), end()) with respect to compare.

2․ Complexity: ~~Linear in N if cont is sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.~~ Same as ranges::sort(c, compare).

Change [flat.set.cons] as follows:

explicit flat_set(container_type cont, const key_compare& comp = key_compare());

1․ Effects: Initializes c with std::move(cont) and compare with comp, ; sorts the range [begin(), end()) with respect to compare, ; and finally erases all but the first element from each group of consecutive equivalent elements.

2․ Complexity: ~~Linear in N if cont is sorted with respect to compare and otherwise N log N, where N is the value of cont.size() before this call.~~ Same as ranges::sort(c, compare).

10. `replace` should take by value

The current specification for replace takes the new container(s) by rvalue reference, which means you can’t just pass in a container the way you can with the key_cont constructor; instead, you have to manually std::move the container.

This might have been originally intended as a guard against accidental expensive copying of containers. But C++ doesn’t use this (explicit-pass-by-rvalue-reference) pattern anywhere else; and it’s inconsistent with the specification of the key_cont constructors, which do take by value and happily allow passing in lvalue containers by copy.

std::vector<int> v = {1,2,3};
std::flat_set<int> fs;

fs = std::flat_set(v); // OK
fs.replace(std::vector(v)); // OK

fs.replace(v);
  // Before: Ill-formed
  // After: OK

Taking by value and move-constructing into place is almost always just as performant as taking by rvalue-reference and move-constructing into place. Caveat: some containers are expensive to move-construct. std::pmr::vector is not such a container. Boost static_vector is. But we shouldn’t cater for such types, especially not at the cost of API consistency.

boost::container::static_vector<int, 100> v;
auto fs = std::flat_set(std::move(v)); // OK, does 2 expensive moves
fs.replace(std::move(v));
  // Before: OK, does 1 expensive move
  // After: OK, does 2 expensive moves
fs.replace(v);
  // Before: Ill-formed
  // After: OK, does 1 expensive copy and 1 expensive move

10.1. Wording

Change [flat.map.defn] as follows:

containers extract() &&;
void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);

Change [flat.map.modifiers] as follows:

void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);

36․ Preconditions: key_cont.size() == mapped_cont.size() is true, the elements of key_cont are sorted with respect to compare, and key_cont contains no equal elements.

37․ Effects: Equivalent to:

c.keys = std::move(key_cont); c.values = std::move(mapped_cont);

Change [flat.multimap.defn] as follows:

containers extract() &&;
void replace(key_container_type&& key_cont, mapped_container_type&& mapped_cont);

Change [flat.multiset.defn] as follows:

container_type extract() &&;
void replace(container_type&&);

Change [flat.multiset.modifiers] as follows:

void replace(container_type&& cont);

12․ Preconditions: The elements of cont are sorted with respect to compare.

13․ Effects: Equivalent to: c = std::move(cont);

Change [flat.set.defn] as follows:

container_type extract() &&;
void replace(container_type&&);

Change [flat.set.modifiers] as follows:

void replace(container_type&& cont);

12․ Preconditions: The elements of cont are sorted with respect to compare, and cont contains no equal elements.

13․ Effects: Equivalent to: c = std::move(cont);

11. Add `flat_set::keys()`

flat_map and flat_multimap both provide keys() and values() getters:

// observers
key_compare key_comp() const;
value_compare value_comp() const;

const key_container_type& keys() const noexcept      { return c.keys; }
const mapped_container_type& values() const noexcept { return c.values; }

flat_set and flat_multiset do not:

// observers
key_compare key_comp() const;
value_compare value_comp() const;

libc++ has found that .keys and .values are helpful in unit tests. The .extract method is a poor replacement.

auto ks = std::vector<int, A>({1,2,3}, A(1));
auto vs = std::vector<int, A>({4,5,6}, A(2));
auto m = std::flat_map(std::move(ks), std::move(vs));
assert(m.keys().get_allocator() == A(1));
assert(m.values().get_allocator() == A(2));
  // convenient

auto ks = std::vector<int, A>({1,2,3}, A(1));
auto s = std::flat_set(std::move(ks));
assert(std::move(s).extract().get_allocator() == A(1));
  // awkward, and modifies the value of s

For a const flat_set, there’s literally no way to get at the container and query its properties, such as capacity, allocator, or even size (which is important for unit tests, if not for real programming).

using S = std::flat_set<int, std::less<>, std::vector<int, A>>;
const S s = {1,2,3};
assert(s.keys().size() == 3);
assert(s.keys().capacity() >= 3);
  // Before: Impossible to retrieve this information
  // After: OK

Therefore we suggest adding a getter for the .keys of a set, just like we already have for the flat map types.

Notice that flat_map's .values() getter returns a container of mapped_type, not a container of value_type. flat_set doesn’t have a mapped_type; therefore it shouldn’t have .values() either.

11.1. Wording

Change [flat.multiset.defn] as follows:

// observers
key_compare key_comp() const;
value_compare value_comp() const;

const container_type& keys() const noexcept { return c; }

Change [flat.set.defn] as follows:

// observers
key_compare key_comp() const;
value_compare value_comp() const;

const container_type& keys() const noexcept { return c; }

12. Issues for discussion

The following subsections describe known issues with the flat containers where we don’t (yet) strongly propose a change. In some cases Louis Dionne asks for further clarification and/or changes to the wording. In some cases we’re just reporting implementation experience. In some cases it seems like a change is warranted, but it’s confusing enough that we don’t have a good wording patch yet.

12.1. Stable sorting in `insert`

For the tree-based associative containers, [associative.reqmts.general] defines the single-element foo::insert(val) to insert in a well-defined order; [associative.reqmts.general] defines the multi-element foo::insert(first, last) to insert in an unspecified order. Nevertheless, in practice, all three vendors implement the latter as a simple loop over the former, so we have this de-facto behavior portable everywhere:

struct Apathy { bool operator()(int, int) const { return false; } };
int a[] = {1,2,3,4,5};
std::multiset<int, Apathy> s;

// #1
for (int i : a) s.insert(i);
assert(std::ranges::equal(s, a)); // de jure

// #2
s.insert(a, a+5);
assert(std::ranges::is_permutation(s, a)); // de jure
assert(std::ranges::equal(s, a)); // de facto portable

// #3
s.insert_range(a);
assert(std::ranges::is_permutation(s, a)); // de jure
assert(std::ranges::equal(s, a)); // de facto portable

Similarly with equivalent keys in a map or multimap:

std::pair<int, int> a[] = {{1,1},{1,2},{1,3}};
std::map<int, int, Apathy> m;

// #1
for (auto kv : a) m.insert(kv);
assert(m[1] == 1); // de jure

// #2
m.insert(a, a+5);
assert(m[1] > 0); // de jure
assert(m[1] == 1); // de facto portable

// #3
m.insert_range(a);
assert(m[1] > 0); // de jure
assert(m[1] == 1); // de facto portable

Arthur’s libc++ implementation leans into the idea that flat_foo is a drop-in replacement for foo, and ensures that flat_foo::insert{,_range} will behave exactly like foo::insert{,_range}.

std::flat_multiset<int, Apathy> fs;

// #1
for (int i : a) fs.insert(i);
assert(std::ranges::equal(fs, a)); // de jure

// #2
fs.insert(a, a+5);
assert(std::ranges::is_permutation(fs, a)); // de jure
assert(std::ranges::equal(fs, a)); // libc++

// #3
fs.insert_range(a);
assert(std::ranges::is_permutation(fs, a)); // de jure
assert(std::ranges::equal(fs, a)); // libc++

flat_foo::insert(first, last) is defined by [flat.set.modifiers] to insert in order and then "sort the range." The vendor will be tempted to use std::sort, which in practice is not stable. Arthur’s implementation uses std::stable_sort specifically to ensure that fs will give the same results as s for all multi-element insertions.

Louis Dionne worries that by providing this additional de-facto guarantee, libc++ might be creating a "portability trap" — the programmer writes obvious code that works perfectly on libc++, and then when the programmer migrates to libstdc++ or Microsoft STL, they suddenly find that their code no longer works.

Therefore Louis asks whether LWG could specifically require that newly inserted elements be sorted stably, e.g.

template<class InputIterator> void insert(InputIterator first, InputIterator last);

5․ Effects: Adds elements to c as if by:

c.insert(c.end(), first, last);
Then, stably sorts the range of newly inserted elements with respect to compare; merges the resulting sorted range and the sorted range of pre-existing elements into a single sorted range; and finally erases all but the first element from each group of consecutive equivalent elements.

6․ Complexity: N + M log M, where N is size() before the operation and M is distance(first, last).

7․ Remarks: Since this operation performs an in-place merge, it may allocate memory.

This operation already requires an in-place merge, which allocates memory, so requiring it to also do a stable sort — which allocates memory — might not be considered such a big deal.

The alternative here would be for libc++ to lean into the idea that multiset::insert_range is supposed to leave the order of equivalent elements unspecified, and instrument it under libc++'s existing _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY flag (currently used only for sort, nth_element, and partial_sort). This would preserve the symmetry between multiset and flat_multiset, by making both of them de facto randomized order (at least in debug mode).

12.2. Non-explicit constructor from two containers

Arthur has observed in a blog post that flat_map's non-explicit constructor from two containers is deceptive when used with braced initializers.

void print_map(std::flat_multimap<int, int>);

// Test the two-container constructor... or is it?

print_map({ {1, 2, 3}, {10, 20, 30} }); // {1,10}, {2,20}, {3,30}
print_map({ {1, 2},    {10, 20} });     // {1,2}, {10,20}
print_map({ {1},       {10} });         // {1,10}
print_map({ {},        {} });           // {0,0}, {0,0}

To address this issue (if we wanted to), we could make one of the relevant constructors explicit. We obviously can’t prevent vector's construction from a braced list of elements, nor pair's from a braced list of (exactly two) elements, nor (in practice) pair's construction from {}; so the only constructor we could explicify to address this would be flat_multimap's own constructor from a braced list of (exactly two) containers. That is, we’d do this (and likewise in flat_map; flat_set doesn’t need to change):

explicit flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont)
  : flat_multimap(std::move(key_cont), std::move(mapped_cont), key_compare()) {}
flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
              const key_compare& comp = key_compare());
template<class Allocator>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                const Allocator& a);
template<class Allocator>
  flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
                const key_compare& comp, const Allocator& a);

Arthur thinks this change would be appreciated by programmers in practice (or rather, if we don’t make this change, then programmers will only ever notice this issue when it bites them). But it would be surprisingly asymmetric to explicify only this one constructor. The small benefit probably does not justify the asymmetry.

We recently made some constructors explicit in P2711 "Making multi-param constructors of views explicit," but that paper’s goal was to increase uniformity and symmetry, not to decrease it.

12.2.1. Remove the container constructors?

A more ambitious alternative would be to eliminate the container constructors entirely, and say that the only way to move containers into a flat container at all is via .replace, after the initial construction has already happened. This would be analogous to vector::reserve or unordered_map::max_load_factor — a feature with no associated constructor, just a setter after the fact. This would be really bold; but if we eliminated them, then we would also solve [LWG3802] (§ 12.11 Allocator-extended container constructors lack move semantics) in one fell swoop, and reduce the size of the constructor overload set from 38 constructors down to 20.

Another reason to think about eliminating the container constructors — at least the non-sorted_unique ones —is that right now the less convenient syntax flat_set(sorted_unique, ks) is faster than the more convenient syntax flat_set(ks); this might be a pitfall for the average programmer.

auto ks = std::pmr::vector<int>({1,2,3}, &mr1);
auto vs = std::pmr::vector<int>({1,2,3}, &mr2);

using FS = std::flat_set<int, std::less<>, decltype(ks)>;
// Before:
FS fs1 = FS(std::sorted_unique, std::move(ks));
// After:
FS fs1 = FS(ks.get_allocator());
fs1.replace(std::move(ks));

using FM = std::flat_map<int, int, std::less<>, decltype(ks), decltype(vs)>;
// Before:
FM fm1 = FM(std::sorted_unique, std::move(ks), std::move(vs));
  // Two different allocators in the same adaptor.
  // Almost certainly there is no valid reason to do this.
// After:
FM fm2 = FM(ks.get_allocator());
fm2.replace({ std::move(ks), std::move(vs) });
  // The data from vs is copied into arena mr1.
  // This is less performant, but more sane.
  // It is physically impossible to create the equivalent of fm1 above.

A downside is that it’s tedious for the programmer to reproduce the effect of the non-sorted_unique container constructors:

// Before:
FS fs2 = FS(std::move(ks));

// After:
FS fs2 = FS(ks.get_allocator());
std::ranges::sort(ks);
ks.erase(std::ranges::unique(ks).begin(), ks.end());
fs2.replace(std::move(ks));

// After, if you can afford one extra allocation:
FS fs2 = FS(std::from_range, ks | std::views::as_rvalue, ks.get_allocator());

We could boldly address this by making fs.replace(ks) always sort, and then if you know your data is already sorted, you would call fs.replace(sorted_unique, ks). That would make the interface much more symmetric, too, because the sortedness precondition would be 100% always indicated by the presence of sorted_unique_t in the signature.

It is very late in the game to be doing design work; but this particular redesign does seem to have a lot of varied benefits for vendors and programmers, with only procedural downsides. I haven’t written wording for this yet, but can do so if LWG is interested.

12.3. Complexity of `equal_range`

[associative.reqmts.general]/171 and /174 define the complexity of b.equal_range(k) and a_tran.equal_range(ke) as "Logarithmic." This means that we have the following required complexities, for both foo and flat_foo:

std::set<std::string> s;
std::multiset<std::string> ms;
std::set<std::string, std::less<>> st;
std::multiset<std::string, std::less<>> mst;

s.equal_range("abc"s);
  // 171: lower_bound, lower_bound+1; (1 + lg N) operations total
ms.equal_range("abc"s);
  // 171: lower_bound, upper_bound; (2 lg N) operations total
st.equal_range("abc");
  // 174: lower_bound, upper_bound; (2 lg N) operations total
mst.equal_range("abc");
  // 174: lower_bound, upper_bound; (2 lg N) operations total

For st.equal_range, [associative.reqmts.general]/7.22 forces us to consider the possibility that std::less<>::operator()(key_type, const char*) is a less granular equivalence relation than std::less<>::operator()(key_type, key_type); i.e., even though this is a set, it might still contain "duplicates" from the point of view of the heterogeneous comparator. It would be efficient in practice to find lower_bound("abc") in lg N time and then step forward linearly until we find an element not equal to "abc" — the expected number of duplicates for the average real-world workload is small. But the number of duplicates theoretically could be O(N); so we’re not allowed to do this (at least not without an arbitrary cap, e.g. if we don’t find the end of the range in 10 probes then fall back to upper_bound — bookkeeping which would again unnecessarily slow down the average case).

Consider a working programmer who writes

std::flat_set<std::string> s;
s.equal_range("abc");
  // lower_bound, lower_bound+1; (1 + lg N) operations total

and then switches to a heterogeneous comparator in an effort to "speed up" the code by avoiding the conversion to std::string:

std::flat_set<std::string, std::less<>> st;
st.equal_range("abc");
  // lower_bound, upper_bound; (2 lg N) operations total, cache-unfriendly

libc++ would like to see vendors given a little more freedom to experiment here.

The proposed wording below doesn’t require any vendor to change their implementation, since an existing implementation in O(log N) certainly also satisfies O(M + log N).

12.3.1. Wording

Change [associative.reqmts.general] as follows:

a_tran.upper_bound(ku)

166․ Result: iterator; const_iterator for constant a_tran.

167․ Returns: An iterator pointing to the first element with key r such that c(ku, r), or a_tran.end() if such an element is not found.

168․ Complexity: Logarithmic.

b.equal_range(k)

169․ Result: pair<iterator, iterator>; pair<const_iterator, const_iterator> for constant b.

170․ Effects: Equivalent to: return make_pair(b.lower_bound(k), b.upper_bound(k));

171․ Complexity: ~~Logarithmic.~~ O(M + log N), where N is b.size() and M is distance(b.lower_bound(k), b.upper_bound(k)).

a_tran.equal_range(ke)

172․ Result: pair<iterator, iterator>; pair<const_iterator, const_iterator> for constant a_tran.

173․ Effects: Equivalent to: return make_pair(a_tran.lower_bound(ke), a_tran.upper_bound(ke));

174․ Complexity: ~~Logarithmic.~~ O(M + log N), where N is a_tran.size() and M is distance(a_tran.lower_bound(ke), a_tran.upper_bound(ke)).

12.4. Special member functions

[flat.set.defn] currently does not declare any special member functions. This implies that they are defaulted, which implicitly specifies their constexprness, noexceptness, and triviality.

All three C++20 container adaptors (e.g. [priqueue.overview]) follow that approach, too.

All four associative and four unordered containers (e.g. [set.overview]) explicitly provide signatures for all five special members, including the destructor, like this:

    set(const set& x);
    set(set&& x);
[...]
    ~set();
    set& operator=(const set& x);
    set& operator=(set&& x)
      noexcept(allocator_traits<Allocator>::is_always_equal::value &&
               is_nothrow_move_assignable_v<Compare>);

Should flat_set's spec hew more closely to std::set's or priority_queue's? We tentatively think set's is the better model, so that the vendor would be free to make the special members non-defaulted. Vendors are still permitted to strengthen the noexceptness and/or triviality of declared functions; for example, both libc++ and libstdc++ make set(set&&) conditionally noexcept.

using V = std::experimental::fixed_capacity_vector<int, 100>;
static_assert(std::is_trivially_destructible_v<V>);
using M = std::flat_set<int, std::less<int>, V>;
static_assert(std::is_trivially_destructible_v<M>);
  // Before: Mandatory.
  // After: Permitted but not mandatory.

12.5. Moving from the comparator

As shown above, the associative and unordered containers give their move-assignment operator a noexcept-spec that strongly implies it must move-from the comparator, never copy it. This particularly affects libstdc++, where set(set&&) will copy a stateful comparator (e.g. std::function) instead of moving-from it, but set::operator=(set&&) must move the comparator, leaving the source object in a "radioactive" state.

This whole area is the subject of [LWG2227] "Stateful comparison objects in associative containers," and is certainly beyond the scope of this paper P2767.

struct TestLess : std::less<> {
  // make this too big to fit in the small buffer
  char pad_[1000];
};
using C = std::function<bool(int,int)>;
std::set<int, C> s({1,2,3}, C(TestLess()));
assert(s.key_comp() != nullptr);
auto t = std::move(s);
assert(s.key_comp() != nullptr);
  // libstdc++: Succeeds
  // libc++: Fails
s.clear();
s.insert({1,2});
  // libstdc++: OK
  // libc++: Throws std::bad_function_call
t = std::move(s);
s.insert({1,2});
  // Everyone: Throws std::bad_function_call

If we user-declare flat_set::operator=(flat_set&&), we must decide whether to give it a similar noexcept-spec.

12.5.1. Possible wording

(This wording merge-conflicts with the resolution of [LWG3884], which in turn merge-conflicts with the editorial refactoring at the beginning of this paper P2767. We can polish it later; the first question is whether LWG wants to pursue this direction at all.)

For example, change [flat.map.defn] as follows:

// [flat.map.cons], constructors
flat_map() : flat_map(key_compare()) { }

flat_map(const flat_map&);
flat_map(flat_map&&);
flat_map& operator=(const flat_multimap&);
flat_map& operator=(flat_multimap&&)
  noexcept(is_nothrow_move_assignable_v<KeyContainer> &&
           is_nothrow_move_assignable_v<MappedContainer> &&
           is_nothrow_move_assignable_v<Compare>);)
~flat_map();

flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
         const key_compare& comp = key_compare());

12.6. "Qualifies as a container"

Arthur’s libc++ implements an alternative resolution to [LWG3803]. This resolution applies generally to all container adaptors, and has the advantage of not ad-hoc relying on a complicated type trait (is_invocable) but being a little more consistent with the pre-existing spec.

The choice of C::const_iterator is simply because T::value_type is already present for allocators, and T::iterator is already present for many iterators (those that inherit from std::iterator, for example). We could just as well choose a criterion like "The expression declval<C&>().size() is well-formed when treated as an unevaluated operand."

12.6.1. Wording

Arthur’s preferred resolution is shown in this color . Parts of the current C++23 Working Draft that were introduced by the adopted resolution of LWG3803, but would be removed by this change, are shown in this color .

Change [container.reqmts]/69 as follows:

69․ The behavior of certain container member functions and deduction guides depends on whether types qualify as input iterators, containers, or allocators.

x․ The extent to which an implementation determines that a type cannot be an input iterator is unspecified, except that as a minimum integral types shall not qualify as input iterators.
x․ ~~Likewise, the~~ The extent to which an implementation determines that a type cannot be an allocator is unspecified, except that as a minimum a type A shall not qualify as an allocator unless it meets both of the following conditions:
(69.1) The qualified-id A::value_type is valid and denotes a type ([temp.deduct]).

(69.2) The expression declval<A&>().allocate(size_t{}) is well-formed when treated as an unevaluated operand.

x․ The extent to which an implementation determines that a type cannot be a container is unspecified, except that as a minimum a type C shall not qualify as a container unless the qualified-id C::const_iterator is valid and denotes a type.

Change [container.adaptors.general]/6 as follows:

6․ A deduction guide for a container adaptor shall not participate in overload resolution if any of the following are true:

(6.1) It has an InputIterator template parameter and a type that does not qualify as an input iterator is deduced for that parameter.

(6.2) It has a Compare template parameter and a type that qualifies as an allocator is deduced for that parameter.

(6.3) It has a Container, KeyContainer, or MappedContainer template parameter and a type that ~~qualifies as an allocator~~ does not qualify as a container is deduced for that parameter.

(6.4) It has no Container, KeyContainer, or MappedContainer template parameter, and it has an Allocator template parameter, and a type that does not qualify as an allocator is deduced for that parameter.

(6.5) It has both Container and Allocator template parameters, and uses_allocator_v<Container, Allocator> is false.

(6.6) It has both KeyContainer and Allocator template parameters, and uses_allocator_v<KeyContainer, Allocator> is false.

(6.7) It has both KeyContainer and Compare template parameters, and
is_invocable_v<const Compare&, const typename KeyContainer::value_type&, const typename KeyContainer::value_type&>
is not a valid expression or is false.
(6.8) It has both MappedContainer and Allocator template parameters, and uses_allocator_v<MappedContainer, Allocator> is false.

12.7. `iterator` and `const_iterator`

flat_set::iterator and flat_set::const_iterator are presented as if they could be two different types. This is consistent with how we do it in set and unordered_set. But in practice, all three vendors make set::iterator and set::const_iterator the same type. We should consider refactoring the spec of set, unordered_set, and flat_set all at once to mandate that these iterator types be the same type, the same way we already do for basic_string_view and (since C++23 introduced std::const_iterator) span<const T>.

This would allow us to remove a lot of redundant overloads from the specification, e.g. we don’t need both iterator find(value_type) and const_iterator find(value_type) const if those are the same iterator type. Vendors can already do this removal in their implementations if they choose to. This is merely a question of our getting to do it in the paper specification too, under the banner of "standardizing existing practice."

12.8. Support for non-standard containers

Vendors are required to support "random-access containers," which means vector<T> (except for vector<bool>) and deque<T>. It’s unclear if vendors are required to support non-standard containers such as boost::container::vector<T>; and if so, what public API those containers must provide in order to interoperate with flat_set.

For example, suppose the underlying container supports C(first, last) but not C(from_range, rg). Then I would expect that I couldn’t initialize a flat_set<T, Compare, C> with flat_set(from_range, rg); but I should still be able to initialize it with flat_set(first, last), right? It would be nice to see what’s required and what’s encouraged in this area.

libc++ goes very slightly out of its way to support vector<bool> as the underlying container, even though we believe we’re not required to support it.

12.9. Inconsistent handling of redundancy in [flat.multiset] and [flat.multimap]

See #6246.

[flat.multiset.overview/4] uses the same boilerplate as vector, set, flat_set, and flat_map:

Descriptions are provided here only for operations on flat_multiset that are not described in one of the general sections or for operations where there is additional semantic information.

[flat.multimap.overview/4] uses different boilerplate:

Except as otherwise noted, operations on flat_multimap are equivalent to those of flat_map, except that flat_multimap operations do not remove or replace elements with equal keys.

[Example 1: flat_multimap constructors and emplace do not erase non-unique elements after sorting them. —end example]

That’s a little handwavey: It doesn’t bother to explain that flat_multimap::insert(sorted_equivalent_t, initializer_list) is "equivalent to" flat_map::insert(sorted_unique_t, initializer_list). It doesn’t bother to explain how the iterator return value of flat_multimap::insert(value_type&&) is derived from the pair<iterator, bool> return value of flat_map::insert(value_type&&).

But it does make the spec a lot shorter! Should we apply the same technique to [flat.multiset] that we already apply to [flat.multimap]? I haven’t written wording for this yet, but can do so if LWG is interested.

Vice versa, should we tweak [flat.multimap]'s wording to address the two "doesn’t bother" points above? Should we tweak it to say "equivalent keys" or "duplicate keys" instead of "equal keys"?

12.10. Noexcept `swap`

This area seems to have been tweaked quite a bit at Batavia 2018. See the minutes.

flat_set::swap is currently specified as unconditionally noexcept, which is inconsistent both with std::set and with the pre-existing adaptors.

// [flat.set.defn]
void swap(flat_set& y) noexcept;

// [priqueue.overview]
void swap(priority_queue& q) noexcept(is_nothrow_swappable_v<Container> &&
                                      is_nothrow_swappable_v<Compare>)
  { using std::swap; swap(c, q.c); swap(comp, q.comp); }

// [set.overview]
void swap(set&)
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
           is_nothrow_swappable_v<Compare>);

[associative.reqmts.except]/3: For associative containers, no swap function throws an exception unless that exception is thrown by the swap of the container’s Compare object (if any).

Suppose the underlying container has a throwing move-constructor (like MSVC std::list), and lacks a custom swap; then std::swap<Container> can throw. Or, suppose the underlying container is boost::container::static_vector<T>; then its swap must swap T objects, which can throw.

Now, what happens if swapping the containers actually does throw? Then both containers are in an unknown state, so we must restore the invariant by clearing both containers. We do the same thing if insert or erase throws, so this is nothing new.

What happens if swapping the comparators throws? Then we cannot recover. Louis suggests adding is_nothrow_swappable_v<Compare> as a constraint. The intent is nicely ergonomic: Almost all comparators are nothrow swappable (including std::function, if we want to support that: [LWG2227]). And the resulting behavior seems better: In the pathological corner case where flat_set cannot safely provide swappability, it’s better for it not to be swappable at all, than for it to falsely advertise a noexcept swap. But, if we constrain away flat_set's hidden-friend swap, swap(fs, fs) will still compile; it’ll just fall back to std::swap<T> [with T=flat_set]. We could actually =delete the swap function, like this:

    void swap(flat_map& y) noexcept;
    void swap(flat_map& y)
      noexcept(is_nothrow_swappable_v<key_container_type> &&
               is_nothrow_swappable_v<mapped_container_type>)
      requires is_nothrow_swappable_v<key_compare>
    void clear() noexcept;

[...]

    friend void swap(flat_map& x, flat_map& y) noexcept { x.swap(y); }
    friend void swap(flat_map& x, flat_map& y)
      noexcept(is_nothrow_swappable_v<key_container_type> &&
               is_nothrow_swappable_v<mapped_container_type>)
      requires is_nothrow_swappable_v<key_compare>
        { x.swap(y); }
    friend void swap(flat_map& x, flat_map& y)
      requires (!is_nothrow_swappable_v<key_compare>) = delete;

but even then ranges::swap(fs, fs) would still compile; it would fall back to the three-step move-and-assign.

It seems to be impossible to make flat_set non-swappable. The only reasonable options are:

Keep the status quo (unconditional noexcept) and terminate the program if swapping containers throws
Conditional noexcept like in [priqueue.overview], and don’t care if swapping throws (i.e. match priority_queue's status quo)
Conditional noexcept like in [priqueue.overview], and clear both containers if swapping throws (but this won’t prevent radioactivity, if swap left the comparator in a bad state)

12.10.1. Specified in terms of `ranges::swap`

Orthogonally: It surprises us that [flat.map.modifiers] specifies swap's implementation in terms of ranges::swap(c, y.c) etc. This feels overspecified; [container.reqmts] adequately covers the semantics of swapping, and vendors should be able to decide for themselves how to swap comparator objects, just like we do in std::set. Arguably the tight specification helps programmers providing their own underlying containers: they know they just need to provide an ADL swap or the requirements of [concept.swappable]/2.3. But one might point out to those programmers that their underlying container must provide the API required in [container.reqmts]/49–51, so the vendor can use ADL swap(c, y.c) or c.swap(y.c) if they want to.

libc++'s implementation currently uses ADL swap(c, y.c), which is equivalent to ranges::swap for all containers satisfying [container.reqmts]/51; but the difference between swap(compare, y.compare) and ranges::swap(compare, y.compare) is probably observable.

12.11. Allocator-extended container constructors lack move semantics

(This whole section would be mooted by § 12.2.1 Remove the container constructors?.)

libc++ has implemented move-semantic allocator-extended constructors for all four flat containers (Godbolt). This is [LWG3802].

template<class T, class C = std::less<T>>
using PmrFlatSet = std::flat_set<T, C, std::pmr::vector<T>>;

std::pmr::monotonic_buffer_resource mr;
auto sets = std::pmr::vector<PmrFlatSet<int>>(&mr);
auto cont1 = std::pmr::vector<int>({1,2,3}, &mr);
sets.emplace_back(std::move(cont1));
  // Before: Makes copies of all the data
  // After: Takes ownership of the existing data

auto cont2 = std::pmr::vector<std::unique_ptr<int>>();
auto fs = std::flat_set(std::move(cont2));
  // Before: Ill-formed
  // After: OK

The wording patch for this (based on top of P2767’s editorial refactoring) would look something like this. I haven’t written wording for this yet, but can do so, if LWG is interested, after P2767’s editorial refactoring is merged.

// [flat.map.cons.alloc], constructors with allocators

template<class Alloc>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_map(const key_container_type& key_cont, mapped_container_type&& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_map(key_container_type&& key_cont, const mapped_container_type& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_map(key_container_type&& key_cont, mapped_container_type&& mapped_cont,
           const Alloc& a);
template<class Alloc>
  flat_map(const key_container_type& key_cont, const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(const key_container_type& key_cont, mapped_container_type&& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(key_container_type&& key_cont, const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(key_container_type&& key_cont, mapped_container_type&& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, const key_container_type& key_cont,
           const mapped_container_type& mapped_cont, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, const key_container_type& key_cont,
           mapped_container_type&& mapped_cont, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, key_container_type&& key_cont,
           const mapped_container_type& mapped_cont, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, key_container_type&& key_cont,
           mapped_container_type&& mapped_cont, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, const key_container_type& key_cont,
           const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, const key_container_type& key_cont,
           mapped_container_type&& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, key_container_type&& key_cont,
           const mapped_container_type& mapped_cont,
           const key_compare& comp, const Alloc& a);
template<class Alloc>
  flat_map(sorted_unique_t, key_container_type&& key_cont,
           mapped_container_type&& mapped_cont,
           const key_compare& comp, const Alloc& a);

13. Implementation experience

I have implemented all of [P0429]/[P1222] and all of this proposal as a series of patches against libc++ trunk; see [Patch]. You can experiment with it on Godbolt Compiler Explorer; just use the P1144 branch of Clang, which uses this patched libc++ by default.

14. Acknowledgments

Thanks to Tomasz Kamiński for recommending Arthur write this paper.
Thanks to Louis Dionne for his code review of libc++'s flat_set implementation.

P2767R0flat_map/flat_set omnibus

Published Proposal, 2023-05-14

Abstract

1. Changelog

2. Introduction

3. Editorial introduction of [flat.foo.cons.alloc]

3.1. [flat.map]

3.2. [flat.multimap]

3.3. [flat.multiset]

3.4. [flat.set]

4. Accidentally explicit constructor

4.1. Wording

5. Add move semantics to flat_set::insert_range

5.1. Wording

6. Add move semantics to flat_map::insert_range

6.1. Wording

7. insert is more primitive than emplace

7.1. Heterogeneous multiset::insert

7.2. "Initializes" phrasing

7.3. Unusual constraints

7.4. Ambiguity with insert(first, last)

7.5. Wording

8. insert_range(sorted_unique, rg)

8.1. Wording

9. Sorting complexity

9.1. Wording

10. replace should take by value

10.1. Wording

11. Add flat_set::keys()

11.1. Wording

12. Issues for discussion

12.1. Stable sorting in insert

12.2. Non-explicit constructor from two containers

12.2.1. Remove the container constructors?

12.3. Complexity of equal_range

12.3.1. Wording

12.4. Special member functions

12.5. Moving from the comparator

12.5.1. Possible wording

12.6. "Qualifies as a container"

12.6.1. Wording

12.7. iterator and const_iterator

12.8. Support for non-standard containers

12.9. Inconsistent handling of redundancy in [flat.multiset] and [flat.multimap]

12.10. Noexcept swap

12.10.1. Specified in terms of ranges::swap

12.11. Allocator-extended container constructors lack move semantics

13. Implementation experience

14. Acknowledgments

References

Informative References

P2767R0
flat_map/flat_set omnibus

5. Add move semantics to `flat_set::insert_range`

6. Add move semantics to `flat_map::insert_range`

7. `insert` is more primitive than `emplace`

7.1. Heterogeneous `multiset::insert`

7.4. Ambiguity with `insert(first, last)`

8. `insert_range(sorted_unique, rg)`

10. `replace` should take by value

11. Add `flat_set::keys()`

12.1. Stable sorting in `insert`

12.3. Complexity of `equal_range`

12.7. `iterator` and `const_iterator`

12.10. Noexcept `swap`

12.10.1. Specified in terms of `ranges::swap`