// 场景：存储 100,000 个实体，每个 128 字节
TArray<FGameEntity> Entities;  // 需要 12.8 MB 连续内存

// 问题 1：内存碎片化 → 分配失败
// 服务器运行一段时间后，总内存够但找不到 12.8 MB 连续空间

// 问题 2：扩容代价高
// 扩容时需要：分配新内存 → 拷贝所有数据 → 释放旧内存
// 时间复杂度 O(n)

// 问题 3：引用失效
FGameEntity* Ptr = &Entities[500];
Entities.Add(NewEntity);  // 扩容后 Ptr 失效！

TChunkedArray<FGameEntity, 32768> Entities;  // 每个 Chunk 32KB

// 优势 1：不需要大块连续内存
// 100,000 个实体分散在约 400 个 32KB Chunk 中

// 优势 2：扩容只需分配新 Chunk，O(1) 复杂度

// 优势 3：引用永不失效
FGameEntity* Ptr = &Entities[500];
for (int32 i = 0; i < 100000; ++i)
    Entities.AddElement(FGameEntity());
// Ptr 仍然有效！

TArray（连续内存）：
┌─────────────────────────────────────────────────────┐
│ Element[0] │ Element[1] │ ... │ Element[N-1]        │
└─────────────────────────────────────────────────────┘

TChunkedArray（分块存储）：
┌────────────────┐  ┌────────────────┐  ┌────────────────┐
│ Chunk 0        │  │ Chunk 1        │  │ Chunk 2        │
│ [0..255]       │  │ [256..511]     │  │ [512..767]     │
└────────────────┘  └────────────────┘  └────────────────┘
     独立分配            独立分配            独立分配

template<typename InElementType, uint32 TargetBytesPerChunk, typename AllocatorType>
class TChunkedArray
{
public:
    typedef InElementType ElementType;
    
protected:
    // 编译时计算每个 Chunk 的元素数量
    enum { NumElementsPerChunk = TargetBytesPerChunk / sizeof(ElementType) };
    
    // Chunk 结构：固定大小的元素数组
    struct FChunk
    {
        ElementType Elements[NumElementsPerChunk];
    };
    
    // 使用 TIndirectArray 存储 Chunk 指针
    // 这样扩容时只移动指针，不移动 Chunk 数据
    typedef TIndirectArray<FChunk, AllocatorType> ChunksType;
    ChunksType Chunks;
    
    // 当前元素总数
    int32 NumElements;
};

// ✅ POD 类型
struct FPodExample
{
    int32 ID;
    float Value;
    FVector Position;    // FVector 也是 POD
    char Name[32];       // 固定大小数组
};

// ❌ 非 POD 类型
struct FNonPodExample
{
    TArray<int32> Data;  // 有构造/析构函数
    FString Name;        // 有构造/析构函数
    virtual void Foo();  // 有虚函数
};

// 危险：昂贵的默认构造函数
struct FExpensiveType
{
    TArray<int32> Data;
    FString Name;
    
    FExpensiveType() 
    { 
        Data.Reserve(1000);  // 每次构造都分配内存！
        Name = TEXT("Default");
    }
};

TChunkedArray<FExpensiveType, 16384> Array;
// 每个 Chunk 约 128 个元素（假设 FExpensiveType 约 128 字节）
// 添加第一个元素时，会构造 128 个 FExpensiveType！
// 即使你只用 1 个，也会执行 128 次构造函数

// 方案 1：使用 POD 类型（推荐）
struct FEntityData  // POD
{
    uint32 ID;
    FVector Position;
    float Health;
};
TChunkedArray<FEntityData> Entities;  // 高效

// 方案 2：使用 TOptional 延迟构造
TChunkedArray<TOptional<FExpensiveType>> Array;
// new FChunk 时只初始化 TOptional 为空状态
// 不会调用 FExpensiveType 的构造函数

// 方案 3：设计轻量级默认构造函数
struct FLightweightType
{
    TArray<int32> Data;  // 默认构造不分配内存
    
    FLightweightType() = default;  // 使用编译器生成的默认构造
    
    void Initialize()  // 延迟初始化
    {
        Data.Reserve(1000);
    }
};

// UE 中检测 POD 类型
static_assert(TIsPODType<FEntityData>::Value, "FEntityData must be POD type");

// TOptional 的简化实现
template<typename T>
class TOptional
{
    alignas(T) uint8 Storage[sizeof(T)];  // 预留空间，但不构造对象
    bool bIsSet = false;                   // 标记是否有值
    
public:
    TOptional() : bIsSet(false) {}  // 默认构造：只设置标志，不构造 T
    
