truy xuất phần tử khóa ngẫu nhiên cho std :: map in C++

Question

cách lấy khóa ngẫu nhiên cho std :: map in C++? sử dụng iterator? Tôi không muốn cấu trúc dữ liệu bổ sung được duy trì

Answer 1

std::map trình lặp là hai chiều, có nghĩa là chọn một khóa ngẫu nhiên sẽ là O(n). Nếu không sử dụng cấu trúc dữ liệu khác, về cơ bản, lựa chọn duy nhất của bạn là sử dụng std::advance với mức tăng ngẫu nhiên từ begin(). Ví dụ:

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

(Hoặc trao đổi ra rand() với (ví dụ) std::mt19939 nếu bạn có quyền truy cập vào <random>).

Answer 2

Điều đó tùy thuộc vào mục đích của bạn. std::map là một vùng chứa được sắp xếp, nhưng không hỗ trợ truy cập ngẫu nhiên theo số phần tử. Do đó và kiến ​​thức về bộ khóa, bạn có thể chọn ngẫu nhiên một điểm để đào vào bản đồ bằng cách sử dụng lower_bound hoặc upper_bound để tìm một phần tử gần đó. Điều này có xu hướng tiếp tục chọn các yếu tố dựa trên khoảng cách giữa chúng và các yếu tố khác trong bản đồ, có nghĩa là kết quả ban đầu có thể được coi là ngẫu nhiên một cách hiệu quả nếu các yếu tố/khoảng trống đó là ngẫu nhiên một cách hiệu quả. chia đêu.

Ví dụ: giả sử các phím của bạn là chữ hoa và các phím 'C', 'O', 'Q' và 'S' nằm trong bản đồ. Nếu bạn tạo một ký tự ngẫu nhiên từ AZ, bạn sẽ có nhiều khả năng kết thúc trên C, O hoặc S hơn Q, vì chỉ PQR gần Q và sử dụng giới hạn trên hoặc dưới, bạn sẽ chọn hai trong số đó, cơ hội 2/26 mặc dù chỉ có 4 yếu tố. Tuy nhiên, nếu có một số ngẫu nhiên để lựa chọn C, O, Q và S để bắt đầu, bạn có thể lập luận rằng khoảng trống và lựa chọn là ngẫu nhiên.

Bạn có thể cải thiện điều đó một chút bằng cách đâm vào thùng chứa như thế này, sau đó thực hiện một số lượng nhỏ ngẫu nhiên các gia số/số lần lặp lại, nhưng nó vẫn không thực sự ngẫu nhiên.

Kết quả thực sự ngẫu nhiên yêu cầu phải tiến hành từng bước một thông qua danh sách hoặc vùng chứa chỉ mục phụ mà bạn muốn tránh.