有没有一种方法来压缩矢量（C++）？

我有一个人口稀疏的矢量，我通过哈希填充，所以元素随机散布在矢量中。现在我想要做的是迭代该向量中的每个元素。我脑海中想到的主要是凝聚矢量以适应当前元素的数量，去除任何空白空间。有什么办法可以做到这一点？有没有一种方法来压缩矢量（C++）？

2010-04-01 zebraman

这是什么向量？你怎么知道一个元素是否被使用？ – 2010-04-01 08:58:33

显然，第一个想法是查看是否可以使用std :: tr1 :: unordered_map（http://www.boost.org/doc/libs/1_36_0/doc/html/boost/unordered_map.html）。它包含迭代器。 – stefaanv 2010-04-01 09:00:42

为什么不使用'unordered_map'？ – kennytm 2010-04-01 09:00:44

您可以在插入元素的过程中保存额外需要的信息（例如链接到上一个/下一个元素与链接列表的链接），或者将所有元素传递一遍并删除不必要的信息。

第一种解决方案需要一定的空间（大约8字节/条目），第二种解决方案需要花费所有元素。根据情况，一个或两个可能性可能没有用处。

来源

2010-04-01 09:02:35

旁边的空间成本，你也有插入/擦除期间的簿记成本（包括找到上一个/下一个条目）。 – stefaanv 2010-04-01 09:20:04

可以使用运行长度编码的版本进行压缩。
您会遍历原始矢量并创建一个新的“压缩”矢量，该矢量包含交替值 - 从原始值开始的值以及到下一个值的空白空间的计数。例如这样的：

3 - - - - 4 - - 7 3 - - - 9 -

变成这样：

3 4 4 2 7 0 3 3 9 1

来源

2010-04-01 09:04:24 shoosh

有没有一种方法来压缩矢量（C++）？

回答

相关问题