std::set怎么比std::map慢?

我试图解决 this problem from acm.timus.ru 它基本上希望我输出给定字符串的不同子字符串的数量(最大长度5000)。

我即将提出的解决方案效率极低,而且在受到限制的情况下,注定会出现“超过时限”的判决。然而,这两种解决方案的唯一不同之处(至少在我看来/理解的范围内)是 std::map<long long, bool> ,而其他用途 std::set <long long> (请参阅最后一个for循环的开头。其余部分相同,您可以通过任何diff工具进行检查)。映射解决方案会导致“测试3超过时间限制”,而设置解决方案会造成“测试2超出时间限制”。这意味着测试2使得映射解决方案在其上的工作速度比设置解决方案更快。如果我选择Microsoft Visual Studio 2010编译器,就会出现这种情况。如果我选择GCC,那么两种解决方案都会在测试3中产生TLE。

我不是在问如何有效地解决这个问题。我在问什么 是如何解释使用 std::map 显然比使用更有效 std::set 。我只是看不到这种现象的机制,希望有人能有任何见解。

代码1(使用地图,TLE 3):

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main ()
{
   string s;
   cin >> s;
   vector <long long> p;
   p.push_back(1);
   for (int i = 1; i < s.size(); i++)
      p.push_back(31 * p[i - 1]);
   vector <long long> hash_temp;
   hash_temp.push_back((s[0] - 'a' + 1) * p[0]);
   for (int i = 1; i < s.size(); i++)
      hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]);   
   int n = s.size();   
   int answer = 0;
   for (int i = 1; i <= n; i++)
   {
      map <long long, bool> hash_ans;
      for (int j = 0; j < n - i + 1; j++)
      {
         if (j == 0)
            hash_ans[hash_temp[j + i - 1] * p[n - j - 1]] = true;
         else
            hash_ans[(hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]] = true;
      }
      answer += hash_ans.size();
   }
   cout << answer;
}

代码2(使用集合,TLE 2):

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

int main ()
{
   string s;
   cin >> s;
   vector <long long> p;
   p.push_back(1);
   for (int i = 1; i < s.size(); i++)
      p.push_back(31 * p[i - 1]);
   vector <long long> hash_temp;
   hash_temp.push_back((s[0] - 'a' + 1) * p[0]);
   for (int i = 1; i < s.size(); i++)
      hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]);   
   int n = s.size();   
   int answer = 0;
   for (int i = 1; i <= n; i++)
   {
      set <long long> hash_ans;
      for (int j = 0; j < n - i + 1; j++)
      {
         if (j == 0)
            hash_ans.insert(hash_temp[j + i - 1] * p[n - j - 1]);
         else
            hash_ans.insert((hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]);
      }
      answer += hash_ans.size();
   }
   cout << answer;
}