P2767R1
flat_map/flat_set omnibus

1. Changelog

• R1 (post-Varna 2023):

  • LWG approved §3 as editorial.

  • LWG reviewed §4,5,6,7. Update those sections' rationales and proposed wordings.

  • Split § 7.1 Heterogeneous insert (to LEWG) away from the rest of §7, because it (alone) requires LEWG input; it is now § 13 Heterogeneous multiset::insert.

  • Split § 12.2 Non-explicit container constructor away from the rest of §12, to draw attention; it is now § 14 Non-explicit constructor from two containers. Write its wording.

• 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.

3. Editorial (merged in R0)

P2767R0’s editorial change was reviewed by LWG in Varna (2023-06-16) and approved; it is submitted as #6274.

#6274 trivially merge-conflicts with the resolution of [LWG3884] (which adds new allocator-extended constructors). I propose to rebase LWG3884’s resolution on top of #6274 as soon as #6274 is merged to trunk.

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.

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

Note: This section was updated in R1 following LWG’s preferred direction. Thanks to Zhihao Yuan for finding the precedent for "Let comp be..." in list::unique.

Change [flat.multiset.defn] as follows:

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

explicit flat_multiset(const key_compare& comp)
  : c(), compare(comp) { }

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

flat_multiset(sorted_equivalent_t, container_type cont,
              const key_compare& comp = key_compare())
  : c(std::move(cont)), compare(comp) { }

Change [flat.multiset.cons] as follows:

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

x․ Let comp be key_compare() for the first overload.

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.

Change [flat.set.defn] as follows:

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

explicit flat_set(const key_compare& comp)
  : c(), compare(comp) { }

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

flat_set(sorted_unique_t, container_type cont, const key_compare& comp = key_compare())
  : c(std::move(cont)), compare(comp) { }

Change [flat.set.cons] as follows:

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

x․ Let comp be key_compare() for the first overload.

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.

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.

Compare the current wording for flat_set.insert_range (added by P1222) versus priority_queue.push_range (added in P1206R5 and tweaked in R6). priority_queue’s wording is not only more robustly Rangified, but also more performant.

Arthur doesn’t know why P1206R5/R6 chose to pass forward<R>(rg) to append_range but plain old lvalue rg to ranges::copy; it seems like it should have forwarded in both places or else forwarded in neither place. Arthur is trying to find out from P1206’s authors. For now, by default, let’s just be consistent with P1206.

5.1. Wording

Note: This section was updated in R1 following LWG’s preferred direction; see rationale above.

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& e : rg) {
  c.insert(c.end(), e);
}

Adds all elements of rg to c via c.append_range(std::forward<R>(rg)) if that is a valid expression, or ranges::copy(rg, back_inserter(c)) otherwise. 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 all elements of rg to c via c.append_range(std::forward<R>(rg)) if that is a valid expression, or ranges::copy(rg, back_inserter(c)) otherwise. 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.

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

The wording below implicitly converts range_reference_t<R> to value_type e, and then move-constructs from e.first and e.second into the map’s containers. Note that e.first and e.second are never reference types, so std::move is correct.

LWG in Varna briefly feinted in the direction of trying to metaprogram away the extra move-construct (e.g. by changing the lambda’s parameter type to something like conditional_t<same_as<decay_t<range_reference_t<R>>, value_type>, range_reference_t<R>, value_type>), but I felt strongly that the chance of getting that correct on the first try was near-nil. Besides, we realized that we were trying to save O(M) move operations along a codepath whose very next step was to do an O(M log M) sort and an O(N) inplace_merge.

If any library vendor actually wants to try that kind of metaprogramming, they are welcome to do so under the As-If Rule. libc++ will not do it.

6.1. Wording

