我有一个按行和列访问的表,其中这两者不是整数。但是,它们将是独一无二的,并且来自同一组。表格需要扩展,但总是从末尾开始。可能需要从中间移除,但不是优先事项。
我目前正在测试两种方法:
map<Key, int> headers;
vector<vector<Value> > table;
或者:
map<Key, map<Key, Value> > table;
哪个更合适?我也愿意接受新的建议。
最佳答案
这完全取决于这个结构将如何使用:表格的填充密度,各种操作的效率,负载类型(Value
)的大小,等
您的第一种方法( vector 的 vector ,使用映射来转换索引)是一种密集表示:每个值都明确存储在表中。如果 vector 增长 L 倍,则数据本身的总分配超额可以上升到 L^2。例如,如果 L == 1.25,您最终可能会有超过 50% 的超额存储;如果 sizeof(Value)
很大或者您的表很大,这可能会让人望而却步。此外,扩展表有时可能会非常昂贵(当必须重新分配 vector 时)。
您的第二种方法( map 的 map )可能是稀疏的。但是,如果访问所有表(行、列)对,它将变得密集。此外, map 的簿记信息比 vector 的要大一些。因此,对于较小的 Value
大小, vector 方法的 vector 可能更节省空间。如果您的大部分表将由“默认”值填充,那么您可以通过区分对表的读取和写入访问来改进:读取值可以执行“查找”并返回合成的默认值(如果有显着条目)被发现了。
关于c++ - 方形和对称表的数据类型,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9880539/