5

キーと値の両方を整数として持つ std::map があります。ここで、マップをランダムにシャッフルしたいので、キーはランダムに異なる値を指します。random_shuffle を試しましたが、コンパイルできません。キーをシャッフルしようとしているわけではないことに注意してください。これは、マップには意味がありません。値をランダム化しようとしています。

値をベクトルにプッシュし、それをシャッフルしてからコピーすることができます。より良い方法はありますか？

4

6 に答える 6

4

のすべてのキーを押して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;
}
于 2013-04-17T20:22:27.670 に答える
2

あなたの提案の複雑さは ですO(N)(コピーとシャッフルの両方が線形の複雑さを持っています)。

データを繰り返しシャッフルしたい場合は、にインデックスを付け、そのベクトルを繰り返しシャッフルするタイプ<Key, size_t>(つまり、ことわざの間接レベル) のマップを維持できます。これにより、スペースのオーバーヘッドstd::vector<Value>と引き換えに、すべてのコピーを節約できます。型自体が高価な場合は、シャッフルを行う実際のデータに追加O(N)のインデックスがあります。Valuevector<size_t>

便宜上、メンバー関数を公開する 1 つのクラス内にmapandをカプセル化できます。このようなラッパーは、基になるマップの基本的な検索/挿入/消去機能も公開する必要があります。vectorshuffle()

EDIT : コメントで @tmyklebu が指摘したように、セカンダリ データへの (生またはスマートな) ポインターを維持すると、反復子の無効化の対象となる可能性があります(たとえば、ベクターの容量がサイズ変更される原因となる新しい要素を最後に挿入する場合)。ポインターの代わりにインデックスを使用すると、「最後に挿入」の問題が解決されます。ただし、ラッパー クラスを作成するときは、新しいキーと値のペアの挿入によってセカンダリ データの「途中での挿入」が発生しないようにする必要があります。これは、インデックスも無効になるためです。より堅牢なライブラリ ソリューションは、 Boost.MultiIndexを使用することです。これは、データ構造に対して複数のタイプのビューを許可するように特別に設計されています。

于 2013-04-17T19:55:41.467 に答える
0

さて、マップのみを使用して、私はそれを考えます：マップの各セルに対してフラグ配列を作成し、ランダムに2つの整数st 0 <= i、j <マップのサイズを生成します。それらを交換し、これらのセルを交換済みとしてマークします。すべてを繰り返します。
編集: 配列はマップのサイズによって割り当てられ、ローカル配列です。

于 2013-04-17T19:53:06.973 に答える
0

疑わしい...

しかし... 2 つのベクトルを含む簡単なクラスを作成してみませんか? 並べ替えstd::vectorられたキーと値のstd::random_shuffledです。およびを使用std::vectorしてキーを検索し、値を取得します。簡単！std::lower_boundstd::distancestd::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());
}
于 2013-04-17T19:53:30.270 に答える