    template<typename... Args>
    void Emplace(Args&&... args)    // 需要时才构造
    {
        new(Storage) T(Forward<Args>(args)...);
        bIsSet = true;
    }
    
    T& GetValue() { return *reinterpret_cast<T*>(Storage); }
    bool IsSet() const { return bIsSet; }
};

直接存储 FExpensiveType：
┌─────────────────────────────────────┐
│ TArray Data (已分配内存)             │  ← 构造时分配
│ FString Name (已构造)               │  ← 构造时初始化
└─────────────────────────────────────┘

TOptional<FExpensiveType>：
┌─────────────────────────────────────┐
│ Storage[sizeof(FExpensiveType)]     │  ← 只是原始字节，未初始化
│ bIsSet = false                      │  ← 标记为"空"
└─────────────────────────────────────┘

TChunkedArray<TOptional<FExpensiveType>> Array;

// 添加元素
int32 Index = Array.Add(1);
Array[Index].Emplace(arg1, arg2);  // 只在需要时构造

// 访问时需要检查
if (Array[Index].IsSet())
{
    Array[Index].GetValue().DoSomething();
}

// 或使用 GetValue() 直接访问（确保已 Emplace）
FExpensiveType& Value = Array[Index].GetValue();

┌─────────────────────────────────────────────────────────────────┐
│                      TChunkedArray 实例                          │
│  ┌───────────────────────────────────────────────────────────┐  │
│  │           Chunks (TIndirectArray<FChunk>)                  │  │
│  │  ┌────────┬────────┬────────┬────────┐                    │  │
│  │  │ Ptr[0] │ Ptr[1] │ Ptr[2] │  ...   │  ← 指针数组        │  │
│  │  └───┬────┴───┬────┴───┬────┴────────┘                    │  │
│  └──────┼────────┼────────┼──────────────────────────────────┘  │
│         │        │        │                                      │
│         ▼        ▼        ▼                                      │
│    ┌────────┐ ┌────────┐ ┌────────┐                             │
│    │Chunk 0 │ │Chunk 1 │ │Chunk 2 │  ← 独立分配的内存块         │
│    │ 16KB   │ │ 16KB   │ │ 16KB   │                             │
│    └────────┘ └────────┘ └────────┘                             │
│                                                                  │
│  NumElements: 10000                                              │
└─────────────────────────────────────────────────────────────────┘

// 分配空间（不初始化）
int32 Add(int32 Count = 1)
{
    const int32 OldNum = NumElements;
    const int32 NewNumElements = OldNum + Count;
    const int32 NewNumChunks = (NewNumElements + NumElementsPerChunk - 1) / NumElementsPerChunk;
    
    NumElements = NewNumElements;
    
    // 按需创建新 Chunk
    for (int32 NumChunks = Chunks.Num(); NumChunks < NewNumChunks; ++NumChunks)
    {
        Chunks.Add(new FChunk);
    }
    
    return OldNum;  // 返回新元素起始索引
}

// 添加并初始化
int32 AddElement(const ElementType& Item)
{
    new(*this) ElementType(Item);  // placement new
    return NumElements - 1;
}

// 全局 operator new 重载
template <typename T, uint32 TargetBytesPerChunk, typename AllocatorType>
void* operator new(size_t Size, TChunkedArray<T, TargetBytesPerChunk, AllocatorType>& ChunkedArray)
{
    const int32 Index = ChunkedArray.Add(1);
    return &ChunkedArray(Index);
}

// 使用方式
TChunkedArray<FMyClass> Array;
new(Array) FMyClass(Arg1, Arg2);  // 直接在数组中构造，避免拷贝

// 预分配
void Reserve(int32 Number);

// 清空
void Empty(int32 Slack = 0);

// 收缩
void Shrink();

// 查询
int32 Num() const { return NumElements; }
bool IsEmpty() const { return NumElements == 0; }
bool IsValidIndex(int32 Index) const { return Index >= 0 && Index < NumElements; }

// 拷贝到线性数组（仅 POD 类型）
template<typename OtherAllocator>
void CopyToLinearArray(TArray<ElementType, OtherAllocator>& DestinationArray);

