我相信这一定在某种教科书中(或更可能是所有教科书中),但我似乎使用了错误的关键词来搜索它... :(
编程时我经常面临的一个任务是处理来自不同来源的对象列表,我需要以某种方式将它们保持同步。通常有一些“主列表”,例如由一些外部API返回,然后我自己创建的对象列表,每个对象对应于主列表中的一个对象(类似"包装器"或"适配器",它们通常包含特定于我的应用程序的外部对象的扩展信息和/或简化访问外部对象)。
问题实例的硬性特征:
- 我无法访问主列表的实现;其接口是固定的
- 两个列表中的元素不能进行赋值
- 我完全控制从列表的实现
- 我无法控制主列表中元素的顺序(即不可排序)
- 主列表要么根本不提供有关添加或删除元素的通知,要么通知不可靠,即同步只能按需发生,而非实时发生
- 简单地清除并重建从头开始所需的从列表不是选项:
- 初始化包装器对象应被视为昂贵的
- 其他对象将持有对包装器的引用
问题实例的其他特点:
- 主列表中的元素只能通过读取其属性而不是直接通过索引或内存地址访问来标识:
- 刷新后,主列表可能返回一组全新的实例,尽管它们仍然表示相同的信息
- 访问主列表中元素的唯一接口可能是一个连续的枚举器
- 大多数情况下,主列表中元素的顺序是稳定的,即新元素总是添加在开头或结尾,永远不会在中间添加;但是,删除通常可以发生在任何位置
那么我通常如何解决这个问题呢?我应该搜索什么算法的名称?
过去我曾以多种方式实现过这个问题(请参见下面的示例),但总觉得应该有一种更清洁和高效的方式,特别是不需要两次迭代(每个列表一次)。
下面是一个示例方法:
- 迭代主列表
- 在“从属列表”中查找每个项
- 添加尚不存在的项
- 以某种方式跟踪已经存在于两个列表中的项目(例如通过标记它们或保持另一个列表)
- 完成后,迭代从属列表并删除所有未被标记的对象(请参见4.),然后再次从所有其他对象中清除标记
更新1
感谢大家迄今为止的回复!我需要一些时间来查看链接。
[...] (文本移动到问题正文中)
更新2 将中间段落重构为(希望)更易于解析的项目列表,并包含在第一个更新后添加的详细信息中。