先问数据必须做什么
别从"该用哪种结构？"出发。要从"我需要哪些操作快？"出发。按位置读取？在某一端添加？按名字查找？每种结构天生就是某些操作快、某些操作慢。把结构匹配到你*最高频*的那个操作上。
再问几个问题也有帮助：大小是固定的，还是会增长？我在意元素到达的顺序，还是只关心某个东西在不在？在这里多想两分钟，能省下你日后把一个慢的 O(n) 循环改写成快循环的功夫。把你的问题对照下面这张清单走一遍。
- 需要按下标读写（第 5 个元素）？-> 数组（或 std::vector）。
- 需要后进先出（撤销、调用栈、回溯）？-> 栈。
- 需要先进先出（公平调度、BFS）？-> 队列。
- 需要按键快速查找/插入/删除（名字 -> 值）？-> 哈希表。
- 既要有序、又要快速查找？-> 树（下文预告）。
代价速查表
整整一阶的内容，浓缩成一张卡片。"平均"对哈希表尤为关键——它最坏是 O(n)，但只要哈希得当，你很少碰到。记住这张表的*形状*，而非每个格子的精确值；形状才是指引你选择的东西。
structure access search insert delete ----------- ------- ------- -------- -------- array O(1) O(n) O(n)* O(n)* linked list O(n) O(n) O(1)** O(1)** stack O(1) top -- O(1) push O(1) pop queue O(1) ends -- O(1) enq O(1) deq hash table -- O(1) avg O(1) avg O(1) avg * array insert/delete is O(1) only at the very end ** linked list O(1) only once you HOLD a pointer to the spot
几个真实的取舍
把这些问题套到真实任务上。"统计一本书里每个单词出现的次数。"你需要查一个单词并给它的计数加一——按键快速查找——所以哈希表（`std::unordered_map<std::string,int>`）胜出。
"按提交顺序处理打印任务。"到达顺序、从队首服务——这是队列。"实现撤销。"最近的操作最先被回退——栈。"存储 256 个固定像素值，会不断按下标读取。"纯按下标访问——数组。
那么"一个总是在中间插入和删除、从不按下标访问的列表"呢？这正是链表难得的用武之地——一旦握有指向那个位置的指针，修改就是 O(1)。
当线性结构不够用：树的预告
有一种组合是这四者都搞不定的：既保持元素有序、又能快速查找。哈希表快但无序；有序数组保持顺序，但插入是 O(n)。答案是一种有分支、而非单一直线的结构——树，尤其是二叉搜索树，它能提供 O(log n) 的有序查找和插入。
(8)
/ \
(3) (10)
/ \ \
(1) (6) (14)
ordered + fast: each step halves the search -> O(log n)那是下一阶的内容。眼下的收获是一个习惯：动手写代码前，先把你需要的操作一一点名，再挑出代价与之匹配的结构。结构是一个*决策*，而不是一个*默认值*。