// CopyToLinearArray 的实现（简化）
template<typename OtherAllocator>
void CopyToLinearArray(TArray<ElementType, OtherAllocator>& DestinationArray)
{
    DestinationArray.SetNumUninitialized(NumElements);
    
    ElementType* Dest = DestinationArray.GetData();
    
    for (int32 ChunkIndex = 0; ChunkIndex < Chunks.Num(); ++ChunkIndex)
    {
        int32 ElementsToCopy = /* 计算本 Chunk 要拷贝的元素数 */;
        
        // 关键：使用 memcpy 直接拷贝内存
        FMemory::Memcpy(Dest, Chunks[ChunkIndex].Elements, ElementsToCopy * sizeof(ElementType));
        
        Dest += ElementsToCopy;
    }
}

struct FNonPod
{
    TArray<int32> Data;   // 内部有指针
    FString Name;         // 内部有指针
};

FNonPod A;
A.Data = {1, 2, 3};
A.Name = TEXT("Hello");

FNonPod B;
memcpy(&B, &A, sizeof(FNonPod));  // 危险！

// 问题 1：浅拷贝 - A 和 B 的 Data.Ptr 指向同一块内存
// 问题 2：B 的析构函数会 delete 这块内存
// 问题 3：A 再析构时 → double free → 崩溃！

struct FPod
{
    int32 ID;
    FVector Position;  // 12 字节，无指针
    float Health;
};

FPod A = {1, FVector(1,2,3), 100.0f};
FPod B;
memcpy(&B, &A, sizeof(FPod));  // 安全！

// POD 类型的所有数据都在结构体内部
// 没有指针，没有资源管理，纯粹的字节拷贝

namespace UE4ChunkedArray_Private
{
    template <typename ChunkType, typename ElementType, uint32 NumElementsPerChunk>
    struct TChunkedArrayIterator
    {
        // 成员变量（注意：没有构造函数，使用聚合初始化）
        ChunkType** Chunk;           // 当前 Chunk 指针的指针
        uint32 Count = 0;            // 已遍历元素数（默认值 0）
        uint32 ElementIndex = 0;     // Chunk 内索引（默认值 0）
        
        // 解引用：获取当前元素
        ElementType& operator*() const
        {
            return (*Chunk)->Elements[ElementIndex];
        }
        
        // 前进：移动到下一个元素
        void operator++()
        {
            ++ElementIndex;
            if (ElementIndex >= NumElementsPerChunk)
            {
                ElementIndex = 0;
                ++Chunk;  // 跳到下一个 Chunk
            }
            ++Count;
        }
        
        // 比较：判断是否到达末尾
        bool operator!=(const TChunkedArrayIterator& Rhs) const
        {
            return Count < Rhs.Count;
        }
    };
}

template<typename InElementType, uint32 TargetBytesPerChunk, typename AllocatorType>
class TChunkedArray
{
private:
    // 迭代器类型定义
    typedef UE4ChunkedArray_Private::TChunkedArrayIterator<
        FChunk, ElementType, NumElementsPerChunk> FIterType;
    typedef UE4ChunkedArray_Private::TChunkedArrayIterator<
        const FChunk, const ElementType, NumElementsPerChunk> FConstIterType;

public:
    FIterType begin()
    {
        return FIterType{Chunks.GetData()};  // 聚合初始化
    }

    FConstIterType begin() const
    {
        return FConstIterType{Chunks.GetData()};
    }

    FIterType end()
    {
        return FIterType{nullptr, uint32(NumElements)};  // 聚合初始化
    }

    FConstIterType end() const
    {
        return FConstIterType{nullptr, uint32(NumElements)};
    }
};

{
    auto&& __range = Entities;
    auto __begin = __range.begin();  // FIterType{Chunks.GetData()}
    auto __end = __range.end();      // FIterType{nullptr, NumElements}
    
    for (; __begin != __end; ++__begin)
    {
        FEntity& Entity = *__begin;
        Entity.Update();
    }
}

数组: [Chunk0: A,B,C,D] [Chunk1: E,F,G,H] [Chunk2: I,J]
      NumElementsPerChunk = 4, NumElements = 10

begin(): Chunk=&Chunks[0], Count=0, ElementIndex=0
end():   Chunk=nullptr,    Count=10

