最近把贪吃蛇用 C++ 重新写了一遍，数据容器选的是 set 和 deque。这个小项目做完，我对这两个容器的理解比看十页文档都深。如果你也在准备课程设计，或者想借一个游戏项目把 STL 容器用熟，这篇文章可以参考着抄作业。

贪吃蛇看起来简单，但它的数据需求其实挺有意思：它不仅要维护一条“身体顺序”，还要随时回答“某个坐标是不是被身体占着”。deque 和 set 的组合正好各管一项。我先把结论放前面：deque 管蛇身的先后顺序和两端的进出，set 管碰撞检测和食物生成时的坐标查询。两个容器里存的是同一组坐标，必须同步更新。

1. 贪吃蛇的数据难题：身体要动，身体也要查

1.1 蛇的两种核心操作

任何一版贪吃蛇，玩法都绕不开两件事。

第一件事是移动。每一帧蛇头向前一格，蛇身跟着走：普通移动时，尾巴同步收缩，身体长度不变；吃到食物时，尾巴保留，身体长度加一。从数据操作上看，这就是“头部插入一个新坐标，尾部看情况删除一个旧坐标”。

第二件事是判定。每走一步之前必须回答三个问题：新蛇头是不是撞墙了？新蛇头是不是咬到了自己的尾巴？新蛇头是不是正好踩在食物上？

这两个需求对数据结构提出的要求是相反的：移动要求两端操作都高效，判定要求“给定一个坐标，快速判断它当前有没有被蛇身占领”。如果你用一个数组从头到尾存蛇身，移动勉强能做，但查询就得从头遍历到尾。如果你用二维数组标记地图，移动和查询都快，但地图状态和蛇身状态混在一起，后面加多蛇、穿墙、障碍物时很难扩展。所以我在这个版本里选择了 deque 加 set 的组合：deque 管“顺序和形状”，set 管“坐标是否存在”。

1.2 数组与 vector 方案的问题

很多课设版本的贪吃蛇用的是vector<pair<int,int>>，每条蛇是一个坐标数组，蛇头放在 back，移动时push_back新头，再用erase(begin())删掉旧尾巴。问题出在erase(begin())这一步：vector 删除头部元素时，要把后面所有元素整体往前搬一格，复杂度是 O(n)。蛇短的时候无所谓，蛇一长就能感受到卡顿，虽然不是量级上的崩溃，但这种“每次移动都要搬移整条身体”的写法，看着就不太对。

还有更常见的“二维数组染色”方案：开一个int map[H][W]，蛇身的每个格子标成 1，移动时把旧尾巴位置改成 0，新头位置改成 1。这个方案查询很快，但它把“蛇身”和“地图”耦合在一个数组里。如果你以后想支持两条蛇对战，或者蛇身有不同部位、不同颜色，就得在这个数组里塞一堆额外状态，越写越复杂。而且数组方案很难回答“这条蛇第 5 节到底在哪”，因为数组里只有标记，没有顺序信息。

1.3 set 和 deque 的分工逻辑

我的方案很直接：用std::deque<Point>按顺序保存蛇身坐标，用std::set<Point>保存同样这一组坐标的无序集合。deque 是蛇身体的“骨架顺序”，set 是“身份登记表”。

打个比方：deque 像一条真实的蛇骨架，每一节从尾巴到脑袋排得清清楚楚；set 像一张花名册，你报一个坐标，它立刻告诉你这个坐标是不是蛇的地盘。查碰撞时用花名册，维护顺序时用骨架，各司其职。

要付出的代价是两份数据同步：deque 里新增一节，set 里也要 insert；deque 里删掉尾部，set 里也要 erase。这套同步契约是所有后续代码的基础，后面我会专门讲这里踩过的坑。

2. deque 做蛇身：头插尾删才是移动的本质

2.1 deque 容器特性回顾

std::deque是双端队列，允许在头部和尾部都以 O(1) 复杂度插入、删除元素，同时支持下标随机访问，也就是body[2]这种操作依然成立。

