SortedMap.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Containers/Map.h"
#include "Algo/BinarySearch.h"
#include "Algo/Sort.h"
#include "UObject/NameTypes.h"
 
template <typename InKeyType, typename InValueType, typename ArrayAllocator /*= FDefaultAllocator*/, typename SortPredicate /*= TLess<KeyType>*/ >
class TSortedMap
{
    template <typename OtherKeyType, typename OtherValueType, typename OtherArrayAllocator, typename OtherSortPredicate>
    friend class TSortedMap;
 
public:
    typedef InKeyType      KeyType;
    typedef InValueType    ValueType;
    typedef typename TTypeTraits<KeyType  >::ConstPointerType KeyConstPointerType;
    typedef typename TTypeTraits<KeyType  >::ConstInitType    KeyInitType;
    typedef typename TTypeTraits<ValueType>::ConstInitType    ValueInitType;
    typedef TPair<KeyType, ValueType> ElementType;
 
    [[nodiscard]] TSortedMap() = default;
    [[nodiscard]] TSortedMap(TSortedMap&&) = default;
    [[nodiscard]] TSortedMap(const TSortedMap&) = default;
    TSortedMap& operator=(TSortedMap&&) = default;
    TSortedMap& operator=(const TSortedMap&) = default;
 
    template<typename OtherArrayAllocator>
    [[nodiscard]] TSortedMap(TSortedMap<KeyType, ValueType, OtherArrayAllocator, SortPredicate>&& Other)
        : Pairs(MoveTemp(Other.Pairs))
    {
    }
 
    template<typename OtherArrayAllocator>
    [[nodiscard]] TSortedMap(const TSortedMap<KeyType, ValueType, OtherArrayAllocator, SortPredicate>& Other)
        : Pairs(Other.Pairs)
    {
    }
 
    [[nodiscard]] TSortedMap(std::initializer_list<TPairInitializer<const KeyType&, const ValueType&>> InitList)
    {
        this->Reserve((int32)InitList.size());
        for (const TPairInitializer<const KeyType&, const ValueType&>& Element : InitList)
        {
            this->Add(Element.Key, Element.Value);
        }
    }
 
    // Start - intrusive TOptional<TSortedMap> state //
    constexpr static bool bHasIntrusiveUnsetOptionalState = true;
    using IntrusiveUnsetOptionalStateType = TSortedMap;
 
    [[nodiscard]] explicit TSortedMap(FIntrusiveUnsetOptionalState Tag)
        : Pairs(Tag)
    {
    }
    [[nodiscard]] bool operator==(FIntrusiveUnsetOptionalState Tag) const
    {
        return Pairs == Tag;
    }
    // End - intrusive TOptional<TSortedMap> state //
 
    template<typename OtherArrayAllocator>
    TSortedMap& operator=(TSortedMap<KeyType, ValueType, OtherArrayAllocator, SortPredicate>&& Other)
    {
        Pairs = MoveTemp(Other.Pairs);
        return *this;
    }
 
    template<typename OtherArrayAllocator>
    TSortedMap& operator=(const TSortedMap<KeyType, ValueType, OtherArrayAllocator, SortPredicate>& Other)
    {
        Pairs = Other.Pairs;
        return *this;
    }
 
    TSortedMap& operator=(std::initializer_list<TPairInitializer<const KeyType&, const ValueType&>> InitList)
    {
        this->Empty((int32)InitList.size());
        for (const TPairInitializer<const KeyType&, const ValueType&>& Element : InitList)
        {
            this->Add(Element.Key, Element.Value);
        }
        return *this;
    }
 
    UE_FORCEINLINE_HINT bool operator==(const TSortedMap& Other) const
    {
        return Pairs == Other.Pairs;
    }
 
    UE_FORCEINLINE_HINT bool operator!=(const TSortedMap& Other) const
    {
        return Pairs != Other.Pairs;
    }
 
    UE_FORCEINLINE_HINT void Empty(int32 ExpectedNumElements = 0)
    {
        Pairs.Empty(ExpectedNumElements);
    }
 
    UE_FORCEINLINE_HINT void Reset()
    {
        Pairs.Reset();
    }
 
