c++stlqlistqvector

How to use QList with std::generate?


I ran a test to compare QVector and QList insertions/sorting performance with this code:

#include <algorithm>
#include <iostream>

#include <boost/timer/timer.hpp>

#include <QVector>
#include <QList>

int  main()
{
  constexpr auto  size = 10000000ul;

  srand(time(nullptr));

  std::cout << std::endl;
  std::cout << "-------------------------------------------------------------------------" << std::endl;
  std::cout << std::endl;

  {
    std::cout << "First test with QVector<int>" << std::endl;
    boost::timer::auto_cpu_timer  _g;
    QVector<int>                  vector(size);

    {
      std::cout << "\t Generating:" << std::endl << "\t\t";
      boost::timer::auto_cpu_timer  _;

      std::generate(std::begin(vector), std::end(vector), []
      {
        return clock() % rand();
      });
    }
    std::cout << std::endl;

    {
      std::cout << "\t Sorting:" << std::endl << "\t\t";
      boost::timer::auto_cpu_timer  _;

      std::sort(std::begin(vector), std::end(vector));
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
  std::cout << "-------------------------------------------------------------------------" << std::endl;
  std::cout << std::endl;

  {
    std::cout << "Second test with QList<int>" << std::endl;
    boost::timer::auto_cpu_timer  _g;
    QList<int>                    list;
    list.reserve(size);

    {
      std::cout << "\t Generating:" << std::endl << "\t\t";
      boost::timer::auto_cpu_timer  _;

      std::generate(std::begin(list), std::end(list), []
      {
        return clock() % rand();
      });
    }
    std::cout << std::endl;

    {
      std::cout << "\t Sorting:" << std::endl << "\t\t";
      boost::timer::auto_cpu_timer  _;

      std::sort(std::begin(list), std::end(list));
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
  std::cout << "-------------------------------------------------------------------------" << std::endl;
  std::cout << std::endl;
}

One possible output:

-------------------------------------------------------------------------

First test with QVector<int>
     Generating:
         5.544336s wall, 3.240000s user + 2.250000s system = 5.490000s CPU (99.0%)

     Sorting:
         2.593883s wall, 2.550000s user + 0.010000s system = 2.560000s CPU (98.7%)

 8.157371s wall, 5.790000s user + 2.280000s system = 8.070000s CPU (98.9%)

-------------------------------------------------------------------------

Second test with QList<int>
     Generating:
         0.000001s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

     Sorting:
         0.000001s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

 0.000060s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

-------------------------------------------------------------------------

I reserve memory with QList<int>::reserve function, and use std::generate to generate random number and insert it to QList variable. But it do nothing because of QList is always empty.

How could i fix it ?


Solution

  • The problem is that reserve only allocates memory, but it doesn't set the size.

    You can reserve any amount, but the size will still be zero.

    There's no QList function to actually set the size.

    However you might be able to use e.g. the std::back_inserter iterator adapter function to append elements to the list. Combine this with the reserve and the list shouldn't have to allocate new memory. Though you can't use it with std::generate, use std::generate_n instead:

    std::generate_n(std::back_inserter(list), size, []
    {
        return clock() % rand();
    });