Initially I thought if append_range is not supported then insert_range is unlikely too, but now I begin to believe it's a good idea to use a container method as long as it is required in container.reqmts or sequence.reqmts)). The same goes for cbegin etc.

I think there is no need to use make_obj_using_allocator for C(another,al) and C(al), as these constructors are required for allocator-aware containers. I believe a container that uses_allocator_v the allocator should also support these constructors.

For C(first,last,al), C(from_range...,al) and C(ilist,al), however, I realize that make_obj_using_allocator is not capable. As a failure to construct with these arguments are considered ill-formed by make_obj_using_allocator.

https://eel.is/c++draft/allocator.uses.construction#5.4.sentence-1
Otherwise, the program is ill-formed.

But the flat_set constructors only say the container should be constructed with the allocator, then behave the same as without the allocator (inserting the range). So these constructors should be valid even if the container doesn't directly support these constructions.

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

A conservative fix would be constructing the container using only _Al, then assigning the range then sorting in the constructor body. I'm not sure whether we should try to utilize these C(...,al) constructors and fall back to the conservative approach though.

(In contrast, other adapters like stack is much more direct about container construction:

template<class InputIterator, class Alloc>
stack(InputIterator first, InputIterator last, const Alloc& alloc);
Effects: Initializes c with first as the first argument, last as the second argument, and alloc as the third argument.

This is related to #4059. Aside from exception guarantee, I think the standard is also not clear enough about how should the invariant be restored.

If any member function in [flat.set.defn] exits via an exception, the invariant is restored.
[Note 2: This can result in the flat_set's being emptied. — end note]

Should flat_meow be unchanged, or should flat_meow be emptied? I think the standard should really clarify this. At least for erasion and single-element insertion, strong-guarantee is possible if the underlying container can provide strong-guarantee too.

The two _New_end were sharing different meanings in _Erase_dupes_if_not_multi and here. Renamed to common _End here to match with other methods (the variable in _Erase_dupes_if_not_multi is removed)

regaining cend is necessary, as _Erase_dupes_if_not_multi may invalidate end. I think for clarity we'd better use _Is_sorted(_Mycont.cbegin(), _Mycont.cend()) for container-scale checks. (update: introduced _Is_sorted(container) for better clarity)

(Further, should we consistently use _Mycont.[c]begin/end rather than [c]begin/end in the methods to reduce a layer of indirection?)

See [flatset.overview] is slightly problematic, as this is also for flat_multiset; not dealt with in this pr. (Is it ok to remove these references?)

But we believe that the most common use-case for both heterogeneous lookup and insertion is the case when key_type and heterogeneous key represents the same thing like for std::string and std::string_view, which gives correct and unambiguous conversion from the heterogeneous key to key_type.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2363r2.html#dec_conv_comp_consistency

The current implementation works well when key_type and heterogeneous key represents the same thing, and the assertion is based on this.

It's possible to support weirder (and much less useful) cases - find(_Val) == find(_Keyval) (for example, both == end()), but lower_bound(_Val) != lower_bound(_Keyval). That will relax the assertion to only !contains(_Keyval) as required by the standard, and the _Keyval should be forwarded to another _Emplace_hint function for correct insertion position. This is, however, unfair for common cases, and will make the performance a lot worse.

(And the hint is effectively useless for inconsistent cases, as at least one full bound-search is needed for either deciding the existence of the heterogeneous key, or deciding the insertion position of _Keyval.)

What does the standard say about Conversion and comparison consistency?

    void insert(initializer_list<_Kty> _Ilist) {
        _Insert_range<false>(_Ilist.begin(), _Ilist.end());
    }

    void insert(_Tsorted, initializer_list<_Kty> _Ilist) {
        _Insert_range<true>(_Ilist.begin(), _Ilist.end());
    }

These methods can use cont.insert(end(), ilist) for insertion; temporarily kept unchanged for tidiness.

It might be clearer to name this function as _Is_Tsorted, if T means "type-dependent".

_Tsorted->_Tsorted_tag
_Is_sorted->_Is_Tsorted
_Msg_not_sorted->_Msg_not_Tsorted

However I'm not very sure about the original meaning of T in _Tsorted...

This optimization was valid, but I think we'd better put this off after solving the remaining invariant-safety issues in insert/erase methods. (And "bool _Noexcept = false" might not be the most suitable form.)

We use TRANSITION for things that need to ship in main, but that we hope to improve in the future. For things that must be addressed before this feature is officially merged, it seems that we should use FIXME. The distinction is that we never allow "FIXME" to reach main.

(Mentioning this for the future, but I didn't push changes here.)