Random subset of elements from multimap grouped by keys

I have a list consisting of car brands ID's and associated car models, e.g.:

1 Corolla

1 Yaris

1 Matrix

2 Cherokee

2 Liberty

3 CR-V

3 CR-Z

3 Element

3 Civic

3 Pilot

where 1=Toyota, 2=Jeep, and 3=Honda. Note that the cardinality of car models per car brand differs.

I would like to retrieve random car models per car-brand. The number of cars to be retrieved per car brand depends upon the total number of associated models and an input float parameter: 'nPercentage'. (The 'nPercentage' parameter is the same for all different car-brands). For example, if nPercentage=0.5, a possible random output would be:

1 Corolla

1 Matrix

2 Liberty

3 CR-Z

3 Civic

3 Pilot

I'm currently working with a multimap class, since the keys can be duplicated. So far, I'm able to find non-duplicate开发者_开发问答d keys and count the number of associated elements. Could anyone shed some light on how to retrieve the random car models per car-brand? Below, the code that I have so far.

//The variable 'm_mapDatasetMapping' is of type: multimap<int, string>

multimap< int, string >::size_type countPerKey;
const int *pLastKey = NULL;
multimap<int,string>::const_iterator it=m_mapDatasetMapping.begin();

// looking for non-duplicated keys.
for( ; it!=m_mapDatasetMapping.end(); it++){

    if( (pLastKey!=NULL) && (*pLastKey==it->first) ){
        continue;
    }
    pLastKey = &(it->first);

    // count the number of values associated to the given key.
    countPerKey = m_mapDatasetMapping.count(*pLastKey);

    /* Select 'x' random elements associated with the key '*pLastKey'. 
       The number of random elements to be extracted
       is a percentage of the total number of values per key, i.e.: 
       x = nPercentage * countPerKey 
    */
    ...
}

---

Perhaps the simplest approach to follow would be to copy all values for the given key out into a new container, say, a vector, random_shuffle it, and resize() it to reduce its size to x:

int x = nPercentage * countPerKey;
auto range = m_mapDatasetMapping.equal_range(*pLastKey);
std::vector<std::string> values;
for(auto i = range.first; i != range.second; ++i)
    values.push_back(i->second);
std::random_shuffle(values.begin(), values.end());
values.resize(x);