在2D中移动行/列的最有效方式std :: vector

我在C++中创建游戏应用程序。我已将地图表示为Tile对象的二维std::vector。在2D中移动行/列的最有效方式std :: vector

我需要在玩家移动时更新该地图。从服务器应用程序，我得到的行或列全球地图的新的部分，它应该被放置在本地客户端的地图，例如：

enter image description here

在图1中还有前球员动作的本地地图。最上面一行填满了对象1，中间是2，底部是0.现在，当玩家向上移动时，我得到新的第一排填满了对象3，其他所有对象都应该向下，并且前面的最后一行应该消失。

我可以通过在for循环中移动所需的对象来做到这一点，但我一直在考虑标准库中是否存在某种算法，或者是否有许多有效的方法来实现这种修改。

编辑：

对不起，我没有意识到会有这样操作行和列之间的差异，但确确实实存在。所以我也编辑了我的标题，因为我有时也需要为列进行编辑。

来源

2013-04-25 dziwna

所以你有一个'std :: vector >'？哪一个维度表示你的列，哪一个行？这很重要，因为如果第二维代表行，则很容易实现这个“向上”命令。您可以交换第1行和第2行，然后交换第1行和第3行，然后替换第1行。通过对向量的指针进行异或操作，可以有效地实现交换，这会导致每次交换产生3个处理器指令。 – Carsten 2013-04-25 09:21:59

您可能想要实现一个迭代器，并且根本不要移动向量的元素。只需为顶行的索引定义一个变量（在屏幕上），然后使用模运算符遍历所有行（因此只有000行应该用333覆盖，而顶行索引将是2而不是0）。该算法是effecient（只许多存储器写入需要的话），并且可以用于在任何方向上滚动：

移动向上：递减顶行索引（MOD行号），改变最后一行
向下运动：增加的最上面一行指数（MOD行号），改变第一行
左右移动：递减左山坳指数（MOD山坳号），改变过去的山坳
向右移动：增加左山坳索引（模数列号），更改第一列。

来源

2013-04-25 09:18:17 WebMonster

这听起来对我来说是一个非常好的解决方案，但我有一个，可能很愚蠢的问题 - 你写我应该实现一个迭代器，但实现它在哪里？ – dziwna 2013-04-25 09:31:50

@dziwna：只需将您的矩阵包装在一个也包含您的行/列索引的类中，并提供将这些索引纳入考虑范围的访问器（以及滚动方法）。 – syam 2013-04-25 09:36:25

@syam非常感谢你！ :) – dziwna 2013-04-25 09:41:45

您可以使用专门用于向量的std :: swap，并且效率很高，因为它只需要两个向量的多个指针交换。此外，你可以使用std :: rotate，但我不确定它是否使用交换技术。

不幸的是，只有当你有一个行向量，你需要移动行，或者你有一个向量列，你需要移动列时，这将工作。看来，要有效地执行这两个操作，你必须使用一些更复杂的数据结构。

来源

2013-04-25 09:21:08 lisyarus

有两个标准集装箱立即浮现在脑海中，当你需要快速的插入/删除在都四肢：std::deque和std::list。但是他们有他们特殊的要求和限制。

如果您遇到一个向量，您可以利用C++ 11移动语义，这将允许您高效地移动对象而不是复制它们，或者@WebMonster提到您可以使用某种类型的循环索引您的缓冲区完全消除了移动/复制的需要。

根据你的要求，假设他们是完整的，我可能会去@WebMonster的解决方案，这是最有效的。 编辑：现在你的需求已经发生了变化，而且你还需要在列上滚动，他的解决方案“循环索引”肯定是要走的路。

来源

2013-04-25 09:21:15 syam

我会给boost matrix一试。

来源

2013-04-25 09:24:07

一种可能的方式是使用：

std::std::swap_ranges()在您的2D动态已有的行std::vector

和

std::transform()修改，需要用新的值替换该行。

来源

2017-05-07 15:29:34 Ziezi

在2D中移动行/列的最有效方式std :: vector

回答

相关问题