c++ - STL 排序对字符串 vector 与字符串指针 vector 的性能比较

Question

我尝试比较 STL 排序对字符串 vector 和字符串指针 vector 的性能。

我预计指针版本的表现会更好，但 500 万个随机生成的字符串的实际结果是

字符串 vector :12.06 秒
指向字符串的指针 vector :16.75 秒

如何解释这种行为？我预计交换指向字符串的指针应该比交换字符串对象更快。

500万个字符串是通过随机整数转换生成的。
使用 (gcc 4.9.3) 编译:g++ -std=c++11 -Wall
CPU:至强X5650

// sort vector of strings
 int main(int argc, char *argv[])
    {
      const int numElements=5000000;
      srand(time(NULL));
      vector<string> vec(numElements);

      for (int i = 0; i < numElements; i++)
            vec[i] = std::to_string(rand() % numElements);

      unsigned before = clock();

      sort(vec.begin(), vec.end());

      cout<< "Time to sort: " << clock() - before << endl;

       for (int i = 0; i < numElements; i++)
         cout << vec[i] << endl;

      return 0;
    }



// sort vector of pointers to strings
    bool comparePtrToString (string *s1, string *s2)
    {
      return (*s1 < *s2);
    }

    int main(int argc, char *argv[])
    {
      const int numElements=5000000;
      srand(time(NULL));
      vector<string *> vec(numElements);

      for (int i = 0; i < numElements; i++)
            vec[i] = new string( to_string(rand() % numElements));

      unsigned before = clock();

      sort(vec.begin(), vec.end(), comparePtrToString);

      cout<< "Time to sort: " << clock() - before << endl;

       for (int i = 0; i < numElements; i++)
         cout << *vec[i] << endl;

      return 0;
    }

Answer 1

这是因为 sort 对 strings 执行的所有操作都是移动和交换。 std::string 的移动和交换都是常量时间操作，这意味着它们只涉及更改一些指针。

因此，对于这两种类型，数据移动具有相同的性能开销。但是，如果是指向字符串的指针，您需要付出一些额外的代价才能在每次比较时取消对指针的引用，这会导致速度明显变慢。