    UE_FORCEINLINE_HINT void Shrink()
    {
        Pairs.Shrink();
    }
 
    UE_FORCEINLINE_HINT void Reserve(int32 Number)
    {
        Pairs.Reserve(Number);
    }
 
    [[nodiscard]] bool IsEmpty() const
    {
        return Pairs.IsEmpty();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Num() const
    {
        return Pairs.Num();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 Max() const
    {
        return Pairs.Max();
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT SIZE_T GetAllocatedSize() const
    {
        return Pairs.GetAllocatedSize();
    }
 
    UE_FORCEINLINE_HINT void CountBytes(FArchive& Ar) const
    {
        Pairs.CountBytes(Ar);
    }
 
    UE_FORCEINLINE_HINT ValueType& Add(const KeyType&  InKey, const ValueType&  InValue) { return Emplace(         InKey ,          InValue ); }
    UE_FORCEINLINE_HINT ValueType& Add(const KeyType&  InKey,       ValueType&& InValue) { return Emplace(         InKey , MoveTemp(InValue)); }
    UE_FORCEINLINE_HINT ValueType& Add(      KeyType&& InKey, const ValueType&  InValue) { return Emplace(MoveTemp(InKey),          InValue ); }
    UE_FORCEINLINE_HINT ValueType& Add(      KeyType&& InKey,       ValueType&& InValue) { return Emplace(MoveTemp(InKey), MoveTemp(InValue)); }
 
    UE_FORCEINLINE_HINT ValueType& Add(const KeyType&  InKey) { return Emplace(         InKey ); }
    UE_FORCEINLINE_HINT ValueType& Add(      KeyType&& InKey) { return Emplace(MoveTemp(InKey)); }
 
    template <typename InitKeyType = KeyType, typename InitValueType = ValueType>
    ValueType& Emplace(InitKeyType&& InKey, InitValueType&& InValue)
    {
        ElementType* DataPtr = AllocateMemoryForEmplace(InKey);
    
        ::new((void*)DataPtr) ElementType(TPairInitializer<InitKeyType&&, InitValueType&&>(Forward<InitKeyType>(InKey), Forward<InitValueType>(InValue)));
 
        return DataPtr->Value;
    }
 
    template <typename InitKeyType = KeyType>
    ValueType& Emplace(InitKeyType&& InKey)
    {
        ElementType* DataPtr = AllocateMemoryForEmplace(InKey);
 
        ::new((void*)DataPtr) ElementType(TKeyInitializer<InitKeyType&&>(Forward<InitKeyType>(InKey)));
 
        return DataPtr->Value;
    }
 
    inline int32 Remove(KeyConstPointerType InKey)
    {
        int32 RemoveIndex = FindIndex(InKey);
 
        if (RemoveIndex == INDEX_NONE)
        {
            return 0;
        }
 
        Pairs.RemoveAt(RemoveIndex);
 
        return 1;
    }
 
    [[nodiscard]] const KeyType* FindKey(ValueInitType Value) const
    {
        for(typename ElementArrayType::TConstIterator PairIt(Pairs);PairIt;++PairIt)
        {
            if(PairIt->Value == Value)
            {
                return &PairIt->Key;
            }
        }
        return nullptr;
    }
 
    [[nodiscard]] inline ValueType* Find(KeyConstPointerType Key)
    {
        int32 FoundIndex = FindIndex(Key);
 
        if (FoundIndex != INDEX_NONE)
        {
            return &Pairs[FoundIndex].Value;
        }
 
        return nullptr;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ValueType* Find(KeyConstPointerType Key) const
    {
        return const_cast<TSortedMap*>(this)->Find(Key);
    }
 
    UE_FORCEINLINE_HINT ValueType& FindOrAdd(const KeyType&  Key) { return FindOrAddImpl(         Key ); }
    UE_FORCEINLINE_HINT ValueType& FindOrAdd(      KeyType&& Key) { return FindOrAddImpl(MoveTemp(Key)); }
 
    [[nodiscard]] inline ValueType& FindChecked(KeyConstPointerType Key)
    {
        ValueType* Value = Find(Key);
        check(Value != nullptr);
        return *Value;
    }
 
    [[nodiscard]] inline const ValueType& FindChecked(KeyConstPointerType Key) const
    {
        const ValueType* Value = Find(Key);
        check(Value != nullptr);
        return *Value;
    }
 
    [[nodiscard]] inline ValueType FindRef(KeyConstPointerType Key) const
    {
        if (const ValueType* Value = Find(Key))
        {
            return *Value;
        }
 
        return ValueType();
    }
 
    [[nodiscard]] inline ValueType FindRef(KeyConstPointerType Key, ValueType DefaultValue) const
    {
        if (const ValueType* Value = Find(Key))
        {
            return *Value;
        }
 
        return DefaultValue;
    }
 
    [[nodiscard]] ElementType* FindArbitraryElement()
    {
        // The goal of this function is to be fast, and so the implementation may be improved at any time even if it gives different results.
 
        return Pairs.IsEmpty() ? nullptr : &Pairs.Last();
    }
    [[nodiscard]] const ElementType* FindArbitraryElement() const
    {
        return const_cast<TSortedMap*>(this)->FindArbitraryElement();
    }
 
    [[nodiscard]] inline bool Contains(KeyConstPointerType Key) const
    {
        if (Find(Key))
        {
            return true;
        }
        return false;
    }
 
    template<typename Allocator> int32 GetKeys(TArray<KeyType, Allocator>& OutKeys) const
    {
        for (typename ElementArrayType::TConstIterator PairIt(Pairs); PairIt; ++PairIt)
        {
            OutKeys.Add(PairIt->Key);
        }
 
        return OutKeys.Num();
    }
 
    template<typename Allocator> void GenerateKeyArray(TArray<KeyType, Allocator>& OutArray) const
    {
        OutArray.Empty(Pairs.Num());
        for(typename ElementArrayType::TConstIterator PairIt(Pairs);PairIt;++PairIt)
        {
            OutArray.Add(PairIt->Key);
        }
    }
 
    template<typename Allocator> void GenerateValueArray(TArray<ValueType, Allocator>& OutArray) const
    {
        OutArray.Empty(Pairs.Num());
        for(typename ElementArrayType::TConstIterator PairIt(Pairs);PairIt;++PairIt)
        {
            OutArray.Add(PairIt->Value);
        }
    }
 
    void Dump(FOutputDevice& Ar)
    {
        Pairs.Dump(Ar);
    }
 
    inline bool RemoveAndCopyValue(KeyInitType Key, ValueType& OutRemovedValue)
    {
        int32 FoundIndex = FindIndex(Key);
        if (FoundIndex == INDEX_NONE)
        {
            return false;
        }
 
        OutRemovedValue = MoveTemp(Pairs[FoundIndex].Value);
        Pairs.RemoveAt(FoundIndex);
        return true;
    }
    
    inline ValueType FindAndRemoveChecked(KeyConstPointerType Key)
    {
        int32 FoundIndex = FindIndex(Key);
        check(FoundIndex != INDEX_NONE);
        
        ValueType OutRemovedValue = MoveTemp(Pairs[FoundIndex].Value);
        Pairs.RemoveAt(FoundIndex);
        return OutRemovedValue;
    }
 
    template<typename OtherArrayAllocator, typename OtherSortPredicate>
    void Append(TSortedMap<KeyType, ValueType, OtherArrayAllocator, OtherSortPredicate>&& OtherMap)
    {
        this->Reserve(this->Num() + OtherMap.Num());
        for (auto& Pair : OtherMap)
        {
            this->Add(MoveTemp(Pair.Key), MoveTemp(Pair.Value));
        }
 
        OtherMap.Reset();
    }
 
    template<typename OtherArrayAllocator, typename OtherSortPredicate>
    void Append(const TSortedMap<KeyType, ValueType, OtherArrayAllocator, OtherSortPredicate>& OtherMap)
    {
        this->Reserve(this->Num() + OtherMap.Num());
        for (auto& Pair : OtherMap)
        {
            this->Add(Pair.Key, Pair.Value);
        }
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ValueType& operator[](KeyConstPointerType Key)
    {
        return this->FindChecked(Key);
    }
    [[nodiscard]] UE_FORCEINLINE_HINT const ValueType& operator[](KeyConstPointerType Key) const
    {
        return this->FindChecked(Key);
    }
 
    // Interface functions to match TMap/TSet
 
    UE_DEPRECATED(5.7 until 5.9, "GetMaxIndex() should be replaced with Num() - 1.")
    [[nodiscard]] UE_FORCEINLINE_HINT int32 GetMaxIndex() const
    {
        // We don't want to deprecate the function entirely, because it should mirror the the existing TMap API, but it's been
        // returning the wrong value and we want to fix that.
        //
        // The deprecation macro lists "5.7 until 5.9", and from 5.9 this function should be de-deprecated and the return value should become "return Pairs.Num();".
        return Pairs.Num() - 1;
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT bool IsValidId(FSetElementId Id) const
    {
        return Pairs.IsValidIndex(Id.AsInteger());
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT ElementType& Get(FSetElementId Id)
    {
        return Pairs[Id.AsInteger()];
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT const ElementType& Get(FSetElementId Id) const
    {
        return Pairs[Id.AsInteger()];
    }
 
private:
    typedef TArray<ElementType, ArrayAllocator> ElementArrayType;
 
    template <typename ArgType>
    [[nodiscard]] inline ValueType& FindOrAddImpl(ArgType&& Key)
    {
        if (ValueType* Value = Find(Key))
        {
            return *Value;
        }
 
        return Add(Forward<ArgType>(Key));
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT int32 FindIndex(KeyConstPointerType Key) const
    {
        return Algo::BinarySearchBy(Pairs, Key, FKeyForward(), SortPredicate());
    }
 
    template <typename InitKeyType>
    inline ElementType* AllocateMemoryForEmplace(InitKeyType&& InKey)
    {
        int32 InsertIndex = Algo::LowerBoundBy(Pairs, InKey, FKeyForward(), SortPredicate());
        check(InsertIndex >= 0 && InsertIndex <= Pairs.Num());
 
        ElementType* DataPtr = nullptr;
        // Since we returned lower bound we already know InKey <= InsertIndex key. So if InKey is not < InsertIndex key, they must be equal
        if (Pairs.IsValidIndex(InsertIndex) && !SortPredicate()(InKey, Pairs[InsertIndex].Key))
        {
            // Replacing element, delete old one
            DataPtr = Pairs.GetData() + InsertIndex;
            DestructItems(DataPtr, 1);
        }
        else
        {
            // Adding new one, this may reallocate Pairs
            Pairs.InsertUninitialized(InsertIndex, 1);
            DataPtr = Pairs.GetData() + InsertIndex;
        }
 
        return DataPtr;
    }
 
    struct FKeyForward
    {
        UE_FORCEINLINE_HINT const KeyType& operator()(const ElementType& Pair) const
        {
            return Pair.Key;
        }
    };
 
    template<bool bConst>
    class TBaseIterator
    {
    public:
        typedef std::conditional_t<bConst,typename ElementArrayType::TConstIterator,typename ElementArrayType::TIterator> PairItType;
    private:
        typedef std::conditional_t<bConst,const TSortedMap,TSortedMap> MapType;
        typedef std::conditional_t<bConst,const KeyType,KeyType> ItKeyType;
        typedef std::conditional_t<bConst,const ValueType,ValueType> ItValueType;
        typedef std::conditional_t<bConst,const typename ElementArrayType::ElementType, typename ElementArrayType::ElementType> PairType;
 
    protected:
        [[nodiscard]] UE_FORCEINLINE_HINT TBaseIterator(const PairItType& InElementIt)
            : PairIt(InElementIt)
        {
        }
 
    public:
        UE_FORCEINLINE_HINT TBaseIterator& operator++()
        {
            ++PairIt;
            return *this;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
        {
            return !!PairIt; 
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TBaseIterator& Rhs) const
        {
            return PairIt == Rhs.PairIt;
        }
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TBaseIterator& Rhs) const
        {
            return PairIt != Rhs.PairIt;
        }
 
        UE_FORCEINLINE_HINT ItKeyType& Key() const
        {
            return PairIt->Key;
        }
        UE_FORCEINLINE_HINT ItValueType& Value() const
        {
            return PairIt->Value;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT FSetElementId GetId() const
        {
            return FSetElementId::FromInteger(PairIt.GetIndex());
        }
 
        UE_FORCEINLINE_HINT PairType& operator*() const
        {
            return  *PairIt;
        }
        UE_FORCEINLINE_HINT PairType* operator->() const
        {
            return &*PairIt;
        }
 
    protected:
        PairItType PairIt;
    };
 
    template<bool bConst>
    class TBaseReverseIterator
    {
        // Once we add reverse iterator to TArray, this class and TBaseIterator could be merged with a template parameter for forward vs reverse.
    private:
        typedef std::conditional_t<bConst, const TSortedMap, TSortedMap> MapType;
        typedef std::conditional_t<bConst, const KeyType, KeyType> ItKeyType;
        typedef std::conditional_t<bConst, const ValueType, ValueType> ItValueType;
        typedef typename ElementArrayType::SizeType SizeType;
 
    public:
        typedef std::conditional_t<bConst, const typename ElementArrayType::ElementType, typename ElementArrayType::ElementType> PairType;
 
    protected:
        [[nodiscard]] UE_FORCEINLINE_HINT TBaseReverseIterator(PairType* InData, SizeType InNum)
            : Data(InData), Index(InNum-1)
        {
        }
 
    public:
        inline TBaseReverseIterator& operator++()
        {
            checkf(Index != static_cast<SizeType>(-1), TEXT("Incrementing an invalid iterator is illegal"));
            --Index;
            return *this;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT explicit operator bool() const
        {
            return Index != static_cast<SizeType>(-1);
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator==(const TBaseReverseIterator& Rhs) const
        {
            return Index == Rhs.Index;
        }
        [[nodiscard]] UE_FORCEINLINE_HINT bool operator!=(const TBaseReverseIterator& Rhs) const
        {
            return Index != Rhs.Index;
        }
 
        UE_FORCEINLINE_HINT ItKeyType& Key() const
        {
            return Data[Index].Key;
        }
        UE_FORCEINLINE_HINT ItValueType& Value() const
        {
            return Data[Index].Value;
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT FSetElementId GetId() const
        {
            return FSetElementId::FromInteger(Index);
        }
 
        UE_FORCEINLINE_HINT PairType& operator*() const
        {
            return  Data[Index];
        }
        UE_FORCEINLINE_HINT PairType* operator->() const
        {
            return &Data[Index];
        }
 
    protected:
        PairType* Data;
        SizeType Index;
    };
 
    ElementArrayType Pairs;
 
public:
 
    class TIterator : public TBaseIterator<false>
    {
    public:
 
        [[nodiscard]] UE_FORCEINLINE_HINT TIterator(TSortedMap& InMap)
            : TBaseIterator<false>(InMap.Pairs.CreateIterator())
        {
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT TIterator(const typename TBaseIterator<false>::PairItType& InPairIt)
            : TBaseIterator<false>(InPairIt)
        {
        }
 
        UE_FORCEINLINE_HINT void RemoveCurrent()
        {
            TBaseIterator<false>::PairIt.RemoveCurrent();
        }
    };
 
    class TConstIterator : public TBaseIterator<true>
    {
    public:
        [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator(const TSortedMap& InMap)
            : TBaseIterator<true>(InMap.Pairs.CreateConstIterator())
        {
        }
 
        [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator(const typename TBaseIterator<true>::PairItType& InPairIt)
            : TBaseIterator<true>(InPairIt)
        {
        }
    };
 
    class TReverseIterator : public TBaseReverseIterator<false>
    {
    public:
        [[nodiscard]] UE_FORCEINLINE_HINT TReverseIterator(TSortedMap& InMap)
            : TBaseReverseIterator<false>(InMap.Pairs.GetData(), InMap.Pairs.Num())
        {
        }
 
        // Add constructor from PairItType and RemoveCurrent once we have reverse iterators on TArray
    };
 
    class TConstReverseIterator : public TBaseReverseIterator<true>
    {
    public:
        [[nodiscard]] UE_FORCEINLINE_HINT TConstReverseIterator(const TSortedMap& InMap)
            : TBaseReverseIterator<true>(InMap.Pairs.GetData(), InMap.Pairs.Num())
        {
        }
 
        // Add constructor from PairItType once we have reverse iterators on TArray
    };
 
    class TConstKeyIterator : public TBaseIterator<true>
    {
        using Super = TBaseIterator<true>;
 
    public:
        [[nodiscard]] inline TConstKeyIterator(const TSortedMap& InMap, KeyInitType InKey)
            : Super(InMap.Pairs.CreateConstIterator())
        {
            int32 NewIndex = InMap.FindIndex(InKey);
        
            if (NewIndex != INDEX_NONE)
            {
                Super::PairIt += NewIndex;
            }
            else
            {
                Super::PairIt.SetToEnd();
            }
        }
 
        inline TConstKeyIterator& operator++()
        {
            Super::PairIt.SetToEnd();
            return *this;
        }
    };
 
    class TKeyIterator : public TBaseIterator<false>
    {
        using Super = TBaseIterator<false>;
 
    public:
        [[nodiscard]] inline TKeyIterator(TSortedMap& InMap, KeyInitType InKey)
            : Super(InMap.Pairs.CreateIterator())
        {
            int32 NewIndex = InMap.FindIndex(InKey);
 
            if (NewIndex != INDEX_NONE)
            {
                Super::PairIt += NewIndex;
            }
            else
            {
                Super::PairIt.SetToEnd();
            }
        }
 
        inline TKeyIterator& operator++()
        {
            Super::PairIt.SetToEnd();
            return *this;
        }
 
        inline void RemoveCurrent()
        {
            Super::PairIt.RemoveCurrent();
            Super::PairIt.SetToEnd();
        }
    };
 
    [[nodiscard]] UE_FORCEINLINE_HINT TIterator CreateIterator()
    {
        return TIterator(*this);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT TConstIterator CreateConstIterator() const
    {
        return TConstIterator(*this);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT TKeyIterator CreateKeyIterator(KeyInitType InKey)
    {
        return TKeyIterator(*this, InKey);
    }
 
    [[nodiscard]] UE_FORCEINLINE_HINT TConstKeyIterator CreateConstKeyIterator(KeyInitType InKey) const
    {
        return TConstKeyIterator(*this, InKey);
    }
 
    typedef typename ElementArrayType::RangedForIteratorType RangedForIteratorType;
    typedef typename ElementArrayType::RangedForConstIteratorType RangedForConstIteratorType;
 
public:
    [[nodiscard]] UE_FORCEINLINE_HINT RangedForIteratorType     begin()       { return Pairs.begin(); }
    [[nodiscard]] UE_FORCEINLINE_HINT RangedForConstIteratorType    begin() const { return Pairs.begin(); }
    [[nodiscard]] UE_FORCEINLINE_HINT RangedForIteratorType     end()         { return Pairs.end(); }
    [[nodiscard]] UE_FORCEINLINE_HINT RangedForConstIteratorType    end() const   { return Pairs.end(); }
 
    friend struct TSortedMapPrivateFriend;
};
 
DECLARE_TEMPLATE_INTRINSIC_TYPE_LAYOUT((template <typename KeyType, typename ValueType, typename ArrayAllocator, typename SortPredicate>), (TSortedMap<KeyType, ValueType, ArrayAllocator, SortPredicate>));
 
struct TSortedMapPrivateFriend
{
    template <typename KeyType, typename ValueType, typename ArrayAllocator, typename SortPredicate>
    static void Serialize(FArchive& Ar, TSortedMap<KeyType, ValueType, ArrayAllocator, SortPredicate>& Map)
    {
        Ar << Map.Pairs;
 
        if (Ar.IsLoading())
        {
            // We need to resort, in case the sorting is not consistent with what it was before
            Algo::SortBy(Map.Pairs, typename TSortedMap<KeyType, ValueType, ArrayAllocator, SortPredicate>::FKeyForward(), SortPredicate());
        }
    }
};
 
template <typename KeyType, typename ValueType, typename ArrayAllocator, typename SortPredicate>
inline FArchive& operator<<(FArchive& Ar, TSortedMap<KeyType, ValueType, ArrayAllocator, SortPredicate>& Map)
{
    TSortedMapPrivateFriend::Serialize(Ar, Map);
    return Ar;
}