遍历过程：
┌───────┬───────┬──────────────┬─────────────────────────┐
│ Count │ ElemIdx│ Chunk        │ *iter                   │
├───────┼───────┼──────────────┼─────────────────────────┤
│   0   │   0   │ &Chunks[0]   │ Chunks[0]->Elements[0]=A│
│   1   │   1   │ &Chunks[0]   │ Chunks[0]->Elements[1]=B│
│   2   │   2   │ &Chunks[0]   │ Chunks[0]->Elements[2]=C│
│   3   │   3   │ &Chunks[0]   │ Chunks[0]->Elements[3]=D│
│   4   │   0   │ &Chunks[1]   │ Chunks[1]->Elements[0]=E│ ← 跳到 Chunk1
│   5   │   1   │ &Chunks[1]   │ Chunks[1]->Elements[1]=F│
│   6   │   2   │ &Chunks[1]   │ Chunks[1]->Elements[2]=G│
│   7   │   3   │ &Chunks[1]   │ Chunks[1]->Elements[3]=H│
│   8   │   0   │ &Chunks[2]   │ Chunks[2]->Elements[0]=I│ ← 跳到 Chunk2
│   9   │   1   │ &Chunks[2]   │ Chunks[2]->Elements[1]=J│
│  10   │   -   │     -        │ Count==end.Count, 停止   │
└───────┴───────┴──────────────┴─────────────────────────┘

TChunkedArray<FEntity> Entities;

// 范围 for 循环（推荐，简洁）
for (FEntity& Entity : Entities)
{
    Entity.Update();
}

// const 遍历
for (const FEntity& Entity : Entities)
{
    UE_LOG(LogTemp, Log, TEXT("ID: %d"), Entity.ID);
}

// 索引循环（需要索引时使用）
for (int32 i = 0; i < Entities.Num(); ++i)
{
    Entities[i].Index = i;
}

// 使用 NumElements = -1 表示"未设置"状态
// 避免 TOptional 额外的 bool 标志

constexpr static bool bHasIntrusiveUnsetOptionalState = true;

explicit TChunkedArray(FIntrusiveUnsetOptionalState)
    : NumElements(-1) {}

bool operator==(FIntrusiveUnsetOptionalState) const
{
    return NumElements == -1;
}

// 使用
TOptional<TChunkedArray<int32>> OptionalArray;
if (!OptionalArray.IsSet())  // 检查 NumElements == -1
{
    OptionalArray.Emplace(1000);
}

// 100 万元素，64 字节/元素

// TArray
Add (no reserve): 0.15 sec    ← 多次重新分配
Add (with reserve): 0.09 sec
Iterate: 0.0012 sec           ← 连续内存，最快
Random access: 0.023 sec

// TChunkedArray
Add (no reserve): 0.095 sec   ← 无需重新分配，更快
Add (with reserve): 0.088 sec
Iterate: 0.0018 sec           ← 略慢（~50%）
Random access: 0.031 sec      ← 略慢（~35%）

// 1. 大规模数据存储
TChunkedArray<FPlayerData, 32768> PlayerData;  // 数万玩家

// 2. 长时间运行的服务（避免碎片化）
TChunkedArray<FLogEntry> LogEntries;

// 3. 需要引用稳定性
TChunkedArray<FObject> Objects;
TMap<FName, FObject*> NameToObject;  // 指针始终有效

// 4. 网络复制系统
TChunkedArray<FActorReplicationInfo> ActorStates;

// 1. 需要连续内存（C API）
void ProcessData(float* Data, int32 Count);
// TChunkedArray 不能直接传递

// 2. 小型数组（Chunk 开销不值得）
TArray<FSmallData> SmallArray;  // 推荐

// 3. 高频随机访问
// TArray 更快

// 4. 需要删除元素
// TChunkedArray 不支持 RemoveAt

// 1. 选择合适的 Chunk 大小
TChunkedArray<int32> IntArray;                    // 默认 16KB
TChunkedArray<FMediumStruct, 32768> MediumArray;  // 32KB
TChunkedArray<FLargeStruct, 65536> LargeArray;    // 64KB

// 2. 预分配
TChunkedArray<FData> Data;
Data.Reserve(ExpectedCount);

// 3. 配合索引映射
TChunkedArray<FEntity> Entities;
TMap<uint32, int32> IDToIndex;

// 4. 利用引用稳定性
FEntity* Ptr = &Entities[Index];  // 永远有效

// EntityManager.h

#pragma once
#include "CoreMinimal.h"
#include "Containers/ChunkedArray.h"

// 实体数据（POD 类型）
struct FEntityData
{
    uint32 EntityID;
    uint32 Flags;
    FVector Location;
    FRotator Rotation;
    float Health;
    float MaxHealth;
    
    bool IsActive() const { return (Flags & 1) != 0; }
    bool IsPendingKill() const { return (Flags & 2) != 0; }
    void MarkDirty() { Flags |= 4; }
};

// 查询过滤器
struct FEntityFilter
{
    TOptional<FVector> Center;
    TOptional<float> Radius;
    TOptional<uint32> RequiredFlags;
    
