CpC*_*d0y 2 c++ algorithm vector c++11
我想实现一个算法,我偶然发现了描述DICE的"交换技巧" 这里(幻灯片19).
根据我的理解,我们首先创建一个包含所有元素的向量,然后当需要删除一个元素时,它与最后一个元素交换,我们减少向量的"大小".这个"大小"是一个外部变量来跟踪我们的"虚拟"大小(因为向量在内部不支持它).
注意:订购/分拣并不重要.此外,当我说"删除"时,没有任何内容被解除分配,只是说该元素被移动到"可用"范围之外.
现在,当需要在向量的可用部分中添加一个元素(来自已删除的元素)时,我们需要将其交换回某处.这就是我阻止的地方.因为,当我们交换它时,我们可以使用在此迭代中需要存在的元素交换它,并且需要交换相同的元素,依此类推......
这是一个如何工作的例子:
迭代1:| 1 2 3 4 | (4号)
迭代2:| 1 3 | 2 4(大小2,元素'2'和'4'仍在内存中,但没有考虑到矢量的大小)
迭代3:| 2 1 3 | 4(尺寸3,元素'4'仍在那里)
我可能会过度思考它,但如果有人知道如何正确地使用这个算法,那将会有所帮助.
谢谢你的帮助.
使用第一个不可用的元素交换它,然后增加您的虚拟大小.所以,举个例子,假设这是你的向量:
// usable unusable
{ 0, 1, 2, 3, 4, 5, 6, 7, 8 } // virtual size = 4
现在让我们假设您要将7从不可用部分移动到可用部分.你将它与4交换,因为那是第一个不可用的元素.然后你将虚拟大小增加1.所以现在你的向量看起来像这样:
// usable // unusable
{ 0, 1, 2, 3, 7, 5, 6, 4, 8 } // virtual size = 5
| 归档时间： |
|
| 查看次数： |
254 次 |
| 最近记录： |