Note: This section was updated in R1 following LWG’s preferred direction; see rationale above.

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& e : rg)
ranges::for_each(rg, [&c](value_type e) {
  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 = 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.

The current definition of emplace is not expressed in terms of insert(value_type(...)). P2767R0 proposed not to change it, simply to keep the diff small. But LWG in Varna asked to make that simplification. libc++'s implementation already implements emplace in terms of insert, so there doesn’t seem to be any sneaky subtlety in that area; we can just do it. So P2767R1 does it.

7.1. Heterogeneous insert (to LEWG)

Note: LWG in Varna raised an objection to adding heterogeneous flat_multiset::insert(K&&) without LEWG input. On the other hand, §7.2,3,4 were acceptable LWG business. Therefore, the rationale and wording for P2767R0’s §7.1 have moved to § 13 Heterogeneous multiset::insert, and P2767R1’s § 7.6 Wording no longer includes the insert(K&&) overload.

7.2. "Initializes" phrasing

The proposed wording below brings [flat.map.modifiers]/2 into 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. [...]

P2767R0 asked whether LWG had appetite to invent something less jargony. No, LWG did not.

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.

With the Constraints elements gone, and emplace(x...) always implemented as insert(value_type(x...)), there is no longer any need for an English description of emplace. It is now specified by code only.

The rewrite of emplace_hint(pos, x...) into insert(pos, value_type(x...)) is frightening, because of the very large overload set of insert; but I think it’s safe: it should always be a perfect match for insert(const_iterator, value_type&&) and never a viable match for any other overload at all.

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. flat_multiset::emplace by rotation

template<class T, class C = std::less<T>>
using PmrFlatMultiset = std::flat_multiset<T, C, std::pmr::vector<T>>;
auto fms = PmrFlatMultiset<std::pmr::string>(&mr);
fms.emplace("hello world");

The C++23 status quo is that we "initialize an object t of type value_type" with "hello world", and then insert it into c. The initial construction of t uses the wrong allocator.

P2767R1 proposes to simplify the specification of flat_multiset::emplace in terms of flat_multiset::insert; but does not propose to change this behavior. We’ll still be constructing a temporary with the wrong allocator.

Tim Song has observed that we could specify flat_multiset::emplace as follows, instead:

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 Adds an element to c as if by:

auto it = ranges::upper_bound(c, t, compare);
c.insert(it, std::move(t));
auto n = ranges::upper_bound(c, t, compare) - c.begin();
c.emplace_back(std::forward(args)...);
ranges::rotate(c.begin() + n, c.end() - 1, c.end());

3․ Returns: An iterator that points to the inserted element.

This would ensure that the new object never gets constructed with the wrong allocator. However, this benefit comes with at least three downsides:

• A user-provided random-access container (e.g. one based on a skip list) might have a way to insert in the middle of the container without moving any other elements at all, or moving only O(1) elements instead of O(n) elements.

• Even for vector it seems more expensive to rotate the elements than to do the right-shift that c.insert would do. Is the cost worth the benefit?

• The proposal applies to flat_multiset::emplace but not to flat_set::emplace (because we don’t want to insert a duplicate and then have to erase it again) and not to flat_multimap::emplace (because we don’t have a container of pairs to emplace into, in that case).

We could mitigate the first two downsides by leaving emplace alone, and doing the rotate-based version only for emplace_hint. There, if the caller gives us an accurate hint, we won’t need to rotate anything at all; and when we do rotate, it can only be because the caller gave us an inaccurate hint (i.e. it’s "their fault"). But this would still suffer the third downside (i.e. inconsistency), and it would be more complicated to teach. Arthur thinks that it is best not to use rotate at all. The proposed wording below does not use rotate.

7.6. Wording

Note: This section was updated in R1 following LWG’s preferred direction; see rationale above. We no longer add insert(K&&) to flat_multiset; that wording has moved to § 13 Heterogeneous multiset::insert.

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);
  { return insert(value_type(std::forward(args)...)); }
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);
    { return insert(position, value_type(std::forward(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 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.

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 x.first.

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);
  { return insert(value_type(std::forward(args)...)); }
template<class... Args>
  iterator emplace_hint(const_iterator position, Args&&... args);
    { return insert(position, value_type(std::forward(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)); }
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)); }

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.

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 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 can easily add this overload.

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<class InputIterator>
  void insert(sorted_equivalent_t, InputIterator first, InputIterator last);

7․ Effects: Equivalent to insert(first, last).

8․ Complexity: Linear.

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<class InputIterator>
  void insert(sorted_equivalent_t, InputIterator first, InputIterator last);

7․ Effects: Equivalent to insert(first, last).

8․ Complexity: Linear.

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<class InputIterator>
  void insert(sorted_unique_t, InputIterator first, InputIterator last);

8․ Effects: Equivalent to insert(first, last).

9․ Complexity: Linear.

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

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

for (const auto& e : rg) {
  c.insert(c.end(), 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.

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.

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

9. Complexity clauses of container constructors

(This whole section would be mooted by § 14.2 Remove the container constructors; make replace sort by default.)

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

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 = 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 container constructor

Note: This section of P2767R0 has moved in P2767R1 to § 14 Non-explicit constructor from two containers.

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

Note: This wording merge-conflicts with the resolution of [LWG3884], which in turn merge-conflicts with the editorial refactoring in §3. 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 § 14.2 Remove the container constructors; make replace sort by default.)

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