c++ - 方形和对称表的数据类型

Question

我有一个按行和列访问的表，其中这两者不是整数。但是，它们将是独一无二的，并且来自同一组。表格需要扩展，但总是从末尾开始。可能需要从中间移除，但不是优先事项。

我目前正在测试两种方法:

map<Key, int> headers;
vector<vector<Value> > table;

或者:

map<Key, map<Key, Value> > table;

哪个更合适？我也愿意接受新的建议。

显示基本用法的示例(虽然都非常简单)是 here和 here .

Answer 1

这完全取决于这个结构将如何使用:表格的填充密度，各种操作的效率，负载类型(Value)的大小，等

您的第一种方法( vector 的 vector ，使用映射来转换索引)是一种密集表示:每个值都明确存储在表中。如果 vector 增长 L 倍，则数据本身的总分配超额可以上升到 L^2。例如，如果 L == 1.25，您最终可能会有超过 50% 的超额存储；如果 sizeof(Value) 很大或者您的表很大，这可能会让人望而却步。此外，扩展表有时可能会非常昂贵(当必须重新分配 vector 时)。

您的第二种方法( map 的 map )可能是稀疏的。但是，如果访问所有表(行、列)对，它将变得密集。此外， map 的簿记信息比 vector 的要大一些。因此，对于较小的 Value 大小， vector 方法的 vector 可能更节省空间。如果您的大部分表将由“默认”值填充，那么您可以通过区分对表的读取和写入访问来改进:读取值可以执行“查找”并返回合成的默认值(如果有显着条目)被发现了。