如何在地图中随机洗牌？ [英] How to randomly shuffle values in a map?

问题描述

我有一个std :: map，key和value都是整数。现在我想随机洗牌地图，所以键随机指向一个不同的值。我尝试了random_shuffle，但它没有编译。请注意，我不是试图洗牌，这对地图是没有意义的。我试图把这些值随机化。

我可以将值推入一个向量，洗牌，然后复制。有更好的方法吗？

解决方案

您的提案的复杂性是 O（N）（这两个拷贝和shuffle都具有线性复杂性），这似乎是最理想的（看少元素会引入非随机性到你的随机播放中）。

如果要反复随机播放数据，可以维护类型为< Key，size_t> （即代表性的间接级别），它们索引到 std :: vector< Value> 中，然后再次重新洗牌。这将节省您所有的复制，以换取 O（N）空间开销。如果价值类型本身是昂贵的，则您可以在其中的实际数据中额外添加向量< size_t> 你做洗牌。

为方便起见，您可以封装地图和矢量在一个公开一个 shuffle（）成员函数的类中。这样的包装器也需要公开基础查找/插入/删除功能的底层地图。

编辑：正如@ tmyklebu在注释中，维护（原始或智能）指向次要数据的指针可能会受到迭代器无效的限制（例如，在导致向量的容量调整大小的末尾插入新元素时）。使用索引而不是指针可以解决插入结束的问题。但是当编写包装类时，您需要确保插入新的键值对不会对辅助数据造成插入到中间，因为这也会使索引无效。更强大的库解决方案是使用 Boost .MultiIndex ，它专门用于允许对数据结构进行多种类型的视图。

I have a std::map with both key and value as integers. Now I want to randomly shuffle the map, so keys point to a different value at random. I tried random_shuffle but it doesn't compile. Note that I am not trying to shuffle the keys, which makes no sense for a map. I'm trying to randomise the values.

I could push the values into a vector, shuffle that and then copy back. Is there a better way?

解决方案

The complexity of your proposal is O(N), (both the copies and the shuffle have linear complexity) which seems optimal (looking at less elements would introduce non-randomness into your shuffle).

If you want to repeatedly shuffle your data, you could maintain a map of type <Key, size_t> (i.e. the proverbial level of indirection) that indexes into a std::vector<Value> and then just shuffle that vector repeatedly. That saves you all the copying in exchange for O(N) space overhead. If the Value type itself is expensive, you have an extra vector<size_t> of indices into the real data on which you do the shuffling.

For convenience sake, you could encapsulate the map and vector inside one class that exposes a shuffle() member function. Such a wrapper would also need to expose the basic lookup / insertion / erase functionality of the underyling map.

EDIT: As pointed out by @tmyklebu in the comments, maintaining (raw or smart) pointers to secondary data can be subject to iterator invalidation (e.g. when inserting new elements at the end that causes the vector's capacity to be resized). Using indices instead of pointers solves the "insertion at the end" problem. But when writing the wrapper class you need to make sure that insertions of new key-value pairs never cause "insertions in the middle" for your secondary data because that would also invalidate the indices. A more robust library solution would be to use Boost.MultiIndex, which is specifically designed to allow multiple types of view over a data structure.

这篇关于如何在地图中随机洗牌？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！