通用容器虽然好，在线评测限制多

在内存严格受限的工程类编程竞赛中，标准 Python 字典（ dict ）往往因底层哈希表的高内存开销而成为性能瓶颈。然而，许多题目不仅要求实现“键到值”的映射，还隐含一个更关键的需求：给定一个键，不仅要查到其对应的值，还要能快速定位它在原始输入序列中首次出现的位置（索引）。这种“带位置信息的双向查询”能力，是普通字典无法直接提供的。本文介绍一种完全不依赖  dict  的轻量级方案，仅通过  list  与  set  的组合，即可同时支持正向查值与反向查位置，并能高效处理动态增量数据。

初始构建阶段，将全部输入数据按顺序存入一个列表  raw 。该列表天然保留了每个元素的插入顺序，其索引即为原始位置。随后，将  raw  转换为集合  all_keys_set ，利用  set  的哈希特性自动去重，得到所有唯一键。由于  set  无序，需将其转为排序后的列表  keys ；与此同时，遍历  raw ，为每个唯一键记录其首次出现的索引，形成位置列表  positions 。关键在于： keys  和  positions  必须按相同的排序规则（如按键值升序）对齐，使得对于任意索引  i ， keys[i]  对应的原始位置就是  positions[i] 。

此时，整个结构由三部分组成：原始数据列表  raw 、排序后的唯一键列表  keys 、以及与之对齐的位置索引列表  positions 。查询操作分为两步：

若需通过键  k  查值，先在  keys  中找到其索引  i （可用二分查找），再通过  p = positions[i]  得到原始位置，最终值为  raw[p] ；

若只需查位置，同样找到  i  后直接返回  positions[i]  即可。
由于  raw[p]  就是键  k  本身（在去重场景中值与键一致），甚至可省略额外的值存储，进一步节省内存。

当系统需要支持动态更新时——例如多轮输入或流式数据到达——该结构仍可高效扩展。具体流程如下：新一批数据被直接  append  到  raw  末尾。接着，将这批新增数据单独转为临时集合  new_batch_set ，并与当前已有的键集合  existing_key_set  做差集运算（ new_keys_set = new_batch_set - existing_key_set ），从而精确识别出本轮真正新增的键（排除重复项）。

对这些新增键，遍历其在  raw  中的实际出现位置（因是追加，位置可直接计算），记录为  new_positions 。然后，将  new_keys_set  转为列表并排序，同时按相同顺序整理  new_positions ，确保二者局部对齐。最后，将  new_keys  与原有  keys  合并（可拼接后整体重排，或采用归并保持有序）， new_positions  也同步合并，形成更新后的全局映射。原有的  existing_key_set  也随之更新为  existing_key_set | new_keys_set ，用于下一轮差分。

这一机制的核心优势在于：

精准增量：通过集合差集，只处理真正新增的键，避免重复计算；

位置可追溯：无论静态还是动态场景，每个键始终关联其首次出现的原始索引；

内存紧凑：仅使用  list  存储数据与位置， set  仅作临时去重与差分，无哈希表空槽浪费；

双向查询：既支持“键→值”，也支持“键→位置”，满足竞赛中常见的上下文定位需求。

该方法已在多场嵌入式算法赛与内存限制严格的在线评测中验证有效。它揭示了一个重要原则：在资源受限环境下，放弃通用容器、回归基础结构、显式管理元信息，往往是突破性能瓶颈的关键#牛客AI配图神器#