Finding most common element in a list (C++ STL)?

问题:

I have a program where I have to find the most common element in a list of integers. I do this with the program below, but the problem is, I suspect that the erase function messes up with the iterator incrementation in the countRepetition() function. My question is how can I fix the problem or if this is not the issue what is it?

Thanks in advance.

回答1:

You have a couple issues. First, as you suspected, was the incorrect use of erase. When you erase an iterator it invalidates the iterator. Any use of the iterator afterwards is undefined behavior. Since erase returns the next valid iterator what you can do is restructure the loop like

for (START = l.begin(); START != l.end();) { // do not increment here
    if (*START) {
        counter++;
        START = l.erase(START); // erase and get next
    }
    else
    {
        ++START; // go to next
    }
}

So now at least you loop through the list. Unfortunately you will still have an invalid iterator in main. You pass START from main to countRepetition and when that iterator is erased from the list you then have an invalid iterator. What you need to do is get a new begin iterator from the list each iteration since you are always erasing the first element. That would make your for loop look like

for (START = l.begin(); START != l.end(); START = l.begin()) {
    m.push_back(countRepetition(START));
}

---

Another issue is you just check if the character is not 0. If you are counting repetitions you need to make sure you are checking that the iterator is the same character. I'll leave that for you to implement.

---

I would also like to point out there is an easier way to do all of this. A std::map lets you build a histogram very easily. Combine that with std::max_element and you could write your entire program as

int main()
{
    std::map<char, int> histogram;
    while ('0' != (number = getchar()))
        ++histogram[number]; // add to map, increment count of occurances

    auto most_frequent = *std::max_element(histogram.begin(), 
                                           histogram.end(), 
                                           [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; }).first;
    std::cout << most_frequent;    
    return 0;
}

回答2:

Your problem is that you use global variables everywhere. The global START is changed in two loops, so you only access the first loop once, then it is changed again in the second function and you don't execute the first loop a second time.

Why do you use the global variables? You should not use them but use local variables.

回答3:

This is probably what you are looking for:

#include <iostream>
#include <list>
#include <vector>
#include <map>

using namespace std;

list <char> l;
map<char, int> ans;
int main()
{
    char c;
   do{
       c = getchar();
       l.push_back(c);
   }while(c != '0');
   for(auto chr: l){
       ans[chr]++;
   }
   char ch;
   int mx = 0;
   for(auto k: ans){
       if(k.second > mx)
       {
           ch = k.first;
           mx = k.second;
       }
   }
   cout<<ch<<" : "<<mx;
}