在C++中檢索std :: map的隨機密鑰元素

Question

如何在C++中獲取std :: map的隨機密鑰？使用迭代器？ 我不想要額外的數據結構來維護

Answer 1

std::map迭代器是雙向的，這意味着選擇一個隨機密鑰將是O(n)。在不使用其他數據結構的情況下，基本上唯一的選擇是使用std::advance，其隨機增量爲begin()。例如：

std::map<K, V> m; 
auto it = m.begin(); 
std::advance(it, rand() % m.size()); 
K random_key = it->first; 

（或使用（例如）std::mt19939換出rand()如果你有<random>訪問）。

Answer 2

這取決於你的目的是隨機的。 std::map是一個排序的容器，但不支持按元素編號隨機訪問。鑑於這一點和關鍵集合的知識，您可以使用lower_bound或upper_bound來隨機選擇要在其中查找地圖的點，以便在該地點附近找到要素。這有一種趨勢，即根據它們與地圖中其他元素之間的差距來選擇元素，這意味着如果元素/間隙本身是有效的隨機元素，重複選擇的隨機元素將不會是初始結果平均分配。例如，假設您的密鑰爲大寫字母，並且鍵「C」，「O」，「Q」和「S」在地圖中。如果你從AZ生成一個隨機字母，你很可能最終選擇C，O或S而不是Q，因爲只有PQR接近Q並且使用上限或下限，你最終會選擇其中的兩個，儘管只有4個元素，但仍有2/26的機會。儘管如此，如果選擇C，O，Q和S時有一些隨機性，那麼你可能會認爲差距和選擇是隨機的。

你可以通過像這樣刺入容器，然後做一個隨機數的迭代器增量/減量來改善，但它仍然不會是真正的隨機數。

一個真正隨機的結果需要推進一個一個遍歷遍歷列表或要避免的二級索引容器。