c++ - 如何随机打乱地图中的值？

Question

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

我可以将这些值推送到一个向量中，将其洗牌，然后复制回来。有没有更好的办法？

Answer 1

您可以按下 a 中的所有键vector，随机播放vector并使用它来交换 中的值map。

这是一个例子：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;
int myrandom (int i) { return std::rand()%i;}
int main ()
{
    srand(time(0));
    map<int,string> m;
    vector<int> v;
    for(int i=0; i<10; i++)
        m.insert(pair<int,string>(i,("v"+to_string(i))));

    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
        v.push_back(i.first);
    }
    random_shuffle(v.begin(), v.end(),myrandom);
    vector<int>::iterator it=v.begin();
    cout << endl;
    for(auto& i:m)
    {
        string ts=i.second;
        i.second=m[*it];
        m[*it]=ts;
        it++;
    }
    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
    }
    return 0;
}

Answer 2

您的提议的复杂性是O(N)，（副本和洗牌都具有线性复杂性）这似乎是最佳的（查看较少的元素会在您的洗牌中引入非随机性）。

如果你想反复打乱你的数据，你可以维护一个<Key, size_t>索引到 a 的类型映射（即众所周知的间接级别），std::vector<Value>然后重复打乱那个向量。这样可以节省所有复制以换取O(N)空间开销。如果类型本身很昂贵，那么您对进行洗牌的真实数据Value有额外的索引。vector<size_t>

为方便起见，您可以将mapand封装vector在一个公开shuffle()成员函数的类中。这样的包装器还需要公开底层映射的基本查找/插入/擦除功能。

编辑：正如@tmyklebu 在评论中指出的那样，维护（原始或智能）指向辅助数据的指针可能会导致迭代器失效（例如，在末尾插入新元素时会导致向量的容量被调整大小）。使用索引而不是指针解决了“最后插入”问题。但是在编写包装类时，您需要确保新键值对的插入永远不会导致辅助数据的“中间插入”，因为这也会使索引无效。一个更强大的库解决方案是使用Boost.MultiIndex，它专门设计用于允许对数据结构进行多种类型的视图。

Answer 3

如果您想就地洗牌，您可以random_shuffle为您的map. 该解决方案仍然需要将键放入向量中，如下使用transform：

typedef std::map<int, std::string> map_type;
map_type m;
m[10] = "hello";
m[20] = "world";
m[30] = "!";
std::vector<map_type::key_type> v(m.size());
std::transform(m.begin(), m.end(), v.begin(),
               [](const map_type::value_type &x){
                   return x.first;
               });
srand48(time(0));
auto n = m.size();
for (auto i = n-1; i > 0; --i) {
    map_type::size_type r = drand48() * (i+1);
    std::swap(m[v[i]], m[v[r]]);
}

我使用drand48()/srand48()了一个统一的伪随机数生成器，但您可以使用最适合您的任何东西。

或者，您可以 shuffle v，然后重新构建map，例如：

std::random_shuffle(v.begin(), v.end());
map_type m2 = m;
int i = 0;
for (auto &x : m) {
    x.second = m2[v[i++]];
}

但是，我想说明在 map 上实现 shuffle 并不过分繁重。

Answer 4

好吧，只使用地图我想到的是：为地图的每个单元格制作一个标志数组，随机生成两个整数 st 0<=i, j <地图大小；交换它们并将这些单元格标记为已交换。为所有人迭代。
编辑：该数组是按地图的大小分配的，并且是一个本地数组。

Answer 5

我对此表示怀疑...

但是...为什么不编写一个包含 2 个向量的快速类。一个排序std::vector的键和一个std::random_shuffledstd::vector值？std::lower_bound使用和使用查找键std::distance并std::advance获取值。简单的！

无需深思熟虑，这应该与std::map参考位置具有相似的复杂性，并且可能更好。

一些未经测试和未完成的代码可以帮助您入门。

template <class Key, class T>
class random_map
{
public:
    T& at(Key const& key);
    void shuffle();
private:
    std::vector<Key> d_keys; // Hold the keys of the *map*; MUST be sorted.
    std::vector<T> d_values;
}

template <class Key, class T>
T& random_map<Key, T>::at(Key const& key)
{
    auto lb = std::lower_bound(d_keys.begin(), d_keys.end(), key);
    if(key < *lb) {
        throw std::out_of_range();
    }
    auto delta = std::difference(d_keys.begin(), lb);
    auto it = std::advance(d_values.begin(), lb);
    return *it;
}

template <class Key, class T>
void random_map<Key, T>::shuffle()
{
    random_shuffle(d_keys.begin(), d_keys.end());
}

Answer 6

这是我使用std::reference_wrapperC++11 的解决方案。

首先，让我们创建一个 std::random_shuffle 版本，用于打乱引用。这是对版本 1的一个小修改：使用该方法获取引用的值。get

template< class RandomIt >
void shuffleRefs( RandomIt first, RandomIt last ) {
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i].get(), first[std::rand() % (i+1)].get());
    }
}

现在很容易：

template <class MapType>
void shuffleMap(MapType &map) {
    std::vector<std::reference_wrapper<typename MapType::mapped_type>> v;
    for (auto &el : map) v.push_back(std::ref(el.second));
    shuffleRefs(v.begin(), v.end());
}