它内部通常是分段连续内存：数据被切成固定大小的块，块与块之间由一个中控数组管理。所以往两端插入删除时，不需要像 vector 那样把所有元素搬走，只需要操作对应内存块；也不像 list 那样每个节点单独分配内存，导致位置分散、缓存命中率低。这种“两端都能动、又能按下标取元素”的特性，正是贪吃蛇蛇身需要的。

2.2 蛇的移动就是标准的头插尾删

蛇移动的本质，是“头往前走一格，尾巴跟上来一格”。

不加速的时候：新头坐标算出来，body.push_front(newHead)把新头插到最前面，然后body.pop_back()把旧尾巴删掉。整个过程中蛇身元素数量不变，但 deque 内部头尾各操作一次，都是 O(1)，每一步移动都非常干净。

加速的时候（吃到食物）：只做body.push_front(newHead)，不删尾巴。头部多出一格，身体长度加一。这个“只看尾巴动不动”的模型，比用长度计数器去修改数组要直观得多。

在 C++ 里写出来就是：

body.push_front(newHead); if (!eat) { body.pop_back(); }

就这么两行，没有循环，没有元素搬移。deque 的接口设计几乎是为这个场景量身定做的。

2.3 为什么不选 vector 和 list

选容器的时候其实我列过一个对比表：

list也是个容易被新手选中的选项，因为蛇身看起来就是“一串节点”。但 list 最大的问题是不能随机访问：以后你想让蛇身第 5 节变个颜色、让第 10 节变成宝石身，list 就得从头遍历到目标位置。deque 直接用下标就能取到。所以在“顺序容器”这个维度上，deque 是最合适的选择。

3. set 做碰撞检测：把自撞判定变成一次查找

3.1 碰撞检测本质是“坐标是否在集合里”

算出新头位置之后，判断有没有撞到身体，本质上就是回答一个问题：这个坐标现在是不是属于蛇身？这就是经典的集合成员查询。

如果你只在 deque 里存蛇身，就要写一个循环从头到尾查一遍：

bool hit = false; for (const auto& p : body) { if (p == newHead) { hit = true; break; } }

这段代码能跑，但它把“判断某个坐标是不是蛇身”这个问题，退化成了一遍线性扫描。而 set 生来就是干这件事的：find、count、insert、erase的时间复杂度都是 O(log n)，n 是蛇身长度。自撞判定变成一次查找：

