c++ - Solution to 2-sum using unordered_map
<p>Okay so I am trying to solve the <code>2-SUM</code> problem in c++. Given a file of 1000000 numbers in arbitrary order, I need to determine if there exist pairs of integers whose sum is <code>t</code> where <code>t is each of [-10000, 10000]</code>. So this basically the <code>2-SUM</code> problem. </p>

<p>So, I coded up my solution in C++ wherein I used <code>unordered_map</code> as my hash table. I am ensuring low <code>load</code> on the hash table. But still this takes around <code>1hr 15mins</code> to finish(successful). Now, I am wondering if it should be that slow. Further reducing the load factor did not give any considerable performance boost.</p>

<p>I have no idea where I can optimise the code. I tried different load factors, doesn't help. This is question from a MOOC and people have been able to get this done in around 30 mins using the same hash table approach. Can anybody help me make this code faster. Or at least give a hint as to where the code might be slowing down.</p>

<p>Here is the code - </p>

<pre><code>#include &lt;iostream&gt;
#include &lt;unordered_map&gt;
#include &lt;fstream&gt;

int main(int argc, char *argv[]){
    if(argc != 2){
        std::cerr &lt;&lt; "Usage: ./2sum &lt;filename&gt;" &lt;&lt; std::endl;
        exit(1);
    }

    std::ifstream input(argv[1]);
    std::ofstream output("log.txt");
    std::unordered_map&lt;long, int&gt; data_map;
    data_map.max_load_factor(0.05);

    long tmp;
    while(input &gt;&gt; tmp){
        data_map[tmp] += 1;
    }

    std::cerr &lt;&lt; "input done!" &lt;&lt; std::endl;
    std::cerr &lt;&lt; "load factor " &lt;&lt; data_map.load_factor() &lt;&lt; std::endl;

    //debug print.
    for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
        output &lt;&lt; iter-&gt;first &lt;&lt; " " &lt;&lt; iter-&gt;second &lt;&lt; std::endl;
    }

    std::cerr &lt;&lt; "debug print done!" &lt;&lt; std::endl;

    //solve
    long ans = 0;

    for(long i = -10000; i &lt;= 10000; ++i){
        //try to find a pair whose sum = i.

        //debug print.
        if(i % 100 == 0)
            std::cerr &lt;&lt; i &lt;&lt; std::endl;

        for(auto iter = data_map.begin(); iter != data_map.end(); ++iter){
            long x = iter-&gt;first;
            long y = i - x;

            if(x == y)
                continue;

            auto search_y = data_map.find(y);
            if(search_y != data_map.end()){
                ++ans;
                break;
            }
        }
    }

    std::cout &lt;&lt; ans &lt;&lt; std::endl;

    return 0;
}
</code></pre>