How to get the top 100 names in a collection

Admin 1
Viewed 101

I am creating a program where I am summarizing from a data file. The data file has information about first names, etc. The information are the fields in the csv file. The fields in the data file are included as instance variables in the class. I created setter and getter methods to return the data for one person. I created vectors to hold the collection of variables.

I am having trouble understanding how create a list of the 100 most common first names of all people in the collection. The list must be in descending order of occurrence.

I was able to print all the common names and its frequencies. But, I am unable to print the 100 most common names. I sorted the vector and got the following errors:

  1. class std::pair<const std::string, int> has no member begin and end

Please help me resolve these issue. All processing of data in the vector must be done with iterators.I am not sure how to fix these issues since I am a beginner.

std::vector<std::string> commonNamesFirst; //vector

for (auto x : census) {
    commonNamesFirst.push_back(x.getFirstName()); //populate vector
}

std::map<std::string, int> frequencies; 

for (auto& x : census) { ++frequencies[x.getFirstName()]; }

for (auto& freq : frequencies) {
    sort(freq.begin(), freq.end(), greater <>()); //error, need to sort in descending order

    cout << freq.first << ": " << freq.second << endl; //print the 100 common names in descending order
}
c++
4 Answers
std::map<std::string, int> frequencies;

This is generally the right direction. You're using this to count how many times each word occurs.

for (auto& freq : frequencies) {

This iterates over each individual word and a count of how many times it occured. This no longer makes any logical sense. You are looking to find the 100 most common ones, the one with the highest count values. Iterating, and looking at each one individually, in the manner that's done here, does not make any sense.

sort(freq.begin(), freq.end(), greater <>());

freq, here, is a single word and how many times it occured. You are using freq to iterate over all of the frequencies. Therefore, this is just one of the words, and its frequency value. This is a single std::pair value. And it does not have anything called begin, or end. And that's what your compiler is telling you, directly.

Furthermore, you cannot sort a std::map in the first place. This is not a sortable container. The simplest option is to extract the contents if the now-complete map into something that's sortable. Like, for example, a vector:

std::vector<std::pair<std::string, int>> vfrequencies{
     frequencies.begin(),
     frequencies.end()
};

So, you've now copied the contents of a map into a vector. Not the most efficient approach, but a workable one.

And now, you can sort this vector. Rather easily.

However, as one last detail, you can't just drop std::greater<> and expect the right thing to happen.

You are looking to sort on the frequency count value only, which is the .second of these std::pairs. A plain std::greater is not going to do this for you. The std::greater overload for a std::pair is not going to do what you think it will do, here.

You will need to provide your own custom lambda for the third parameter of std::sort, that compares the second value of the std::pairs in that vector.

And then, the first 100 most common words will be the first 100 values in the vector. Mission accomplished.

user_39433120

You cannot (re-)sort std::map, you can copy frequencies in vector or std::multimap as intermediate:

std::map<std::string, int> frequencies;
for (auto& x : census) { ++frequencies[x.getFirstName()]; }

std::vector<std::pair<std::string, int>> freqs{frequencies.begin(), frequencies.end()};

std::partial_sort(freqs.begin(), freqs.begin() + 100, freqs.end(),
                  [](const auto& lhs, const auto& rhs){ return lhs.second > rhs.second; });
for (std::size_t i = 0; i != 100; ++i)
{
    std::cout << freqs[i].second << ":" << freqs[i] << std::endl;
}
user_26845390

Building on to @Michał Kaczorowski's answer, you are trying to sort the values in each pair instead of the pairs in the map. However, as Sam mentoined, you cannot sort an std::map (the internal implementation stores things sorted by the key value, or the name in this case). You'd have to get the values out of the map and sort them then, or use a priority queue and heapsort (faster constant factor), or a monotonic queue (linear time but harder to implement). Here is an example heapsort implementation:

vector<string> commonNamesFirst; //vector

for (auto x : census) {
    commonNamesFirst.push_back(x.getFirstName()); //populate vector
}

std::map<std::string, int> frequencies; 

for (auto& x : census) { ++frequencies[x.getFirstName()]; }

std::priority_queue<pair<int, std::string> > top_names;  // put the frequency before the name to take advantage of default pair compare

for (auto& freq : frequencies) top_names.push(std::make_pair(freq.second, freq.first));
for (int i=0; i<100; ++i)
{
    outputFile << top_names.top().second << ": " << top_names.top().first << endl; //print the 100 common names in descending order
    top_names.pop();
}
user_103728250

The error you get, says it all. You are trying to sort individual std::pair. I think the best way would be to transform your map into a std::vector of pairs and then sort that vector. Then just go through first 100 elements in a loop and print results.

user_47358030
Related