C++实现Polygon类：内部存储结构选择vector还是链表

首先明确基础存储逻辑：开发时优先仅存储顶点集合，不要冗余存储边对象——边完全可以通过相邻顶点实时计算得到，冗余存储边只会带来数据一致性维护的额外负担（比如顶点修改后忘记同步边的端点，导致周长计算、边匹配的逻辑全错）。

为什么不选链表作为内部存储 #

• 链表的核心价值是任意位置的O(1)插入/删除、插入时不搬移已有元素，但在当前类需要实现的功能场景里，这个优势根本没有发挥空间：
  • 两个add接口的操作都是低频、小批量的：要么是往多边形末尾追加顶点，要么是找到匹配的已有边、在边中间插入新顶点拆分边。哪怕顶点数到几百个，用vector做遍历查找、插入搬移的耗时都是纳秒级的，用户完全感知不到性能差异。
  • 很多人看到有“在已有边中间插入新点”的操作，就本能觉得该用链表，但实际上这个操作在多边形场景里是低频操作，哪怕每次插入要搬移几十上百个点，耗时都不到1微秒，根本不是性能瓶颈。真正的高频操作是遍历所有顶点算周长、打印顶点，这部分恰恰是链表的弱项。
  • 链表的反向代价非常高：每个节点要存前后指针，内存散落在堆各处，遍历顶点计算周长、print输出的时候，CPU缓存命中率极低，实际运行效率比连续内存的vector差好几倍。同时手动维护链表指针容易出悬空指针、内存泄漏的问题，开发和调试成本反而更高。

为什么std::vector是最优适配 #

• 连续的内存布局，对顺序遍历类的操作（算周长、打印顶点）性能最优，同等顶点数下的内存开销比链表低至少1/3。
• 初始的三点构造器可以直接预分配3个元素的容量，后续add顶点的增量场景，vector的自动扩容机制完全能覆盖，不需要手动管理内存。
• 针对bool add(Line & exist, Point & p)的接口逻辑：只需要顺序遍历vector里的相邻顶点对，找到和传入的exist边完全匹配的端点对，再在两个顶点的位置中间插入新点即可。哪怕vector插入时需要搬移后续元素，因为多边形的顶点规模通常很小，这个开销完全可以忽略。

参考的私有成员声明 #

可以直接在类的私有区写对应的存储结构：

private:
    std::vector<Point> m_vertices; // 仅存储多边形顶点，边实时计算

什么时候才需要考虑换链表？只有当你的多边形应用场景是顶点数破万、且需要频繁在中间位置插入/删除顶点的时候，再考虑链表或者其他关联容器，常规的2D多边形计算场景根本用不着。

内容的提问来源于stack exchange，提问作者strangledstranger