unordered_map 随机元素
对于hash的结构来说
思路1：直接随机内部list 即可，但是数据量大的话 iter 要定位起来是个很麻烦的事情
思路2：先随机到一个可用bucket 然后再里面随机一个元素即可
这样存在一个问题，就是bucket会随着rehash resize等扩容而变化，但是size会变化很大 甚至远小于，这样的话随机的时候就很难随机到该元素，rehash 让多余太多的bucket 去掉，但是rehash的代价本身就比较大， 因此这个方法不够好，单纯的解决这个问题 可以考虑用map来随机化，但是查找性能又会下降。因此这种情况就要考虑自己实现一个适合这种情况的hash_map 来处理这个问题 而不是用std::unordered_map了
const std::string & GatewayLoginInfo::RandomMember()
{
if (this->uuid_to_session_id.size() <= 0)
{
return empty_string;
}
//way2 to random
int max_random_counter = this->uuid_to_session_id.bucket_count();
int iter = max_random_counter * 2;
int bucket;
while ((--iter) >= 0)
{
// find a not empty bucket
bucket = rand() % max_random_counter;
int size = this->uuid_to_session_id.bucket_size(bucket);
if (size > 0)
{
// this bucket is not empty
//大部分情况下 size 一般为0 1 因此比way1 好很多
auto this_bucket_iter = this->uuid_to_session_id.begin(bucket);
int counter = rand() % size;
while (--counter >= 0)
{
++this_bucket_iter;
}
return this_bucket_iter->first;
}
}
return empty_string;
//way1 to random
/*auto it = this->uuid_to_session_id.begin();
int counter = rand() % this->uuid_to_session_id.size();
while (counter--)
{
++it;
}
return it->first;*/
}
//泛型版本：
//从hash表中随机一个元素
template< typename HashMap>
auto unordered_map_random_member_if(HashMap & hash, const std::function<bool(const decltype(hash.begin())&)> &cb)->decltype(hash.begin())
{
if (hash.size() <= 0)
{
return hash.end();
}
int max_random_counter = hash.bucket_count();
int iter = max_random_counter * 2;
int bucket;
while ((--iter) >= 0)
{
// find a not empty bucket
bucket = rand() % max_random_counter;
int size = hash.bucket_size(bucket);
if (size > 0)
{
// this bucket is not empty
//大部分情况下 size 一般为0 1
auto this_bucket_iter = hash.begin(bucket);
int counter = rand() % size;
while (--counter >= 0)
{
++this_bucket_iter;
}
if (cb(this_bucket_iter))
{
return (this_bucket_iter);
}
}
}
return hash.end();
}
//从hash表中随机一个元素
template< typename HashMap>
auto unordered_map_random_member(HashMap & hash)->decltype(hash.begin())
{
has_find_one = false;
if (hash.size() <= 0)
{
return hash.end();
}
int max_random_counter = hash.bucket_count();
int iter = max_random_counter * 2;
int bucket;
while ((--iter) >= 0)
{
// find a not empty bucket
bucket = rand() % max_random_counter;
int size = hash.bucket_size(bucket);
if (size > 0)
{
// this bucket is not empty
//大部分情况下 size 一般为0 1
auto this_bucket_iter = hash.begin(bucket);
int counter = rand() % size;
while (--counter >= 0)
{
++this_bucket_iter;
}
return (this_bucket_iter);
}
}
return hash.end();
}
非hash结构的std::map的 随机元素 TODO