c++ - 如何在 C++ 中打乱指针列表？

Question

如何在 C++ 中打乱 stl 指针列表？我在类 Player 上有 stl 指针向量，我像这样随机播放

std::random_shuffle(players.begin(), players.end());

是否已经有不需要随机访问的随机列表算法，或者我需要将列表转换为向量 => 随机播放 => 回到列表？有更优雅的解决方案吗？

Answer 1

随机洗牌算法将特定元素与随机选择的元素交换。重复遍历列表来获取元素是非常低效的（即这将是一个O(n^2)操作）。

这就是为什么最好（更快）将您的列表复制到一个数组一次，进行随机洗牌并可能恢复列表。那将是3*n遍历，仍然是O(n).

Answer 2

std::random_shuffle需要一个随机迭代器。Vector 支持这一点，而 List 则不支持。怎么样std::deque，它就像一种向量和一种列表。

Answer 3

你的问题很有趣。所以，我试着写点东西，最后想出了这个。

    //---------- sample List initialization ------
    list<string> lst;
    lst.push_back("A");
    lst.push_back("B");
         ....
    lst.push_back("Y");
    lst.push_back("Z");

    #define LIST_SIZE 26
    //--------------------------------------------

    //------------- Shuffle Algorithm ------------
    unordered_multimap<int,string> mymap;
    int HashKeys[LIST_SIZE];
    srand((int)time(NULL) * (int)clock());

    for(int i = 0; i<LIST_SIZE; i++) // loop 'n' times
    {
        HashKeys[i] = rand(); // O(c) operation
    }

    for(int i = 0;lst.size() > 0; i++) // loop 'n' times
    {
         // O(n) operation ( varies from O(c) to O(n) according to the situations )
        mymap.insert(std::make_pair<int,string>(HashKeys[rand() % LIST_SIZE],lst.front()));
        lst.pop_front(); // O(c) operation
    }

    unordered_multimap<int,string>::iterator it;
    for(int i = 0; i < LIST_SIZE ;i++) // loop 'n' times
    {
        while(mymap.count(HashKeys[i]) > 0) // unpredictable
        {
            it = mymap.find(HashKeys[i]); // O(c) for single O(n) for multi
                    // ...USAGE...
            cout << it->second << endl;
                    lst.push_back(it->second);
                    //............
            mymap.erase(it); // O(c) operation
        }
    }
    //-------------------------------------------------

如果哈希图中的同一键有多个值，则时间复杂度为 O(n^2)。否则时间复杂度为 O(n)。所以一切都取决于功能(rand() % LIST_SIZE)