if (occupied.find(newHead) != occupied.end()) { // 撞到自己了 }

更重要的是代码意图非常清楚。读代码的人不需要从一个循环里推导“这是在查碰撞”，看到occupied.find就知道你在做成员判断。

3.2 为什么用 set 而不是 unordered_set

set 底层通常是一棵红黑树，元素自动有序。我优先选 set 而不是unordered_set，有几个原因。

第一，蛇身坐标需要定义排序关系，也就是operator<，set 正好需要；unordered_set还需要额外写哈希函数，对Point这种小结构来说有点多余。

第二，红黑树的插入、删除、查找复杂度稳定，不会有哈希表扩容、重哈希的最坏情况。在贪吃蛇这个规模下，O(log n) 和 O(1) 的差别感知不到，但代码更简单。

第三，set 的有序性在调试时很友好。我经常打日志看occupied里都有哪些元素，set 打印出来是一串有序坐标，一眼能看出 set 和 deque 是否同步。如果用哈希表，打印出来的顺序是乱的，排查问题时反而不方便。

3.3 生成食物同样依赖 set

食物生成也必须判断“随机选出来的格子是不是已经被蛇占了”。最简单的写法是不断随机坐标，直到落在空位上。蛇身短时这个策略很快，但蛇快占满地图时，随机命中空位的概率很低，极端情况下会死循环。

所以我干脆遍历整个地图，把不在occupied里的坐标收集到一个vector，再从vector里随机选一个作为食物：

vector<Point> emptyCells; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { Point p(x, y); if (occupied.find(p) == occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food = emptyCells[rand() % emptyCells.size()]; }

这个做法是稳定的，不会出现随机死循环。而且每次判断都用 set，不需要针对每个空格再去遍历一遍 deque。

4. 核心逻辑串起来：移动、进食、死亡判定

4.1 坐标类型与方向状态机

坐标用Point结构体，包含 x、y 两个 int。它必须实现operator<，set 依赖这个排序关系；还要实现operator==，用来判断蛇头是否踩到食物、绘制时比较坐标。

方向用两个 int 表示单位向量：dirX和dirY。按 W 时dirY=-1，按 S 时dirY=1，按 A 时dirX=-1，按 D 时dirX=1。按键处理里必须有一个“禁止原地掉头”的判断：

if (ndx == -dirX && ndy == -dirY) return;

为什么这个判断重要？因为蛇向左走时，你按 D 想去右边，新头会直接穿回自己脖子那一节，这是游戏规则不允许的。挡住掉头，比在 tick 里再处理要好，因为改方向时直接拒绝，游戏逻辑更清晰。

4.2 一步移动的完整流程

每帧执行的 tick 函数按这个顺序处理：

1. 取蛇头body.front()，根据当前方向算出newHead。
2. 撞墙判定：newHead超出地图范围就置 running 为 false。
3. 判断是否吃到食物：newHead == food。
4. 自撞判定：在occupied里查找newHead。
5. 执行移动：body.push_front(newHead)，同时occupied.insert(newHead)。
6. 没吃到食物就删尾巴，吃到食物就保留尾巴。
7. 吃到食物时得分加一，重新生成食物，并检查胜利。

排列顺序上要注意：所有碰撞判定都发生在真正修改蛇身之前。你不能先 push_front 再查碰撞，因为那样等于把新头当成自己的身体去查，永远查不到。

4.3 “尾巴特判”：最容易写错的碰撞分支

自撞判定有一个非常隐蔽的细节：新蛇头撞上自己尾巴时，如果这一帧没有吃到食物，其实是合法的。

原因是：下一秒尾巴就要被 pop_back 移走，蛇头进入的位置正好空出来，不会撞上。但如果这一帧吃到食物，尾巴保留不动，那么新头踩到尾巴就是真撞上。

所以判断不能写死成“集合里有这个坐标就死”：

if (occupied.find(newHead) != occupied.end()) { Point tail = body.back(); // 不吃食物时，尾巴马上会移走，撞尾巴是允许的 if (!(newHead == tail && !eat)) { running = false; return false; } }

我第一次实现时漏掉了这个特判，蛇越长越容易在转身时离奇死亡，排查了很久才发现是这里的问题。这也是 set 和 deque 必须同步维护的又一个体现：判断需要用 deque 的back()拿到尾巴坐标，结合是否吃食物来修正结果。

4.4 食物生成与胜利条件

胜利条件不是“分数到了某个固定值”，而是蛇身长度占满整个地图。初始长度是 1，每吃一个食物长度加一，所以胜利时score == width * height - 1。

这个判断要放在生成食物之前，否则地图满了时，spawnFood的emptyCells是空的，随机取食物会失败。代码里是这样：

if (score == width * height - 1) { victory = true; running = false; return true; } spawnFood();

5. 完整可运行的控制台版贪吃蛇

5.1 完整代码（C++17）

到这里，我把完整代码贴出来。这个版本是 Windows 控制台版，用conio.h处理即时按键，用windows.h的Sleep控制帧间隔。核心的 deque 和 set 逻辑不依赖平台。

// snake.cpp 贪吃蛇：set + deque 版本 #include <cctype> #include <conio.h> #include <cstdlib> #include <ctime> #include <deque> #include <iostream> #include <set> #include <vector> #include <windows.h> using namespace std; struct Point { int x, y; Point(int px = 0, int py = 0) : x(px), y(py) {} bool operator<(const Point& other) const { if (x != other.x) return x < other.x; return y < other.y; } bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; class SnakeGame { int width, height; deque<Point> body; set<Point> occupied; Point food; int dirX, dirY; int score; bool running; bool victory; public: SnakeGame(int w = 24, int h = 12) : width(w), height(h), dirX(1), dirY(0), score(0), running(true), victory(false) { Point start(width / 2, height / 2); body.push_back(start); occupied.insert(start); spawnFood(); } void changeDir(char key) { int ndx = 0, ndy = 0; switch (tolower(key)) { case 'w': ndx = 0; ndy = -1; break; case 's': ndx = 0; ndy = 1; break; case 'a': ndx = -1; ndy = 0; break; case 'd': ndx = 1; ndy = 0; break; default: return; } if (ndx == -dirX && ndy == -dirY) return; dirX = ndx; dirY = ndy; } bool tick() { if (!running) return false; Point head = body.front(); Point newHead(head.x + dirX, head.y + dirY); if (newHead.x < 0 || newHead.x >= width || newHead.y < 0 || newHead.y >= height) { running = false; return false; } bool eat = (newHead == food); if (occupied.find(newHead) != occupied.end()) { Point tail = body.back(); if (!(newHead == tail && !eat)) { running = false; return false; } } body.push_front(newHead); occupied.insert(newHead); if (eat) { score++; if (score == width * height - 1) { victory = true; running = false; return true; } spawnFood(); } else { Point tail = body.back(); body.pop_back(); occupied.erase(tail); } return true; } void draw() const { system("cls"); for (int y = -1; y <= height; y++) { for (int x = -1; x <= width; x++) { if (x == -1 || x == width || y == -1 || y == height) { cout << '#'; continue; } Point p(x, y); if (p == body.front()) { cout << '@'; } else if (occupied.find(p) != occupied.end()) { cout << 'O'; } else if (p == food) { cout << '*'; } else { cout << ' '; } } cout << '\n'; } cout << "Score: " << score << '\n'; } bool isRunning() const { return running; } bool isVictory() const { return victory; } int getScore() const { return score; } private: void spawnFood() { vector<Point> emptyCells; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { Point p(x, y); if (occupied.find(p) == occupied.end()) { emptyCells.push_back(p); } } } if (!emptyCells.empty()) { food = emptyCells[rand() % emptyCells.size()]; } } }; int main() { srand((unsigned)time(nullptr)); SnakeGame game(24, 12); while (game.isRunning()) { game.draw(); while (_kbhit()) { char key = _getch(); if (key == 'q' || key == 'Q') { cout << "Quit.\n"; return 0; } game.changeDir(key); } game.tick(); Sleep(150); } game.draw(); if (game.isVictory()) { cout << "You Win! Final Score: " << game.getScore() << '\n'; } else { cout << "Game Over! Final Score: " << game.getScore() << '\n'; } return 0; }

5.2 编译与运行方式

在 Windows 控制台或 MinGW 环境下，用这条命令编译：

g++ -std=c++17 snake.cpp -o snake.exe

运行起来之后，地图是一个 24 乘 12 的方框，蛇头是@，蛇身是O，食物是*。WASD 控制方向，按 Q 直接退出。程序默认每 150 毫秒走一步，蛇会一直向当前方向前进，直到你按键转向或者撞上边界、撞上自己。

如果你在 Linux 或者 macOS 上想跑，conio.h和windows.h都不能直接用。最省事的方案是把输入改成termios非阻塞模式，把Sleep换成nanosleep，或者干脆装 ncurses 重写输入部分。核心的 deque 和 set 逻辑完全可以原样搬过去，平台差异只影响输入输出层，不影响数据结构和游戏逻辑。

5.3 运行效果与结构说明

跑起来之后，你会发现几个细节：

• 食物不会生成在蛇身上，因为生成逻辑用occupied做了判断。
• 蛇头碰到自己尾巴的前一刻，如果尾巴即将移走，游戏不会误判死亡。
• 蛇身越来越长之后，移动依然流畅，因为每次移动只做常数次 deque 操作和几次 O(log n) 的 set 操作。
• 地图被占满时，游戏提示 You Win，而不是进入死循环等食物。

结构上，我把数据和逻辑都封在SnakeGame类里。body和occupied两个成员就是核心数据结构；tick负责一步的状态推进；draw负责渲染；spawnFood负责生成食物。以后想加功能，比如速度递进、穿墙模式、障碍物，都是在这个类上做增量修改。

6. 实测中踩过的坑：set 和 deque 的同步维护

6.1 改了 deque 忘了改 set，碰撞判定直接失效

这套组合容器最大的坑就是两份数据不同步。我有一次重构时只写了body.push_front(newHead)，忘了同时occupied.insert(newHead)。结果画面里蛇正常移动，但 set 里始终只有最初几个坐标。后果是蛇头撞上后半段身体时，set 根本查不到那个坐标，蛇直接从自己身上穿过去，怎么死的都不知道。

反过来也一样：只body.pop_back()但忘了occupied.erase(tail)，set 里会残留一堆已经不存在的坐标，蛇走到某个空位会莫名判定死亡。

我的经验是：把“同步更新”当成一个固定动作，每次写移动代码时把这两个容器的操作放在一起，push_front 和 insert 在同一段，pop_back 和 erase 在同一段。宁可代码看起来啰嗦，也不要把同步拆得太散。

6.2 键盘方向与逻辑方向打架

另一个容易出问题的地方是按键方向和 tick 的执行顺序。如果你把按键处理放在 tick 之后，按下的方向要到下一帧才生效，手感会明显迟钝。我的写法是每帧先绘制，然后立刻清空键盘缓冲区读取最新方向，最后才 tick。这样按键到下一条指令之间的延迟只有一个 Sleep 间隔。

还有一个取舍问题：用if (_kbhit())一次只读一个键，连续快速按键时会丢操作；用while (_kbhit())循环读，会把同一帧里的多次按键归并成最后一次。我的代码选择后者，确实会有“上、左”变成“只剩左”的情况，但至少蛇不会出现慢半拍转向。如果你更追求跟手，可以改成一次只读一个键，把帧率调高。这个取舍没有绝对标准。

6.3 随机生成食物的死循环隐患

食物生成如果写成下面这样：

while (true) { Point p(rand() % width, rand() % height); if (occupied.find(p) == occupied.end()) { food = p; break; } }

蛇身短的时候没问题，但蛇快占满地图时，随机命中空位的概率越来越低，循环次数会指数上升，极端情况下直接卡死。我的spawnFood改成收集所有空格再随机选，从根本上避免了这个问题。空位收集也正好用 set 的查找，一举两得。

6.4 绘制地图时 set 的另一个用武之地

draw函数里遍历整个地图，对每个格子都要判断“这是不是蛇身”。如果没有 set，就得在 deque 里再写一层循环。地图 24 乘 12 有 288 格，蛇长 100 时是 28800 次比较，代码还会嵌套得很深。有了 set，一个find搞定，绘制逻辑清清楚楚。

这个场景顺带说明了一件事：只要游戏里的任意位置需要回答“某个坐标在不在蛇身上”，都可以直接交给 set。撞墙判断、食物生成、地图绘制、以后要做雷达图、碰撞特效，都是同一个查询接口。

6.5 一个诚实的结论：性能不是唯一理由

最后补一句实话：以贪吃蛇的地图规模，就算你用 vector 加 find，每帧做几次线性扫描，计算机也不会卡。蛇身最长也就几百个格子，性能根本不是瓶颈。我坚持用 set 配 deque，更看重的是容器语义和代码可读性：deque 天然表达“两端操作的身体序列”，set 天然表达“坐标是否存在”的集合。你写代码的时候，不用去想“这里应该用哪个容器”，而是“这个问题需要什么样的操作”，容器自己就跳出来了。

最后说一个我个人的习惯：我把 set 成员命名为occupied，而不是bodySet。因为 set 里保存的语义是“哪些坐标已经被占用”，这样在spawnFood、draw、tick里读代码时，意图非常明确。容器命名跟着语义走，比跟着类型走好维护得多。你以后写自己的游戏，也可以试试这个习惯。