Counting the occurrences of bank account numbers for SPOJ challenge I am solving a problem on SPOJ and am currently unsatisfied with my submission time, given that my fastest time is 0.28s (which ranks me 123/5037) and the leading submission is 0.04s.

The problem is pretty simple: Given a list of bank account numbers, print the bank account number along with the frequency at which it is repeated.


  Input
  
  t [the number of tests &lt;= 5]
  n [the number of accounts&lt;= 100 000] 
  
  [list of accounts]
  [empty line]
  [next test cases]
  
  Output
  
  [sorted list of accounts with the number of repeated accounts]
  [empty line]
  [other results]


Example:

Input:
2
6
03 10103538 2222 1233 6160 0142 
03 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 

5
30 10103538 2222 1233 6160 0144 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0145 
30 10103538 2222 1233 6160 0146 
30 10103538 2222 1233 6160 0143 

Output:
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2

30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1


In order to solve this, I am using a map where the key is the bank account and the value is the frequency of repetition. However, I am first loading the bank accounts into a vector, and I am pretty sure this is one area where I am losing efficiency. I have tried to avoid using the vector, but my efficiency is greatly reduced.

What are some things that I can do to either improve my algorithm, or perhaps increase my I/O speed?

#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int t;
  std::cin &gt;&gt; t;
  while (t--) {
    int n, i;
    std::cin &gt;&gt; n;
    std::cin.ignore();
    std::vector&lt;std::string&gt; accounts(n);
    for (i = 0; i &lt; n; ++i) {
      std::getline(std::cin, accounts[i]);
    }
    std::cout &lt;&lt; "\n";
    std::map&lt;std::string, int&gt; count;
    for (i = 0; i &lt; accounts.size(); ++i) {
      auto map_it(count.find(accounts[i]));
      if (map_it != count.end()) {
        map_it-&gt;second++;
      } else {
        count[accounts[i]] = 1;
      }
    }
    for (auto it = count.begin(); it != count.end(); ++it) {
      std::cout &lt;&lt; it-&gt;first &lt;&lt; it-&gt;second &lt;&lt; "\n";
    }
    if (t != 0) {
      std::string blank;
      std::getline(std::cin, blank);
    }
  }
  return 0;
}
One area of inefficiency is here:

for (i = 0; i &lt; n; ++i) {
  std::getline(std::cin, accounts[i]);
}
std::cout &lt;&lt; "\n";
std::map&lt;std::string, int&gt; count;
for (i = 0; i &lt; accounts.size(); ++i) {
  auto map_it(count.find(accounts[i]));
  if (map_it != count.end()) {
    map_it-&gt;second++;
  } else {
    count[accounts[i]] = 1;
  }
}


You're reading each account number, storing them then going back through the data to get the counts.  The map class allows for a key that doesn't exist to create an entry on the fly.  Using this will eliminate the second loop:

std::string temp = "";
std::map&lt;std::string, int&gt; count;
for (i = 0; i &lt; n; ++i) {
  std::getline(std::cin, temp);
  count[temp]++; 
}
std::cout &lt;&lt; "\n";