D2767R2
flat_map/flat_set omnibus

1. Changelog

• R2 (post-LEWG-telecon, pre-Tokyo 2024):

  • Vastly reorder, and separate the sections into "LWG business" and "LEWG business." Combine all the subsections that would be resolved at once by § 5 (LEWG) Monolithic proposal: tag narrow-contract functions, remove container ctors.

  • Replace many snippets with Tony Tables for clarity.

  • Wording nits.

  • Add § 4.2 Zero-initialization of containers.

• R1 (post-Varna 2023):

  • LWG approved §3 as editorial.

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

  • Split § 4.4 Efficient flat_multiset::insert(K&&) and § 5.1 Deceptive list-initialization from two lists out of their respective sections.

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

3.1. Editorial (merged in R0)

P2767R0’s editorial change was reviewed by LWG in Varna (2023-06-16) and approved by a vote of 7–0–1 (minutes); it is submitted as #6274. Jonathan Wakely is on the hook to approve and merge it.

Once this editorial business is merged, the rest of the diffs presented in this paper will apply cleanly.

3.2. Accidentally explicit constructor

STL style is that multi-argument constructors should be non-explicit; see [P1163]. This change is non-editorial, but non-controversial. LWG reviewed R0’s wording in Varna and expressed a preferred direction. Zhihao Yuan found the precedent for "Let comp be..." in list::unique.

3.2.1. Wording

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.

3.3. 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. On 2023-07-17, Casey Carter concurred: "Let’s assume it’s just a mistake and change both places consistently."

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

Adds the elements of rg to c via c.append_range(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 the elements of rg to c via c.append_range(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.

3.4. (LWG4000) Add move semantics to flat_map::insert_range

Note: This resolves [LWG4000].

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.

3.4.1. Wording

Note: This section was updated in R1 following LWG’s preferred direction. I don’t recall why LWG preferred ranges::for_each over the ranged-for-loop shown in [LWG4000]'s P/R.

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.

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

3.5.1. "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.

3.5.2. Inconsistent emplace 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.

3.5.3. Ambiguous 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.

3.5.4. 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 instead specify flat_multiset::emplace like this (following inplace_vector’s precedent):

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));
c.emplace_back(std::forward<Args>(args)...);
auto n = upper_bound(c.begin(), c.end() - 1, c.back(), compare) - c.begin();
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.

3.5.5. Wording

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

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>(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)); }
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<class P> pair<iterator, bool> insert(P&& x);
template<class P> 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>(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)); }

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.

3.6. 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"?

3.7. 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 eight associative and/or unordered containers (e.g. [set.overview]) explicitly provide signatures for all five special members, including 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::inplace_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.

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

3.7.2. Partial wording

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());

4. LEWG business

4.1. 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."

4.2. Zero-initialization of containers

Jean-Philippe Boivin points out that the flat containers currently specify their constructors as value-initializing, rather than default-initializing, the keys and values containers. This is extremely expensive for in-place containers such as P0843 std::inplace_vector (proposed for C++26). A reduced example looks like this (Godbolt):

struct flat_set {
    using key_compare = std::less<int>;
    using container_type = std::inplace_vector<int, 1024>;

    flat_set() : flat_set(key_compare()) { }
    explicit flat_set(const key_compare& comp)
      : c_(), compare_(comp) { }
private:
    [[no_unique_address]] key_compare compare_;
    container_type c_;
};

The value-initialization of c_ zeroes the memory footprint of c_ and then calls inplace_vector’s default constructor (which initializes size_ but is otherwise trivial). This involves a 4096-byte memset. On the other hand, if flat_set’s constructors were defined as

flat_set() = default;
explicit flat_set(const key_compare& comp)
  : compare_(comp) { }

then there would be no 4096-byte memset. This would make flat_set more suitable for embedded programming, where every cycle counts.

We don’t care about the cost of zero-initializing the comparator, since comparators are usually empty types, or at least small.

4.2.1. Wording

Change [flat.map.defn] as follows:

[...]

// [flat.map.cons], constructors
flat_map() : flat_map(key_compare()) { }
flat_map() = default;
explicit flat_map(const key_compare& comp)
  : c(), compare(comp) { }
flat_map(key_container_type key_cont, mapped_container_type mapped_cont,
         const key_compare& comp = key_compare());
flat_map(sorted_unique_t, key_container_type key_cont, mapped_container_type mapped_cont,
         const key_compare& comp = key_compare());
