Kattis Challenge - Recount - count who has the most votes in a list of names I am attempting to solve the Kattis problem Recount. 


  The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge!
  
  In their desperation, the election officials turn to you and ask you to write a program to count the vote!
  
  Input
  
  The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least 2 votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to 100,000 valid votes.
  
  Output
  
  If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: “Runoff!” (don’t forget to include the exclamation mark!)
  
  Sample Input 1

Penny Franklin  
Marti Graham  
Connie Froggatt  
Joseph Ivers  
Connie Froggatt  
Penny Franklin  
Connie Froggatt  
Bruce Stanger  
Connie Froggatt  
Barbara Skinner  
Barbara Skinner  
***

  
  Sample Output 1

Connie Froggatt

  
  Sample Input 2

Penny Franklin  
Connie Froggatt  
Barbara Skinner  
Connie Froggatt  
Jose Antonio Gomez-Iglesias  
Connie Froggatt  
Bruce Stanger  
Barbara Skinner  
Barbara Skinner
***

  
  Sample Output 2

Runoff!



#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
#include &lt;algorithm&gt;
#include &lt;functional&gt;
using namespace std;

struct voter
{
    string name;
    int numvotes;
    bool operator==(const string   &amp;) const;
    bool operator&lt;(const voter   &amp;) const;
    bool operator&gt;(const voter   &amp;) const;

};
bool voter::operator==(const string &amp;f) const
{
    return name == f;
}

bool voter::operator&lt;(const voter &amp;f) const
{
    return (numvotes &lt; f.numvotes);
}
bool voter::operator&gt;(const voter &amp;f) const
{
    return (numvotes &gt; f.numvotes);
}

bool myfunction(voter i, voter j) { return (i&lt;j); }

int main() {
    vector&lt;voter&gt; voters;
    string name;

    while (getline(cin, name))
    {
        if (name == "***")
        {
            break;
        }
        _Vector_iterator&lt;_Vector_val&lt;_Simple_types&lt;voter&gt;&gt;&gt; it = find(voters.begin(), voters.end(), name);
        if (it != voters.end()) {
            it-&gt;numvotes += 1;
        }
        else
        {
            voter a;
            a.name = name;
            a.numvotes = 1;
            voters.push_back(a);
        }
    }
    sort(voters.begin(), voters.end(), greater&lt;voter&gt;());

    if (voters[0].numvotes == voters[1].numvotes)
    {
        cout &lt;&lt; "Runoff!" &lt;&lt; endl;
    }
    else
    {
        _Vector_iterator&lt;_Vector_val&lt;_Simple_types&lt;voter&gt;&gt;&gt;  tt = max_element(voters.begin(), voters.end());
        cout &lt;&lt; tt-&gt;name &lt;&lt; endl;
    }
    return 0;
}


My program will pass all of the tests except the very last one where it "times out". Any input I can get on this will be greatly appreciated. This code does compile and run in VS and here: http://cpp.sh/8l3b 

To get this to run on cpp.sh I did have to change the _Vector_iterator&lt;_Vector_val&lt;_Simple_types&lt;voter&gt;&gt;&gt; on lines 43 and 63 to auto. I don't quite understand why, so I would also be very appreciative if you could explain what I should use as a type to be portable.
There are 2 important performance issues here:


find(...) in a vector performs a linear search, \$O(n)\$. You would do better by using a hash map instead, that would allow constant-time search, \$O(1)\$.
Sorting the candidates by vote count is unnecessary to find the ones with the maximum count. Sorting is an \$O(n \log n)\$ operation. You can find the maximum with a linear search, \$O(n)\$, and in a second linear pass you could verify if a run-off is needed. (You could as well make this part of step 1 and do it in a single pass, but that wouldn't change the order of complexity of the algorithm.)


Lastly, a minor thing, but the implementation will fail if there are less than two candidates :-)