字符串向量与字符串指针向量的STL排序性能比较

Question

我试图比较字符串向量和字符串指针向量的STL排序的性能.

我预计指针版本会跑赢大盘,但500万随机生成的字符串的实际结果是

字符串向量:12.06秒
指向字符串的向量:16.75秒

什么解释了这种行为？我期望交换指向字符串的指针应该比交换字符串对象更快.

通过转换随机整数生成500万个字符串.
编译(gcc 4.9.3):g++ -std=c++11 -Wall
CPU:Xeon 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恒定时间操作,这意味着它们只涉及更改一些指针.

因此,对于这两种类型的数据移动具有相同的性能开销.但是,在指向字符串的情况下,您需要支付一些额外的费用来取消引用每个比较的指针,这会导致它明显变慢.