template<class InputIterator>
  flat_map(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
    : c(), compare(comp) { insert(first, last); }
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<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>
  flat_map(from_range_t, R&& rg, const key_compare& comp)
    : flat_map(comp) { insert_range(std::forward<R>(rg)); }

[...]

Change [flat.multimap.defn] as follows:

[...]

// [flat.multimap.cons], constructors
flat_multimap() : flat_multimap(key_compare()) { }
flat_multimap() = default;
explicit flat_multimap(const key_compare& comp)
  : c(), compare(comp) { }
flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,
              const key_compare& comp = key_compare());
flat_multimap(sorted_equivalent_t, key_container_type key_cont, mapped_container_type mapped_cont,
              const key_compare& comp = key_compare());
template<class InputIterator>
  flat_multimap(InputIterator first, InputIterator last, const key_compare& comp = key_compare())
    : c(), compare(comp) { insert(first, last); }
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<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>
  flat_multimap(from_range_t, R&& rg, const key_compare& comp)
    : flat_multimap(comp) { insert_range(std::forward<R>(rg)); }

[...]

Change [flat.multiset.defn] as follows:

[...]

// [flat.multiset.cons], constructors
flat_multiset() : flat_multiset(key_compare()) { }
flat_multiset() = default;
explicit flat_multiset(const key_compare& comp)
  : c(), compare(comp) { }
explicit flat_multiset(container_type cont, const key_compare& comp = key_compare());
flat_multiset(sorted_equivalent_t, container_type cont,
              const key_compare& comp = key_compare())
  : c(std::move(cont)), compare(comp) { }
template<class InputIterator>
  flat_multiset(InputIterator first, InputIterator last,
                const key_compare& comp = key_compare())
    : c(), compare(comp)
    { insert(first, last); }
template<class InputIterator>
  flat_multiset(sorted_equivalent_t, InputIterator first, InputIterator last,
                const key_compare& comp = key_compare())
    : c(first, last), compare(comp) { }
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>
  flat_multiset(from_range_t, R&& rg, const key_compare& comp)
    : flat_multiset(comp)
    { insert_range(std::forward<R>(rg)); }

[...]

Change [flat.set.defn] as follows:

[...]

// [flat.set.cons], constructors
flat_set() : flat_set(key_compare()) { }
flat_set() = default;
explicit flat_set(const key_compare& comp)
  : c(), compare(comp) { }
explicit flat_set(container_type cont, const key_compare& comp = key_compare());
flat_set(sorted_unique_t, container_type cont,
         const key_compare& comp = key_compare())
  : c(std::move(cont)), compare(comp) { }
template<class InputIterator>
  flat_set(InputIterator first, InputIterator last,
           const key_compare& comp = key_compare())
    : c(), compare(comp)
    { insert(first, last); }
template<class InputIterator>
  flat_set(sorted_unique_t, InputIterator first, InputIterator last,
           const key_compare& comp = key_compare())
    : c(first, last), compare(comp) { }
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>
  flat_set(from_range_t, R&& rg, const key_compare& comp)
    : flat_set(comp)
    { insert_range(std::forward<R>(rg)); }

[...]

4.3. Add flat_set::keys()

flat_map and flat_multimap 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, because it is mutating. 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.

Therefore we suggest adding flat_{multi,}set.keys().

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.

auto m = std::flat_map({{1,2},{3,4},{5,6}}, A(1));
assert(m.keys().get_allocator() == A(1));
assert(m.values().get_allocator() == A(1));
  // OK, m is not modified
auto s = std::flat_set({1,2,3}, A(1));
assert(std::move(s).extract().get_allocator() == A(1));
  // awkward, s is modified
const auto cs = std::flat_sett);
assert(???);
  // no way to check cs’s capacity

auto m = std::flat_map({{1,2},{3,4},{5,6}}, A(1));
assert(m.keys().get_allocator() == A(1));
assert(m.values().get_allocator() == A(1));
  // OK, m is not modified
auto s = std::flat_set({1,2,3}, A(1));
assert(s.keys().get_allocator() == A(1));
  // OK, s is not modified
const auto cs = std::flat_sett);
assert(cs.keys().capacity() == 0);
  // OK, cs can be tested

4.3.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; }

4.4. Efficient flat_multiset::insert(K&&)

std::set<BigNum, std::less<>> s;
s.insert(42);
  // Find the insertion point via less(int, BigNum)
  // Maybe construct BigNum(int) in-place in a new node
  // Maybe attach the node to the tree
std::flat_set<BigNum, std::less<>> s;
s.insert(42);
  // Find the insertion point via less(int, BigNum)
  // Maybe construct BigNum(int) in-place in the vector

