C++ 手写 List 容器在游戏开发中的应用：动态实体管理

在游戏开发中，动态实体（如敌人、子弹、道具等）的数量和状态会实时变化。手写 List 容器通过高效的内存管理和操作特性，成为管理这类实体的理想选择。以下是核心应用场景和技术实现：

1. 为什么选择链表？

• 动态内存分配：实体数量不可预测，链表按需分配内存，避免预分配浪费
• 高效增删：插入/删除实体时间复杂度为 $O(1)$，优于数组的 $O(n)$
• 无内存碎片：节点分散存储，避免连续内存需求

2. 关键实现代码（C++ 双向链表）

template <typename T>
class GameEntityList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
    };

    Node* head = nullptr;
    Node* tail = nullptr;
    size_t size = 0;

public:
    // 添加实体到末尾
    void addEntity(const T& entity) {
        Node* newNode = new Node(entity);
        if (!head) head = tail = newNode;
        else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }

    // 删除指定实体
    void removeEntity(Node* target) {
        if (!target) return;
        
        if (target == head) head = head->next;
        if (target == tail) tail = tail->prev;
        
        if (target->prev) target->prev->next = target->next;
        if (target->next) target->next->prev = target->prev;
        
        delete target;
        size--;
    }

    // 帧更新遍历（示例）
    void updateAll() {
        Node* current = head;
        while (current) {
            current->data.update();  // 实体更新逻辑
            current = current->next;
        }
    }
    
    ~GameEntityList() { /* 遍历释放所有节点 */ }
};

3. 游戏开发中的典型应用

• 子弹管理系统

  GameEntityList<Bullet> activeBullets;
  void fireBullet() {
      activeBullets.addEntity(Bullet(player.position));
  }
  

  子弹生成时插入链表，命中目标后立即删除，避免数组移动开销。

• 敌人生成池
  $$ \text{实体复用率} = \frac{\text{回收敌人数量}}{\text{总敌人数}} \times 100% $$ 链表实现对象池：

  void spawnEnemy() {
      if (recycledEnemies.empty()) 
          activeEnemies.addEntity(new Enemy());
      else 
          activeEnemies.addEntity(recycledEnemies.popFront());
  }
  

• 特效粒子系统
  短生命周期粒子（如爆炸火花）高频增删：

  void updateParticles() {
      Node* curr = particleList.head;
      while (curr) {
          if (curr->data.lifetime <= 0) {
              Node* toDelete = curr;
              curr = curr->next;
              particleList.removeEntity(toDelete);  // O(1)删除
          } else {
              curr->data.updatePhysics();
              curr = curr->next;
          }
      }
  }
  

4. 性能优化策略

• 内存局部性补偿
  定期对频繁访问的实体（如附近NPC）进行局部排序： $$ \text{缓存命中率} \propto \frac{1}{\text{遍历步长}} $$
• 批处理操作
  帧末统一处理删除请求，避免多次内存分配
• 自定义分配器
  预分配节点内存池，减少 new/delete 开销

5. 对比 STL list 的优势

应用建议：在实体数量 > 1000 且高频增删的场景（如开放世界游戏），手写链表性能提升可达 15%~30%。建议结合组件模式，将链表节点作为 Entity 的成员变量，实现高效ECS架构。