    FEntityFilter& InRadius(const FVector& C, float R)
    {
        Center = C;
        Radius = R;
        return *this;
    }
    
    FEntityFilter& WithFlags(uint32 F)
    {
        RequiredFlags = F;
        return *this;
    }
    
    bool Matches(const FEntityData& E) const
    {
        if (RequiredFlags.IsSet() && (E.Flags & RequiredFlags.GetValue()) != RequiredFlags.GetValue())
            return false;
        if (Center.IsSet() && Radius.IsSet())
        {
            float DistSq = FVector::DistSquared(E.Location, Center.GetValue());
            if (DistSq > Radius.GetValue() * Radius.GetValue())
                return false;
        }
        return true;
    }
};

// 实体管理器
class FEntityManager
{
public:
    static constexpr uint32 ChunkSize = 32768;  // 32KB
    
private:
    TChunkedArray<FEntityData, ChunkSize> Entities;
    TMap<uint32, int32> IDToIndex;
    TArray<int32> FreeIndices;
    uint32 NextID = 1;
    
public:
    // 创建实体
    uint32 CreateEntity(const FVector& Location)
    {
        uint32 ID = NextID++;
        int32 Index;
        
        if (FreeIndices.Num() > 0)
        {
            Index = FreeIndices.Pop();
            Entities[Index] = FEntityData();
        }
        else
        {
            Index = Entities.Num();
            Entities.AddElement(FEntityData());
        }
        
        Entities[Index].EntityID = ID;
        Entities[Index].Location = Location;
        Entities[Index].Flags = 1;  // Active
        Entities[Index].Health = 100.0f;
        Entities[Index].MaxHealth = 100.0f;
        
        IDToIndex.Add(ID, Index);
        return ID;
    }
    
    // 通过 ID 获取
    FEntityData* GetByID(uint32 ID)
    {
        if (int32* Index = IDToIndex.Find(ID))
            return &Entities[*Index];
        return nullptr;
    }
    
    // 查询
    void Query(const FEntityFilter& Filter, TArray<uint32>& OutIDs)
    {
        OutIDs.Reset();
        for (const FEntityData& E : Entities)
        {
            if (E.EntityID != 0 && Filter.Matches(E))
                OutIDs.Add(E.EntityID);
        }
    }
    
    // 销毁
    void DestroyEntity(uint32 ID)
    {
        if (int32* Index = IDToIndex.Find(ID))
        {
            Entities[*Index].Flags |= 2;  // PendingKill
            Entities[*Index].Flags &= ~1; // Clear Active
        }
    }
    
    // 清理待销毁实体
    void Cleanup()
    {
        for (int32 i = 0; i < Entities.Num(); ++i)
        {
            if (Entities[i].IsPendingKill())
            {
                IDToIndex.Remove(Entities[i].EntityID);
                Entities[i] = FEntityData();
                FreeIndices.Add(i);
            }
        }
    }
    
    // 遍历活跃实体
    template<typename Func>
    void ForEachActive(Func&& F)
    {
        for (FEntityData& E : Entities)
        {
            if (E.IsActive())
                F(E);
        }
    }
    
    // 统计
    int32 Num() const { return Entities.Num(); }
    SIZE_T GetMemoryUsage() const { return Entities.GetAllocatedSize(); }
};

void Example()
{
    FEntityManager Manager;
    
    // 创建实体
    TArray<uint32> IDs;
    for (int32 i = 0; i < 10000; ++i)
    {
        FVector Loc(FMath::RandRange(-1000.f, 1000.f),
                    FMath::RandRange(-1000.f, 1000.f), 0);
        IDs.Add(Manager.CreateEntity(Loc));
    }
    
    // 修改实体
    if (FEntityData* E = Manager.GetByID(IDs[500]))
    {
        E->Health = 50.0f;
        E->MarkDirty();
    }
    
    // 查询附近实体
    TArray<uint32> NearbyIDs;
    FEntityFilter Filter;
    Filter.InRadius(FVector::ZeroVector, 500.0f).WithFlags(1);
    Manager.Query(Filter, NearbyIDs);
    
    // 遍历所有活跃实体
    Manager.ForEachActive([](FEntityData& E)
    {
        E.Location += FVector(1, 0, 0);
        E.MarkDirty();
    });
    
    // 销毁和清理
    Manager.DestroyEntity(IDs[100]);
    Manager.Cleanup();
    
    UE_LOG(LogTemp, Log, TEXT("Entities: %d, Memory: %.2f KB"),
        Manager.Num(), Manager.GetMemoryUsage() / 1024.0f);
}