当前位置:  编程语言>c/c++

STL vector+sort排序和multiset/multimap排序比较

 
分享到:
    发布时间:2013-7-26  


    本文导语:  在C++的STL库中,要实现排序可以通过将所有元素保存到vector中,然后通过sort算法来排序,也可以通过multimap实现在插入元素的时候进行排序。在通过vector+sort进行排序时,所有元素需要先存入vector容器中,sort在排序时...

    在c++stl库中,要实现排序可以通过将所有元素保存到vector中,然后通过sort算法来排序,也可以通过multimap实现在插入元素的时候进行排序。在通过vector+sort进行排序时,所有元素需要先存入vector容器中,sort在排序时又需要将元素全部取出来再进行排序。multimap底层实现为红黑树,因此元素在插入的过程中就实现了排序。那么到底哪一种排序速度更快呢?

   下面有一个测试程序:

   

#include <vector>
#include <set>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/time.h>
using namespace std;
double time() {
  struct timeval tv;
  if (gettimeofday(&tv, NULL) != 0) return 0.0;
  return tv.tv_sec + tv.tv_usec / 1000000.0;
}
struct Score {
  string name;
  double score;
  bool operator <(const Score& right) const {
    return score < right.score;
  }
};
int main(int argc, char** argv) {
  vector<Score> src;
  for (int i = 0; i < 10000000; i++) {
    int num = rand();
    char buf[32];
    sprintf(buf, "%d", num);
    Score score = { buf, num };
    src.push_back(score);
  }
  {
    double stime = time();
    vector<Score> res;
    for (vector<Score>::const_iterator it = src.begin();
         it != src.end(); ++it) {
      res.push_back(*it);
    }
    sort(res.begin(), res.end());
    double etime = time();
    printf("vector: %fn", etime - stime);
  }
  {
    double stime = time();
    multiset<Score> res;
    for (vector<Score>::const_iterator it = src.begin();
         it != src.end(); ++it) {
      res.insert(*it);
    }
    double etime = time();
    printf("multiset: %fn", etime - stime);
  }
  return 0;
}

程序运行结果为:

         time
vector   4.776060
multiset 10.761023

在这个测试中,vector+sort排序比multiset(multimap实现基于multiset)快多了。快速排序是目前已知的所有排序算法中最快的排序算法,因此它比基于堆排序的multiset快。

 在这个测试结果出来之前,大多数人都会毫无疑问地认为multiset排序要更快。这也是有原因的,快速排序速度虽然快,但是在实际的运行过程中,它需要大量地拷贝元素,其拷贝操作的时间复杂度为o(NlogN),而基于红黑树的multiset在排序的过程中则避免了元素的拷贝。如果元素的内存占用空间比较大,那么multiset排序的速度将比vector+sort快。为了测试这个结果,将上面测试程序中的结构体改为:

struct Score {
  string name1;
  string name2;
  string name3;
  string name4;
  double score;
  bool operator <(const Score& right) const {
    return score < right.score;
  }
};

然后重新编译运行测试程序,测试结果为:

         time
vector   12.955739
multiset 11.368364

这个测试结果和我们的预期一致。

  总之,我们在使用STL的排序算法时,需要根据不同的元素构造来进行合适的选择,如果都是比较简单的元素,那么适合选择vector+sort来进行排序,对于由字符串构成的占用了比较大的空间的复杂元素,应该使用multiset。如果排序的元素的总个数比较少,那么选择任意一种都可以。


  • 本站(WWW.169IT.COM)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.169IT.COM)站内文章除注明原创外,均为转载,整理或搜集自网络.欢迎任何形式的转载,转载请注明出处.
    转载请注明:文章转载自:[169IT-IT技术资讯]
    本文标题:STL vector+sort排序和multiset/multimap排序比较
相关文章推荐:


站内导航:


特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

©2012-2017,169IT.COM,E-mail:www_169it_com#163.com(请将#改为@)

浙ICP备11055608号