Sorting speed of stl vectors and lists

Posted   on Friday, February 12 - 2010 (289 words)

This snippet is an addition to my previous article about sorting STL containers. I’ve tested the sorting speed of std::vector vs. std::list on my MacBook. As we can see by the results below, vectors are much faster than lists when it comes to sorting (almost 8 times faster on my machine).

Thx to Dean H. for commenting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>   // Needed for sort() method
#include <vector>      // STL vector class
#include <list>        // STL list class
#include <iostream>    // Needed for cout,endl
#include <sys/time.h>  // Needed for rand,timeval
using namespace std;   // Save us some typing

bool comp(const int& num1, const int& num2)
{
   return num1 > num2;
}


// Prints the difference between to time values to std::out
void printDiff(const timeval& end, const timeval& start)
{
    timeval diff;
    diff.tv_sec = end.tv_sec  - start.tv_sec;
    diff.tv_usec= end.tv_usec - start.tv_usec;
    if (diff.tv_usec < 0) {
        diff.tv_sec--;
        diff.tv_usec += 1000000;
    }
    cout << "Elapsed time: " << diff.tv_sec << "seconds, "
         << diff.tv_usec << " microseconds." << endl;
}

int main()
{
    vector<int> v;              // Vector containing integers
    vector<int>::iterator vIt;  // Iterator navigating through vector

    list<int> l;                // List containing integers
    list<int>::iterator lIt;    // Iterator navigating through list


    // Insert a 100 million integer values into both containers
    srand( time(NULL) ); // Initialize random number generator
    generate_n (back_inserter(v), 100000000, rand);
    generate_n (back_inserter(l), 100000000, rand);

    // Measure sorting time
    timeval start, end;

    // Sort vector
    gettimeofday(&start, 0);
    sort(v.begin(), v.end(), comp);
    gettimeofday(&end, 0);
    cout << "VECTOR: ";
    printDiff(end, start);

    // Sort list
    gettimeofday(&start, 0);
    l.sort(comp);
    gettimeofday(&end, 0);
    cout << "LIST: ";
    printDiff(end, start);

    /* Output:
     * VECTOR: Elapsed time: 99seconds, 566816 microseconds.
     * LIST:  Elapsed time: 770seconds, 216836 microseconds
     */
    return 0;
}
More? Here's a list of all posts.
Feel free to copy, share and comment.
Tweet