C++代码模拟器中交叉开关阵列的最优数据结构选型咨询

问题概述 #

开发C++代码模拟器时，需要存储并操作符合特定格式的交叉开关阵列数据，要求支持动态内存分配，核心操作是基于行信号、列信号和交叉点历史值计算新的交叉点值。目前在std::vector和std::map之间犹豫，寻求最优数据结构方案。

输入与结构说明 #

输入文件示例 #

0 TRUE 3 FALSE 2 FALSE
0 FALSE 1 0x3 3 0x2

语法规则 #

rowNumber signal@rowNumber colNumber1 signal@colNumber1 colNumber2 signal@colNumber2 ..... colNumberN signal@colNumberN
注：每行前两项为行相关值，后续项为对应列的详情

目标交叉开关阵列结构 #

0   1   2   3
    |   |   |   |  
0- [x] [y] [ ] [ ]
1- [ ] [ ] [ ] [ ]
2- [ ] [ ] [ ] [ ]
3- [ ] [ ] [ ] [ ]

核心操作 #

• 交叉点值计算：例如x的值 = minimum(signal@row0, signal@column0, x的历史值)，y的值 = minimum(signal@row0, signal@column1, y的历史值)
• 动态扩容：阵列初始大小未知，需根据输入数据自动调整规模

推荐方案分析 #

1. 最优选择：嵌套std::vector（二维动态数组） #

适配理由：

• 动态扩容便捷：std::vector原生支持动态内存管理，读取数据时可通过resize()快速扩展到所需的行/列规模，无需手动管理内存。
• 访问效率极高：连续内存存储，随机访问时间复杂度为O(1)，完美匹配交叉开关阵列的行列直接访问需求（快速获取行信号、列信号、交叉点历史值）。
• 空间利用率高：如果阵列属于稠密结构（大部分交叉点会被使用或填充），连续内存的空间浪费远低于哈希表或树结构。

实现思路：

• 用外层std::vector存储每行数据，每个行元素包含该行的信号值，以及一个内层std::vector存储该行各列交叉点的状态（含历史值）。
• 额外维护两个独立的std::vector：一个存储所有行的信号值，一个存储所有列的信号值，便于快速获取signal@rowN和signal@colM。
• 读取输入行时，先检查行号是否超出外层vector的大小，超出则扩容；同理处理列号对应的内层vector。

2. 备选方案：std::unordered_map（稀疏场景） #

如果交叉开关阵列是稀疏结构（大部分行列交叉点无有效数据），使用std::unordered_map存储有效交叉点更节省空间：

• 键采用std::pair<int, int>（行号+列号）或自定义哈希结构体，值存储交叉点的历史值等数据。
• 行/列的信号值用单独的std::unordered_map<int, SignalType>存储（SignalType根据实际需求定义为bool、整数等类型）。
• 缺点：平均访问时间复杂度为O(1)，最坏情况为O(n)，比std::vector的连续访问慢，仅适合数据量小且稀疏的场景。

3. 不推荐std::map #

std::map基于红黑树实现，访问时间复杂度为O(logn)，性能弱于std::vector和std::unordered_map。除非你需要对行列号进行有序遍历（而你的场景核心是交叉点计算，有序遍历并非刚需），否则无需考虑。

总结 #

• 若阵列是稠密结构，优先选择嵌套std::vector，兼顾访问速度与空间效率。
• 若阵列是稀疏结构，选择std::unordered_map存储交叉点，配合单独的map存储行/列信号值，减少空间浪费。

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