std::set<BigNum, std::less<>> s;
s.insert(42);
  // Find the insertion point via less(int, BigNum)
  // Maybe construct BigNum(int) in-place in a new node
  // Maybe attach the node to the tree
std::flat_set<BigNum, std::less<>> s;
s.insert(42);
  // Find the insertion point via less(int, BigNum)
  // Maybe construct BigNum(int) in-place in the vector

std::multiset<BigNum, std::less<>> s;
s.insert(42);
  // Construct BigNum(int) in-place in a new node
  // Find the insertion point via less(BigNum, BigNum)
  // Attach the node to the tree
std::flat_multiset<BigNum, std::less<>> s;
s.insert(42);
   // Construct BigNum(int) in the argument slot
   // Find the insertion point via less(BigNum, BigNum)
   // Move-construct BigNum(BigNum&&) into the vector

std::multiset<BigNum, std::less<>> s;
s.insert(42);
  // Construct BigNum(int) in-place in a new node
  // Find the insertion point via less(BigNum, BigNum)
  // Attach the node to the tree
std::flat_multiset<BigNum, std::less<>> s;
s.insert(42);
   // Find the insertion point via less(int, BigNum)
   // Construct BigNum(int) in-place in the vector

template<class T, class C>
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());
char cstr[] = "too long to fit in the small string buffer";

std::pmr::multiset<std::pmr::string, std::less<>> s(&mr);
s.emplace(cstr);
  // Construct string(cstr, &mr) in-place in a new node
  // Find the insertion point via less(string, string)
  // Attach the node to the tree
s.insert(cstr);
  // Construct string(cstr, &mr) in-place in a new node
  // Find the insertion point via less(string, string)
  // Attach the node to the tree

std::pmr::multiset<std::pmr::string, std::less<>> s(&mr);
s.emplace(cstr);
  // Construct string(cstr, &mr) in-place in a new node
  // Find the insertion point via less(string, string)
  // Attach the node to the tree
s.insert(cstr);
  // Construct string(cstr, &mr) in-place in a new node
  // Find the insertion point via less(string, string)
  // Attach the node to the tree

PmrFlatMultiset<std::pmr::string, std::less<>> fs(&mr);
fs.emplace(cstr);
  // Construct string(cstr) in a temporary t
  //   (throws bad_alloc)
  // Find the insertion point via less(string, string)
  // Move-construct string(std::move(t)) into the vector
fs.insert(cstr);
   // Construct string(cstr) in the argument slot
   //   (throws bad_alloc)
   // Find the insertion point via less(string, string)
   // Move-construct string(string&&) into the vector

PmrFlatMultiset<std::pmr::string, std::less<>> fs(&mr);
fs.emplace(cstr);
  // Construct string(cstr) in a temporary t
  //   (throws bad_alloc)
  // Find the insertion point via less(string, string)
  // Move-construct string(std::move(t)) into the vector
fs.insert(cstr);
   // Find the insertion point via less(char*, string)
   // Construct string(cstr, &mr) into the vector
   //   (OK, does not throw)

[P2363] explains why they chose not to add insert(K&&) to the node-based std::multiset:

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.

That last sentence is false for the vector-based flat_multiset: We cannot mitigate overheads by using emplace, because emplace must first construct t outside the vector using the default allocator (which may throw bad_alloc). emplace cannot use the proper allocator, because flat_multiset is (deliberately) not allocator-aware. Therefore we propose to add flat_multiset::insert(K&&).

4.4.1. Wording

Note: This diff assumes § 3.5.5 Wording as the starting point.

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);
iterator insert(value_type&& x);
template<class K> iterator insert(K&& x);
iterator insert(const_iterator position, const value_type& x);
iterator insert(const_iterator position, value_type&& x);
template<class K> iterator insert(const_iterator hint, K&& x);

Change [flat.multiset.modifiers] as follows:

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);

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 upper_bound(x) == upper_bound(u) is true.

x․ Effects: Inserts a new element as if by

auto it = ranges::upper_bound(c, x, compare);
c.emplace(it, std::forward<K>(x));

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

4.5. 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).

4.5.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)).

4.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."

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

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

4.8. 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 std::inplace_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)

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

4.9. Stable sorting

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

4.10. insert_range(sorted_unique, rg)

The multi-element insertion API consists of these five overloads:

insert(first, last);                 // 1a
insert(il);                          // 2a
insert_range(rg);                    // 3a

insert(sorted_unique, first, last);  // 1b
insert(sorted_unique, il);           // 2b

insert_range(sorted_unique, rg) // 3c 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;