flat_map.h

/*
 * Boost Software License - Version 1.0 - August 17th, 2003
 *
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

#pragma once

// This is an implementation of C++23 "std::flat_map" as specified in P0429,
// with some modifications as specified in P2767.

#include <stddef.h>
#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <utility>
#include <vector>

#if __cplusplus >= 202002L
#include <compare>
#include <concepts>
#include <ranges>
#endif // __cplusplus >= 202002L

#ifndef SG14_FLAT_MAP_THROW
#include <stdexcept>
#define SG14_FLAT_MAP_THROW(x) throw (x)
#endif

namespace sg14 {

namespace flatmap_detail {
    template<class It>
    using is_random_access_iterator = std::is_convertible<
        typename std::iterator_traits<It>::iterator_category,
        std::random_access_iterator_tag
    >;

    template<int I> struct priority_tag : priority_tag<I-1> {};
    template<> struct priority_tag<0> {};

    // As proposed in P0591R4. Guaranteed copy elision makes this do the right thing.
    template<class T, class Alloc, class... Args, class = typename std::enable_if<
        std::uses_allocator<T, Alloc>::value && std::is_constructible<T, std::allocator_arg_t, const Alloc&, Args&&...>::value
    >::type>
    T make_obj_using_allocator_(priority_tag<3>, const Alloc& alloc, Args&&... args) {
        return T(std::allocator_arg, alloc, static_cast<Args&&>(args)...);
    }
    template<class T, class Alloc, class... Args, class = typename std::enable_if<
        std::uses_allocator<T, Alloc>::value && std::is_constructible<T, Args&&..., const Alloc&>::value
    >::type>
    T make_obj_using_allocator_(priority_tag<2>, const Alloc& alloc, Args&&... args) {
        return T(static_cast<Args&&>(args)..., alloc);
    }
    template<class T, class Alloc, class... Args, class = typename std::enable_if<
        !std::uses_allocator<T, Alloc>::value && std::is_constructible<T, Args&&...>::value
    >::type>
    T make_obj_using_allocator_(priority_tag<1>, const Alloc&, Args&&... args) {
        return T(static_cast<Args&&>(args)...);
    }
    template<class T, class Alloc, class... Args>
    T make_obj_using_allocator_(priority_tag<0>, const Alloc&, Args&&...) {
        static_assert(sizeof(T)==0, "this request for uses-allocator construction is ill-formed");
    }
    template<class T, class Alloc, class... Args>
    T make_obj_using_allocator(const Alloc& alloc, Args&&... args) {
        return make_obj_using_allocator_<T>(priority_tag<3>(), alloc, static_cast<Args&&>(args)...);
    }

    template<class InputIterator>
    using iter_key_type = typename std::remove_const<typename std::iterator_traits<InputIterator>::value_type::first_type>::type;

    template<class InputIterator>
    using iter_mapped_type = typename std::iterator_traits<InputIterator>::value_type::second_type;

    template<class...> using void_t = void;

    template<class A, class = void>
    struct qualifies_as_allocator : std::false_type {};
    template<class A>
    struct qualifies_as_allocator<A, void_t<
        typename A::value_type,
        decltype(std::declval<A&>().allocate(size_t{}))
    >> : std::true_type {};

    template<class It>
    using qualifies_as_input_iterator = std::integral_constant<bool, !std::is_integral<It>::value>;

    template<class... Its>
    void swap_together(size_t i, size_t j, Its... its)
    {
        using std::swap;
        int dummy[] = {
            0,
            (std::iter_swap(its + i, its + j), 0) ...
        };
        (void)dummy;
    }

    template<class Predicate, class Head, class... Rest>
    size_t partition_together(Predicate& pred, size_t left, size_t right, Head head, const Rest... rest) {
        while (left < right) {
            while (left != right && pred(*(head + left))) ++left;
            while (left != right && !pred(*(head + (right-1)))) --right;
            if (left + 1 < right) {
                flatmap_detail::swap_together(left, right-1, head, rest...);
                ++left;
                --right;
            }
        }
        return right;
    }

    template<class Compare, class Head, class... Rest>
    void sort_together(Compare& less, size_t left, size_t right, Head head, Rest... rest) {
        if (right - left >= 3) {
            size_t pivot_idx = left + (right - left) / 2;
            // Swap the pivot element all the way to the right.
            if (pivot_idx != right - 1) {
                flatmap_detail::swap_together(pivot_idx, right-1, head, rest...);
            }
            const auto& pivot_elt = *(head + (right-1));
            auto less_than_pivot = [&](const auto& x) -> bool {
                return less(x, pivot_elt);
            };
            size_t correct_pivot_idx = flatmap_detail::partition_together(less_than_pivot, left, right-1, head, rest...);
            if (correct_pivot_idx != right-1) {
                flatmap_detail::swap_together(correct_pivot_idx, right-1, head, rest...);
            }
            flatmap_detail::sort_together(less, left, correct_pivot_idx, head, rest...);
            flatmap_detail::sort_together(less, correct_pivot_idx+1, right, head, rest...);
        } else if (right - left == 2) {
            if (less(*(head + left), *(head + (left+1)))) {
                // nothing to do
            } else {
                flatmap_detail::swap_together(left, left+1, head, rest...);
            }
        }
    }

    template<class Compare, class Head, class... Rest>
    void sort_together(Compare less, Head& head, Rest&... rest) {
        flatmap_detail::sort_together(less, 0, head.size(), head.begin(), rest.begin()...);
    }

    template<class It, class It2, class Compare>
    It unique_helper(It first, It last, It2 mapped, const Compare& compare) {
        It dfirst = first;
        It2 dmapped = mapped;
        while (first != last) {
            It next = first;
            ++next;
            if ((next != last) && !bool(compare(*first, *next))) {
                // "next" is a duplicate of "first", so do not preserve "first"
            } else {
                // do preserve "first"
                if (first != dfirst) {
                    *dfirst = std::move(*first);
                    *dmapped = std::move(*mapped);
                }
                ++dfirst;
                ++dmapped;
            }
            first = next;
            ++mapped;
        }
        return dfirst;
    }

    template<class FS>
    struct InvariantRestoringGuard {
        FS *self_;
        explicit InvariantRestoringGuard(FS *self) : self_(self) {}
        void complete() {
            self_ = nullptr;
        }
        ~InvariantRestoringGuard() {
            if (self_ != nullptr) {
                self_->clear();
            }
        }
    };

    template<class, class> class iter;
    template<class K, class V> iter<K, V> make_iterator(K, V);

    template<class Reference>
    struct arrow_proxy {
        Reference *operator->() { return std::addressof(data_); }

        template<class, class> friend class iter;

        Reference data_;
    };

    template<class KeyIt, class MappedIt>
    class iter {
    public:
        using difference_type = ptrdiff_t;
        using value_type = std::pair<typename std::iterator_traits<KeyIt>::value_type, typename std::iterator_traits<MappedIt>::value_type>;
        using reference = std::pair<typename std::iterator_traits<KeyIt>::reference, typename std::iterator_traits<MappedIt>::reference>;
        using pointer = arrow_proxy<reference>;
        using iterator_category = std::random_access_iterator_tag;

        iter() = default;
        iter(iter&&) = default;
        iter(const iter&) = default;
        iter& operator=(iter&&) = default;
        iter& operator=(const iter&) = default;
        ~iter() = default;

        // This is the iterator-to-const_iterator implicit conversion.
        template<class CK, class CM,
                 class = typename std::enable_if<std::is_convertible<CK, KeyIt>::value>::type,
                 class = typename std::enable_if<std::is_convertible<CM, MappedIt>::value>::type>
        iter(const iter<CK, CM>& other) : kit_(other.private_impl_getkey()), vit_(other.private_impl_getmapped()) {}

        reference operator*() const {
            return reference{*kit_, *vit_};
        }

        pointer operator->() const {
            return arrow_proxy<reference>{reference{*kit_, *vit_}};
        }

        friend auto iter_move(const iter& it) {
#if __cpp_lib_ranges >= 201911L
            using K = decltype(std::ranges::iter_move(it.kit_));
            using V = decltype(std::ranges::iter_move(it.vit_));
            return std::pair<K, V>(std::ranges::iter_move(it.kit_), std::ranges::iter_move(it.vit_));
#else
            using K = decltype(std::move(*it.kit_));
            using V = decltype(std::move(*it.vit_));
            return std::pair<K, V>(std::move(*it.kit_), std::move(*it.vit_));
#endif
        }

        iter& operator++() { ++kit_; ++vit_; return *this; }
        iter& operator--() { --kit_; --vit_; return *this; }
        iter operator++(int) { iter result(*this); ++*this; return result; }
        iter operator--(int) { iter result(*this); --*this; return result; }
        iter& operator+=(ptrdiff_t n) { kit_ += n; vit_ += n; return *this; }
        iter& operator-=(ptrdiff_t n) { kit_ -= n; vit_ -= n; return *this; }
        reference operator[](ptrdiff_t n) const { return *(*this + n); }
        friend iter operator+(iter it, ptrdiff_t n) { it += n; return it; }
        friend iter operator+(ptrdiff_t n, iter it) { it += n; return it; }
        friend iter operator-(iter it, ptrdiff_t n) { it -= n; return it; }
        friend ptrdiff_t operator-(const iter& it, const iter& jt) { return ptrdiff_t(it.kit_ - jt.kit_); }
        friend bool operator==(const iter& a, const iter& b) { return a.kit_ == b.kit_; }
        friend bool operator!=(const iter& a, const iter& b) { return !(a.kit_ == b.kit_); }
        friend bool operator<(const iter& a, const iter& b) { return a.kit_ < b.kit_; }
        friend bool operator<=(const iter& a, const iter& b) { return !(b.kit_ < a.kit_); }
        friend bool operator>(const iter& a, const iter& b) { return b.kit_ < a.kit_; }
        friend bool operator>=(const iter& a, const iter& b) { return !(a.kit_ < b.kit_); }

        KeyIt private_impl_getkey() const { return kit_; }
        MappedIt private_impl_getmapped() const { return vit_; }

    private:
        template<class K, class V>
        friend iter<K, V> make_iterator(K, V);

        explicit iter(KeyIt&& kit, MappedIt&& vit)
            : kit_(static_cast<KeyIt&&>(kit)), vit_(static_cast<MappedIt&&>(vit)) {}
        KeyIt kit_;
        MappedIt vit_;
    };

    template<class K, class V>
    iter<K, V> make_iterator(K kit, V vit) {
        return iter<K, V>(static_cast<K&&>(kit), static_cast<V&&>(vit));
    }

} // namespace flatmap_detail

#ifndef SG14_HAS_SORTED_UNIQUE
#define SG14_HAS_SORTED_UNIQUE

struct sorted_unique_t { explicit sorted_unique_t() = default; };

#if defined(__cpp_inline_variables)
inline
#endif
constexpr sorted_unique_t sorted_unique {};

#endif // SG14_HAS_SORTED_UNIQUE

template<
    class Key,
    class Mapped,
    class Compare = std::less<Key>,
    class KeyContainer = std::vector<Key>,
    class MappedContainer = std::vector<Mapped>
>
class flat_map {
    static_assert(flatmap_detail::is_random_access_iterator<typename KeyContainer::iterator>::value, "");
    static_assert(flatmap_detail::is_random_access_iterator<typename MappedContainer::iterator>::value, "");
    static_assert(std::is_same<Key, typename KeyContainer::value_type>::value, "");
    static_assert(std::is_same<Mapped, typename MappedContainer::value_type>::value, "");
    static_assert(!std::is_const<KeyContainer>::value && !std::is_const<Key>::value, "");
    static_assert(!std::is_const<MappedContainer>::value && !std::is_const<Mapped>::value, "");
    static_assert(!std::is_reference<KeyContainer>::value && !std::is_reference<Key>::value, "");
    static_assert(!std::is_reference<MappedContainer>::value && !std::is_reference<Mapped>::value, "");
    static_assert(std::is_convertible<decltype(std::declval<const Compare&>()(std::declval<const Key&>(), std::declval<const Key&>())), bool>::value, "");
#if defined(__cpp_lib_is_swappable)
    static_assert(std::is_nothrow_swappable<KeyContainer>::value, "");
    static_assert(std::is_nothrow_swappable<MappedContainer>::value, "");
#endif
public:
    using key_type = Key;
    using mapped_type = Mapped;
    using value_type = std::pair<const Key, Mapped>;
    using key_compare = Compare;
    using const_key_reference = typename KeyContainer::const_reference;
    using mapped_reference = typename MappedContainer::reference;
    using const_mapped_reference = typename MappedContainer::const_reference;
    using reference = std::pair<const_key_reference, mapped_reference>;
    using const_reference = std::pair<const_key_reference, const_mapped_reference>;
    using size_type = size_t; // TODO: this should be KeyContainer::size_type
    using difference_type = ptrdiff_t; // TODO: this should be KeyContainer::difference_type
    using iterator = flatmap_detail::iter<typename KeyContainer::const_iterator, typename MappedContainer::iterator>;
    using const_iterator = flatmap_detail::iter<typename KeyContainer::const_iterator, typename MappedContainer::const_iterator>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using key_container_type = KeyContainer;
    using mapped_container_type = MappedContainer;

    struct value_compare {
        explicit value_compare(Compare c): comp_(std::move(c)) {}
        bool operator()(const_reference x, const_reference y) const {
            return comp_(x.first, y.first);
        }
    private:
        Compare comp_;
    };

    struct containers {
        KeyContainer keys;
        MappedContainer values;
    };

// =========================================================== CONSTRUCTORS
// This is all one massive overload set!

    flat_map() = default;

    explicit flat_map(const Compare& comp)
        : compare_(comp) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(const Compare& comp, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a)),
          compare_(comp) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    explicit flat_map(const Alloc& a)
        : flat_map(Compare(), a) {}

#if __cpp_lib_ranges >= 201911L && __cpp_lib_ranges_to_container >= 202202L
    template<std::ranges::input_range R>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
    flat_map(std::from_range_t, R&& rg)
    {
        this->insert_range(static_cast<R&&>(rg));
    }

    template<std::ranges::input_range R, class Alloc>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type> &&
                 std::uses_allocator_v<KeyContainer, Alloc> &&
                 std::uses_allocator_v<MappedContainer, Alloc>
    flat_map(std::from_range_t, R&& rg, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a))
    {
        this->insert_range(static_cast<R&&>(rg));
    }

    template<std::ranges::input_range R>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
    flat_map(std::from_range_t, R&& rg, const Compare& comp)
        : compare_(comp)
    {
        this->insert_range(static_cast<R&&>(rg));
    }

    template<std::ranges::input_range R, class Alloc>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type> &&
                 std::uses_allocator_v<KeyContainer, Alloc> &&
                 std::uses_allocator_v<MappedContainer, Alloc>
    flat_map(std::from_range_t, R&& rg, const Compare& comp, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a)),
          compare_(comp)
    {
        this->insert_range(static_cast<R&&>(rg));
    }
#endif // __cpp_lib_ranges >= 201911L && __cpp_lib_ranges_to_container >= 202202L

    template<class InputIterator,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type>
    flat_map(InputIterator first, InputIterator last, const Compare& comp = Compare())
        : compare_(comp)
    {
        this->insert(first, last);
    }

    template<class InputIterator, class Alloc,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type,
             class = typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value>::type,
             class = typename std::enable_if<std::uses_allocator<MappedContainer, Alloc>::value>::type>
    flat_map(InputIterator first, InputIterator last, const Compare& comp, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a)),
          compare_(comp)
    {
        this->insert(first, last);
    }

    template<class InputIterator, class Alloc,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type,
             class = typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value>::type,
             class = typename std::enable_if<std::uses_allocator<MappedContainer, Alloc>::value>::type>
    flat_map(InputIterator first, InputIterator last, const Alloc& a)
        : flat_map(first, last, Compare(), a) {}

    template<class InputIterator,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type>
    flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Compare& comp = Compare())
        : compare_(comp)
    {
        this->insert(sorted_unique, first, last);
    }

    template<class InputIterator, class Alloc,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type,
             class = typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value>::type,
             class = typename std::enable_if<std::uses_allocator<MappedContainer, Alloc>::value>::type>
    flat_map(sorted_unique_t, InputIterator first, InputIterator last, const Compare& comp, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a)),
          compare_(comp)
    {
        this->insert(sorted_unique, first, last);
    }

    template<class InputIterator, class Alloc,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type,
             class = typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value>::type,
             class = typename std::enable_if<std::uses_allocator<MappedContainer, Alloc>::value>::type>
    flat_map(sorted_unique_t s, InputIterator first, InputIterator last, const Alloc& a)
        : flat_map(s, first, last, Compare(), a) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(flat_map&& m, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a, std::move(m.keys_))),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a, std::move(m.values_))),
          compare_(std::move(m.compare_)) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(const flat_map& m, const Alloc& a)
        : keys_(flatmap_detail::make_obj_using_allocator<KeyContainer>(a, m.keys_)),
          values_(flatmap_detail::make_obj_using_allocator<MappedContainer>(a, m.values_)),
          compare_(m.compare_) {}

    flat_map(std::initializer_list<value_type> il)
        : flat_map(il.begin(), il.end()) {}

    flat_map(std::initializer_list<value_type> il, const Compare& comp)
        : flat_map(il.begin(), il.end(), comp) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(std::initializer_list<value_type> il, const Compare& comp, const Alloc& a)
        : flat_map(il.begin(), il.end(), comp, a) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(std::initializer_list<value_type> il, const Alloc& a)
        : flat_map(il.begin(), il.end(), Compare(), a) {}

    flat_map(sorted_unique_t s, std::initializer_list<value_type> il, const Compare& comp = Compare())
        : flat_map(s, il.begin(), il.end(), comp) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(sorted_unique_t s, std::initializer_list<value_type> il, const Compare& comp, const Alloc& a)
        : flat_map(s, il.begin(), il.end(), comp, a) {}

    template<class Alloc,
             typename std::enable_if<std::uses_allocator<KeyContainer, Alloc>::value && std::uses_allocator<MappedContainer, Alloc>::value, int>::type = 0>
    flat_map(sorted_unique_t s, std::initializer_list<value_type> il, const Alloc& a)
        : flat_map(s, il.begin(), il.end(), Compare(), a) {}

// ========================================================== OTHER MEMBERS

    flat_map& operator=(std::initializer_list<value_type> il) {
        this->clear();
        this->insert(il.begin(), il.end());
        return *this;
    }

    iterator begin() noexcept { return flatmap_detail::make_iterator(keys_.begin(), values_.begin()); }
    const_iterator begin() const noexcept { return flatmap_detail::make_iterator(keys_.begin(), values_.begin()); }
    iterator end() noexcept { return flatmap_detail::make_iterator(keys_.end(), values_.end()); }
    const_iterator end() const noexcept { return flatmap_detail::make_iterator(keys_.end(), values_.end()); }

    const_iterator cbegin() const noexcept { return flatmap_detail::make_iterator(keys_.begin(), values_.begin()); }
    const_iterator cend() const noexcept { return flatmap_detail::make_iterator(keys_.end(), values_.end()); }

    reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
    reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }

    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }

#if __cplusplus >= 201703L
    [[nodiscard]]
#endif
    bool empty() const noexcept { return keys_.empty(); }
    size_type size() const noexcept { return keys_.size(); }
    size_type max_size() const noexcept { return std::min<size_type>(keys_.max_size(), values_.max_size()); }

    mapped_reference operator[](const Key& x) {
        return try_emplace(x).first->second;
    }

    mapped_reference operator[](Key&& x) {
        return try_emplace(static_cast<Key&&>(x)).first->second;
    }

    mapped_reference at(const Key& k) {
        auto it = this->find(k);
        if (it == end()) {
            SG14_FLAT_MAP_THROW(std::out_of_range("flat_map::at"));
        }
        return it->second;
    }

    const_mapped_reference at(const Key& k) const {
        auto it = this->find(k);
        if (it == end()) {
            SG14_FLAT_MAP_THROW(std::out_of_range("flat_map::at"));
        }
        return it->second;
    }

    template<class... Args, class = decltype(std::pair<Key, Mapped>(std::declval<Args&&>()...), void())>
    std::pair<iterator, bool> emplace(Args&&... args) {
        std::pair<Key, Mapped> t(static_cast<Args&&>(args)...);
        auto it = this->lower_bound(t.first);
        if (it == end() || compare_(t.first, it->first)) {
            auto kit = it.private_impl_getkey();
            auto vit = it.private_impl_getmapped();
            // TODO: we must make this exception-safe
            kit = keys_.emplace(kit, static_cast<Key&&>(t.first));
            vit = values_.emplace(vit, static_cast<Mapped&&>(t.second));
            auto result = flatmap_detail::make_iterator(kit, vit);
            return {std::move(result), true};
        } else {
            return {it, false};
        }
    }

    template<class... Args>
    iterator emplace_hint(const_iterator, Args&&... args) {
        return this->emplace(static_cast<Args&&>(args)...).first;
    }

    std::pair<iterator, bool> insert(const value_type& x) {
        return this->emplace(x);
    }

    std::pair<iterator, bool> insert(value_type&& x) {
        return this->emplace(static_cast<value_type&&>(x));
    }

    iterator insert(const_iterator position, const value_type& x) {
        return this->emplace_hint(position, x);
    }

    iterator insert(const_iterator position, value_type&& x) {
        return this->emplace_hint(position, static_cast<value_type&&>(x));
    }

    template<class P,
             class = decltype(std::pair<Key, Mapped>(std::declval<P&&>()))>
    std::pair<iterator, bool> insert(P&& x) {
        return this->emplace(static_cast<P&&>(x));
    }

    template<class P,
             class = decltype(std::pair<Key, Mapped>(std::declval<P&&>()))>
    iterator insert(const_iterator position, P&& x) {
        return this->emplace_hint(position, static_cast<P&&>(x));
    }

    template<class InputIterator,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type>
    void insert(InputIterator first, InputIterator last) {
        // TODO: if we're inserting lots of elements, stick them at the end and then sort
        while (first != last) {
            this->insert(*first);
            ++first;
        }
    }

    template<class InputIterator,
             class = typename std::enable_if<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value>::type>
    void insert(sorted_unique_t, InputIterator first, InputIterator last) {
        // TODO: if InputIterator is bidirectional, this loop should (go backward??)
        // TODO: if we're inserting lots of elements, stick them at the end and then sort
        auto it = begin();
        while (first != last) {
            std::pair<Key, Mapped> t(*first);
            it = std::partition_point(it, this->end(), [&](const auto& elt) {
                return bool(compare_(elt.first, t.first));
            });
            if (it == this->end() || bool(compare_(t.first, it->first))) {
                it = this->emplace_hint(it, std::move(t));
            }
            ++it;
            ++first;
        }
    }

    void insert(std::initializer_list<value_type> il) {
        this->insert(il.begin(), il.end());
    }

    void insert(sorted_unique_t s, std::initializer_list<value_type> il) {
        this->insert(s, il.begin(), il.end());
    }

#if __cpp_lib_ranges >= 201911L && __cpp_lib_ranges_to_container >= 202202L
    template<std::ranges::input_range R>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
    void insert_range(R&& rg) {
        flatmap_detail::InvariantRestoringGuard<flat_map> guard(this);
        size_type oldsize = keys_.size();
        for (value_type e : rg) {
            keys_.emplace_back(std::move(e.first));
            values_.emplace_back(std::move(e.second));
        }
        if (keys_.size() != oldsize) {
            auto begin = flatmap_detail::make_iterator(keys_.begin(), values_.begin());
            auto mid = begin + oldsize;
            auto end = flatmap_detail::make_iterator(keys_.end(), values_.end());
            std::ranges::sort(mid, end, value_comp());
            std::ranges::inplace_merge(begin, mid, end, value_comp());
            auto kit = flatmap_detail::unique_helper(keys_.begin(), keys_.end(), values_.begin(), compare_);
            auto vit = values_.begin() + (kit - keys_.begin());
            keys_.erase(kit, keys_.end());
            values_.erase(vit, values_.end());
        }
        guard.complete();
    }

    template<std::ranges::input_range R>
        requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
    void insert_range(sg14::sorted_unique_t, R&& rg) {
        flatmap_detail::InvariantRestoringGuard<flat_map> guard(this);
        size_type oldsize = keys_.size();
        for (value_type e : rg) {
            keys_.emplace_back(std::move(e.first));
            values_.emplace_back(std::move(e.second));
        }
        if (keys_.size() != oldsize) {
            auto begin = flatmap_detail::make_iterator(keys_.begin(), values_.begin());
            auto mid = begin + oldsize;
            auto end = flatmap_detail::make_iterator(keys_.end(), values_.end());
            std::ranges::inplace_merge(begin, mid, end, compare_);
            auto kit = flatmap_detail::unique_helper(keys_.begin(), keys_.end(), values_.begin(), compare_);
            auto vit = values_.begin() + (kit - keys_.begin());
            keys_.erase(kit, keys_.end());
            values_.erase(vit, values_.end());
        }
        guard.complete();
    }
#endif

    containers extract() && {
        flatmap_detail::InvariantRestoringGuard<flat_map> guard(this);
        containers result{
            static_cast<KeyContainer&&>(keys_),
            static_cast<MappedContainer&&>(values_)
        };
        // Deliberately do not complete the guard.
        return result;
    }

    void replace(KeyContainer keys, MappedContainer values) {
        flatmap_detail::InvariantRestoringGuard<flat_map> guard(this);
        keys_ = static_cast<KeyContainer&&>(keys);
        values_ = static_cast<MappedContainer&&>(values);
        this->sort_and_unique_impl();
        guard.complete();
    }

    void replace(sorted_unique_t, KeyContainer keys, MappedContainer values) {
        flatmap_detail::InvariantRestoringGuard<flat_map> guard(this);
        keys_ = static_cast<KeyContainer&&>(keys);
        values_ = static_cast<MappedContainer&&>(values);
        guard.complete();
    }

    template<class... Args>
    std::pair<iterator, bool> try_emplace(const Key& k, Args&&... args) {
        auto kit = std::lower_bound(keys_.begin(), keys_.end(), k, std::ref(compare_));
        auto vit = values_.begin() + (kit - keys_.begin());
        if (kit == keys_.end() || compare_(k, *kit)) {
            kit = keys_.insert(kit, k);
            // TODO: we must make this exception-safe if the container throws
            vit = values_.emplace(vit, static_cast<Args&&>(args)...);
            return {flatmap_detail::make_iterator(kit, vit), true};
        } else {
            return {flatmap_detail::make_iterator(kit, vit), false};
        }
    }

    template<class... Args>
    std::pair<iterator, bool> try_emplace(Key&& k, Args&&... args) {
        auto kit = std::lower_bound(keys_.begin(), keys_.end(), k, std::ref(compare_));
        auto vit = values_.begin() + (kit - keys_.begin());
        if (kit == keys_.end() || compare_(k, *kit)) {
            kit = keys_.insert(kit, static_cast<Key&&>(k));
            // TODO: we must make this exception-safe if the container throws
            vit = values_.emplace(vit, static_cast<Args&&>(args)...);
            return {flatmap_detail::make_iterator(kit, vit), true};
        } else {
            return {flatmap_detail::make_iterator(kit, vit), false};
        }
    }

    // TODO: use the hint, here
    template<class... Args>
    iterator try_emplace(const_iterator, const Key& k, Args&&... args) {
        return try_emplace(k, static_cast<Args&&>(args)...).first;
    }

    // TODO: use the hint, here
    template<class... Args>
    iterator try_emplace(const_iterator, Key&& k, Args&&... args) {
        return try_emplace(static_cast<Key&&>(k), static_cast<Args&&>(args)...).first;
    }

    template<class M>
    std::pair<iterator, bool> insert_or_assign(const Key& k, M&& obj) {
        static_assert(std::is_assignable<Mapped&, M>::value, "");
        static_assert(sizeof( Mapped(static_cast<M&&>(obj)) ) != 0, "");
        auto result = try_emplace(k, static_cast<M&&>(obj));
        if (!result.second) {
            result.first->second = static_cast<M&&>(obj);
        }
        return result;
    }

    template<class M>
    std::pair<iterator, bool> insert_or_assign(Key&& k, M&& obj) {
        static_assert(std::is_assignable<Mapped&, M>::value, "");
        static_assert(sizeof( Mapped(static_cast<M&&>(obj)) ) != 0, "");
        auto result = try_emplace(static_cast<Key&&>(k), static_cast<M&&>(obj));
        if (!result.second) {
            result.first->second = static_cast<M&&>(obj);
        }
        return result;
    }

    // TODO: use the hint, here
    template<class M>
    iterator insert_or_assign(const_iterator, const Key& k, M&& obj) {
        static_assert(std::is_assignable<Mapped&, M>::value, "");
        static_assert(sizeof( Mapped(static_cast<M&&>(obj)) ) != 0, "");
        auto result = try_emplace(k, static_cast<M&&>(obj));
        if (!result.second) {
            result.first->second = static_cast<M&&>(obj);
        }
        return result.first;
    }

    // TODO: use the hint, here
    template<class M>
    iterator insert_or_assign(const_iterator, Key&& k, M&& obj) {
        static_assert(std::is_assignable<Mapped&, M>::value, "");
        static_assert(sizeof( Mapped(static_cast<M&&>(obj)) ) != 0, "");
        auto result = try_emplace(static_cast<Key&&>(k), static_cast<M&&>(obj));
        if (!result.second) {
            result.first->second = static_cast<M&&>(obj);
        }
        return result.first;
    }

    iterator erase(iterator position) {
        auto kit = position.private_impl_getkey();
        auto vit = position.private_impl_getmapped();
        // TODO: what if either of these next two lines throws an exception?
        auto kitmut = keys_.erase(kit);
        auto vitmut = values_.erase(vit);
        return flatmap_detail::make_iterator(kitmut, vitmut);
    }

    iterator erase(const_iterator position) {
        auto kit = position.private_impl_getkey();
        auto vit = position.private_impl_getmapped();
        // TODO: what if either of these next two lines throws an exception?
        auto kitmut = keys_.erase(kit);
        auto vitmut = values_.erase(vit);
        return flatmap_detail::make_iterator(kitmut, vitmut);
    }

    size_type erase(const Key& k) {
        auto it = this->find(k);
        if (it != this->end()) {
            this->erase(it);
            return 1;
        }
        return 0;
    }

    iterator erase(const_iterator first, const_iterator last) {
        auto kfirst = first.private_impl_getkey();
        auto vfirst = first.private_impl_getmapped();
        auto klast = last.private_impl_getkey();
        auto vlast = last.private_impl_getmapped();
        // TODO: what if either of these next two lines throws an exception?
        auto kitmut = keys_.erase(kfirst, klast);
        auto vitmut = values_.erase(vfirst, vlast);
        return flatmap_detail::make_iterator(kitmut, vitmut);
    }

    void swap(flat_map& fm) noexcept
#if defined(__cpp_lib_is_swappable)
        (std::is_nothrow_swappable<Compare>::value)
#endif
    {
        using std::swap;
        swap(compare_, fm.compare_);
        swap(keys_, fm.keys_);
        swap(values_, fm.values_);
    }

    friend void swap(flat_map& a, flat_map& b) noexcept(noexcept(a.swap(b))) {
        a.swap(b);
    }

    void clear() noexcept {
        keys_.clear();
        values_.clear();
    }

    key_compare key_comp() const {
        return compare_;
    }

    value_compare value_comp() const {
        return value_compare(compare_);
    }

    const KeyContainer& keys() const {
        return keys_;
    }

    MappedContainer& values() {
        return values_;
    }

    const MappedContainer& values() const {
        return values_;
    }

    iterator find(const Key& k) {
        auto it = this->lower_bound(k);
        if (it == end() || compare_(k, it->first)) {
            return end();
        }
        return it;
    }

    const_iterator find(const Key& k) const {
        auto it = this->lower_bound(k);
        if (it == end() || compare_(k, it->first)) {
            return end();
        }
        return it;
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    iterator find(const K& x) {
        auto it = this->lower_bound(x);
        if (it == end() || compare_(x, it->first)) {
            return end();
        }
        return it;
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    const_iterator find(const K& x) const {
        auto it = this->lower_bound(x);
        if (it == end() || compare_(x, it->first)) {
            return end();
        }
        return it;
    }

    size_type count(const Key& k) const {
        return this->contains(k) ? 1 : 0;
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    size_type count(const K& x) const {
        return this->contains(x) ? 1 : 0;
    }

    bool contains(const Key& k) const {
        return this->find(k) != this->end();
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    bool contains(const K& x) const {
        return this->find(x) != this->end();
    }

    iterator lower_bound(const Key& k) {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, k));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    const_iterator lower_bound(const Key& k) const {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, k));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    iterator lower_bound(const K& x) {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, x));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    const_iterator lower_bound(const K& x) const {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, x));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    iterator upper_bound(const Key& k) {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return !bool(compare_(k, elt));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    const_iterator upper_bound(const Key& k) const {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return !bool(compare_(k, elt));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    iterator upper_bound(const K& x) {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return !bool(compare_(x, elt));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    const_iterator upper_bound(const K& x) const {
        auto kit = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return !bool(compare_(x, elt));
        });
        auto vit = values_.begin() + (kit - keys_.begin());
        return flatmap_detail::make_iterator(kit, vit);
    }

    std::pair<iterator, iterator> equal_range(const Key& k) {
        auto kit1 = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, k));
        });
        auto kit2 = std::partition_point(kit1, keys_.end(), [&](const auto& elt) {
            return !bool(compare_(k, elt));
        });
        auto vit1 = values_.begin() + (kit1 - keys_.begin());
        auto vit2 = values_.begin() + (kit2 - keys_.begin());
        return {
            flatmap_detail::make_iterator(kit1, vit1),
            flatmap_detail::make_iterator(kit2, vit2)
        };
    }

    std::pair<const_iterator, const_iterator> equal_range(const Key& k) const {
        auto kit1 = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, k));
        });
        auto kit2 = std::partition_point(kit1, keys_.end(), [&](const auto& elt) {
            return !bool(compare_(k, elt));
        });
        auto vit1 = values_.begin() + (kit1 - keys_.begin());
        auto vit2 = values_.begin() + (kit2 - keys_.begin());
        return {
            flatmap_detail::make_iterator(kit1, vit1),
            flatmap_detail::make_iterator(kit2, vit2)
        };
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    std::pair<iterator, iterator> equal_range(const K& x) {
        auto kit1 = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, x));
        });
        auto kit2 = std::partition_point(kit1, keys_.end(), [&](const auto& elt) {
            return !bool(compare_(x, elt));
        });
        auto vit1 = values_.begin() + (kit1 - keys_.begin());
        auto vit2 = values_.begin() + (kit2 - keys_.begin());
        return {
            flatmap_detail::make_iterator(kit1, vit1),
            flatmap_detail::make_iterator(kit2, vit2)
        };
    }

    template<class K,
             class Compare_ = Compare, class = typename Compare_::is_transparent>
    std::pair<const_iterator, const_iterator> equal_range(const K& x) const {
        auto kit1 = std::partition_point(keys_.begin(), keys_.end(), [&](const auto& elt) {
            return bool(compare_(elt, x));
        });
        auto kit2 = std::partition_point(kit1, keys_.end(), [&](const auto& elt) {
            return !bool(compare_(x, elt));
        });
        auto vit1 = values_.begin() + (kit1 - keys_.begin());
        auto vit2 = values_.begin() + (kit2 - keys_.begin());
        return {
            flatmap_detail::make_iterator(kit1, vit1),
            flatmap_detail::make_iterator(kit2, vit2)
        };
    }

    friend bool operator==(const flat_map& a, const flat_map& b) {
        return std::equal(a.begin(), a.end(), b.begin(), b.end());
    }

#if __cplusplus >= 202002L && defined(__cpp_lib_three_way_comparison) && __cpp_lib_three_way_comparison >= 201907L
    friend auto operator<=>(const flat_map& a, const flat_map& b) {
        return std::lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end());
    }
#else
    friend bool operator<(const flat_map& a, const flat_map& b) {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
    }
    friend bool operator>(const flat_map& a, const flat_map& b) { return (b < a); }
    friend bool operator<=(const flat_map& a, const flat_map& b) { return !(b < a); }
    friend bool operator>=(const flat_map& a, const flat_map& b) { return !(a < b); }
    friend bool operator!=(const flat_map& a, const flat_map& b) { return !(a == b); }
#endif

private:
    void sort_and_unique_impl() {
        flatmap_detail::sort_together(compare_, keys_, values_);
        auto kit = flatmap_detail::unique_helper(keys_.begin(), keys_.end(), values_.begin(), compare_);
        auto vit = values_.begin() + (kit - keys_.begin());
        auto it = flatmap_detail::make_iterator(kit, vit);
        this->erase(it, end());
    }

    KeyContainer keys_;
    MappedContainer values_;
    Compare compare_;
};

#if defined(__cpp_deduction_guides)

template<class InputIterator,
         class Key = flatmap_detail::iter_key_type<InputIterator>,
         class T = flatmap_detail::iter_mapped_type<InputIterator>,
         class Compare = std::less<Key>,
         class = std::enable_if_t<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value && !flatmap_detail::qualifies_as_allocator<Compare>::value>>
flat_map(InputIterator, InputIterator, Compare = Compare())
    -> flat_map<Key, T, Compare>;

template<class InputIterator,
         class Key = flatmap_detail::iter_key_type<InputIterator>,
         class T = flatmap_detail::iter_mapped_type<InputIterator>,
         class Compare = std::less<Key>,
         class = std::enable_if_t<flatmap_detail::qualifies_as_input_iterator<InputIterator>::value && !flatmap_detail::qualifies_as_allocator<Compare>::value>>
flat_map(sorted_unique_t, InputIterator, InputIterator, Compare = Compare())
    -> flat_map<Key, T, Compare>;

#if __cpp_lib_ranges >= 201911L && __cpp_lib_ranges_to_container >= 202202L
template<std::ranges::input_range R,
         class Key = flatmap_detail::iter_key_type<std::ranges::iterator_t<R>>,
         class T = flatmap_detail::iter_mapped_type<std::ranges::iterator_t<R>>,
         class Compare = std::less<Key>>
flat_map(std::from_range_t, R&&, Compare = Compare())
    -> flat_map<Key, T, Compare>;
#endif // __cpp_lib_ranges >= 201911L && __cpp_lib_ranges_to_container >= 202202L

#endif // __cpp_deduction_guides

} // namespace sg14