Reverse Order on QStringList slow...?

[patrik08]

I must delete file and collection (folder on remote server Webdav) i read file and dir on separate list
from level 0 to infinity down ...
Now to begin to delete file and Dir i must beginn from last level down
and i reverse the list so.....

QStringList ReverseList( QStringList xx  )
 
{
 
    if (xx.size() == 0) {
 
        return xx;
 
    }
 
    QStringList newreversed;
 
     newreversed.clear();
 
       bool walking = true;
 
       int o = xx.size();
 
         for (;walking;) {
 
             o--;    /*  size 1 goto 0  ;  size 2 start on 1 end on 0 */
 
             newreversed.append(xx.at(o));
 
             if (o == 0) {
 
               walking = false;  
 
             }
 
         }
 
  return newreversed;    
 
}

QStringList ReverseList( QStringList xx  )

{

    if (xx.size() == 0) {

        return xx;

    }

    QStringList newreversed;

     newreversed.clear();

       bool walking = true;

       int o = xx.size();

         for (;walking;) {

             o--;    /*  size 1 goto 0  ;  size 2 start on 1 end on 0 */

             newreversed.append(xx.at(o));

             if (o == 0) {

               walking = false;  

             }

         }

  return newreversed;    

}

To copy to clipboard, switch view to plain text mode 

I suppose and i see now is very slow the action why?
is ther a other method to reverse a list?...

If You have a remote webdav dir ..... can you test the application?
curl -O http://ppk.ciz.ch/qt_c++/webdavdir.tar.gz
tar -zxvf w* && cd w*
qmake a.pro && make
./webdav

[wysota]

is ther a other method to reverse a list?...

#include <algorithm>
std::reverse(xx.begin(), xx.end());

#include <algorithm>
std::reverse(xx.begin(), xx.end());

To copy to clipboard, switch view to plain text mode 

But you don't have to reverse the list to iterate it in reverse order... QList has an index based way of accessing items, so you can just make a for loop:

for(int i=xx.size()-1; i>=0;i--){
  doSomething(xx.at(i));
}

for(int i=xx.size()-1; i>=0;i--){
  doSomething(xx.at(i));
}

To copy to clipboard, switch view to plain text mode 

[camel]

I must delete file and collection (folder on remote server Webdav) i read file and dir on separate list
from level 0 to infinity down ...
Now to begin to delete file and Dir i must beginn from last level down
and i reverse the list so.....

Are you sure that reversing the list is your problem? (Beside that you do not even need it as wysota mentioned ;-)

I just wrote a (completly unscientific but good enough to get an idea) benchmark for it...and it does not seem to take that much time.

Here is my test prog (with an other implementation of reverse that does only take about half of the time):

#include <QtCore>
 
 
static inline QStringList oldReverseList(const QStringList &xx)
{
    if (xx.size() == 0) {
        return xx;
    }
 
    QStringList newreversed;
    newreversed.clear();
 
    bool walking = true;
 
    int o = xx.size();
    for (;walking;) {
        o--;    /*  size 1 goto 0  ;  size 2 start on 1 end on 0 */
        newreversed.append(xx.at(o));
        if (o == 0) {
            walking = false;  
        }
    }
    return newreversed;    
}
 
static inline QStringList newReverseList(const QStringList &list)
{
    if (list.isEmpty()) {
        return QStringList();
    }
 
    QStringList reversedList = list;
    const int listSize = list.size();
    const int maxSwap = list.size() / 2;
    for (int i = 0; i < maxSwap; ++i) {
        qSwap(reversedList[i], reversedList[listSize - 1 -i]);
    }
 
    return reversedList;
}
 
int main(int argc, char* argv[])
{
    Q_UNUSED(argc);
    Q_UNUSED(argv);
 
    QStringList testList;
    for (int i = 1; i < 100; ++i) {
        testList << QString::number(i);
    }
 
    const int iterations = 1000000;
    {
        QDateTime start = QDateTime::currentDateTime();
        for (int j = 1; j < iterations; ++j) {
            QStringList reversedList = oldReverseList(testList);
            if (testList != oldReverseList(reversedList)) {
                qFatal("reverseList is broken");
            }
        }
        QDateTime stop = QDateTime::currentDateTime();
        qDebug() << iterations * 2 << "iterations of oldReverseList in" << start.secsTo(stop) << "seconds ";
    }
    {
        QDateTime start = QDateTime::currentDateTime();
        for (int j = 1; j < iterations; ++j) {
            QStringList reversedList = newReverseList(testList);
            if (testList != newReverseList(reversedList)) {
                qFatal("reverseList is broken");
            }
        }
        QDateTime stop = QDateTime::currentDateTime();
        qDebug() << iterations * 2 << "iterations of newReverseList in" << start.secsTo(stop) "seconds";
    }
    return 0;
}

#include <QtCore>


static inline QStringList oldReverseList(const QStringList &xx)
{
    if (xx.size() == 0) {
        return xx;
    }

    QStringList newreversed;
    newreversed.clear();

    bool walking = true;

    int o = xx.size();
    for (;walking;) {
        o--;    /*  size 1 goto 0  ;  size 2 start on 1 end on 0 */
        newreversed.append(xx.at(o));
        if (o == 0) {
            walking = false;  
        }
    }
    return newreversed;    
}

static inline QStringList newReverseList(const QStringList &list)
{
    if (list.isEmpty()) {
        return QStringList();
    }

    QStringList reversedList = list;
    const int listSize = list.size();
    const int maxSwap = list.size() / 2;
    for (int i = 0; i < maxSwap; ++i) {
        qSwap(reversedList[i], reversedList[listSize - 1 -i]);
    }

    return reversedList;
}

int main(int argc, char* argv[])
{
    Q_UNUSED(argc);
    Q_UNUSED(argv);

    QStringList testList;
    for (int i = 1; i < 100; ++i) {
        testList << QString::number(i);
    }

    const int iterations = 1000000;
    {
        QDateTime start = QDateTime::currentDateTime();
        for (int j = 1; j < iterations; ++j) {
            QStringList reversedList = oldReverseList(testList);
            if (testList != oldReverseList(reversedList)) {
                qFatal("reverseList is broken");
            }
        }
        QDateTime stop = QDateTime::currentDateTime();
        qDebug() << iterations * 2 << "iterations of oldReverseList in" << start.secsTo(stop) << "seconds ";
    }
    {
        QDateTime start = QDateTime::currentDateTime();
        for (int j = 1; j < iterations; ++j) {
            QStringList reversedList = newReverseList(testList);
            if (testList != newReverseList(reversedList)) {
                qFatal("reverseList is broken");
            }
        }
        QDateTime stop = QDateTime::currentDateTime();
        qDebug() << iterations * 2 << "iterations of newReverseList in" << start.secsTo(stop) "seconds";
    }
    return 0;
}

To copy to clipboard, switch view to plain text mode 

The results that I got were:

2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds

[wysota]

The results are obvious and the benchmark is not needed If you do half the amount of iterations, you'll get half amount of effort to complete the task I'm pretty certain std::reverse uses the same algorithm your newReverse does (as there is no "temporary" or "second" list so it has to store objects in the list itself and the easiest way to do that is to just swap the items).

Anyway I think the problem is not in the list (like already mentioned) but on the deleting algorithm... Why do you need those two lists (dirs/files)? Can't you do a recursive delete of the root directory?

Pseudocode follows:

bool deleteDir(const QString &path){
  bool good = true;
  QStringList entries = children(path);
  foreach(QString entry, entries){
    if(isFile(entry))
      good = deleteFile(path+entry);
    else if(isDir(entry))
      good = deleteDir(path+entry); // recursive call here
    if(!good)
      return false; // bail out on error
  }
  return deleteSelf(path);
}

bool deleteDir(const QString &path){
  bool good = true;
  QStringList entries = children(path);
  foreach(QString entry, entries){
    if(isFile(entry))
      good = deleteFile(path+entry);
    else if(isDir(entry))
      good = deleteDir(path+entry); // recursive call here
    if(!good)
      return false; // bail out on error
  }
  return deleteSelf(path);
}

To copy to clipboard, switch view to plain text mode 

[camel]

The results are obvious and the benchmark is not needed If you do half the amount of iterations, you'll get half amount of effort to complete the task I'm pretty certain std::reverse uses the same algorithm your newReverse does (as there is no "temporary" or "second" list so it has to store objects in the list itself and the easiest way to do that is to just swap the items).

Actually they are not 100% obvious, depending of you viewpoint. I am thinking about memory allocation problems.
When you have a QList and fill them one by one, you might get problems with reallocation, as the QList needs more memory.

I first thought about experimenting with that, using reserve(as in QVector::reserve()) ... until I noticed that there is not such a thing in QList ;-)

Thus, copy and detach :-)


qSwap has another (very slight) advantage over using the std algorithms (at least when using with implicitly shared Qt types, and types sufficiently declared using Q_DECLARE_TYPEINFO) as it does some bad magic if the type is only the size of a pointer. This saves some atomic operations compared to doing it via three way operator=().

TIP: Qt has a nice collection of algorithms for containers :-)


But I guess this transgresses into the realm of the very off topic ;-)

[And: these kind of optimizations should only be taken out of the safe when everything else is failing...which it they do not at this point ;-) ]

[wysota]

When you have a QList and fill them one by one, you might get problems with reallocation, as the QList needs more memory.

Yes, but the list doesn't allocate one by one, it does a preallocation.

I first thought about experimenting with that, using reserve(as in QVector::reserve()) ... until I noticed that there is not such a thing in QList ;-)

It wouldn't have much sense. QVector expands in one direction (items are "appended" to the end), whereas QList can grow in two directions (items can be "appended" or "prepended"). Reserve would not make much sense then, you'd need two methods instead ("reserveAtEnd" and "reserveAtFront"). But you can subsitute QStringList with QVector<String> without any performance loss as in this situation items are only added to the end, not anywhere inbetween or in front.

qSwap has another (very slight) advantage over using the std algorithms (at least when using with implicitly shared Qt types) as it does some bad magic if the type is only the size of a pointer. This saves some atomic operations compared to doing it via three way operator=().

Yes, it can actually exchange the values, but the value needs to be memmovable.

About the speed of std::reverse - the use of iterators should slow QList down that much. I'm convinced that the iterator in QList is not much more than item index, so access to an element should always be O(1). Operator= for QList has the same features qSwap has and additionally QString is pretty fast on its own, so that also should have such a big influence. My guess is that std::reverse is simply slow

Actually I just checked my implementation of std::reverse:

{
      while (true)
        if (__first == __last || __first == --__last)
          return;
        else
          {
            std::iter_swap(__first, __last);
            ++__first;
          }
    }

{
      while (true)
        if (__first == __last || __first == --__last)
          return;
        else
          {
            std::iter_swap(__first, __last);
            ++__first;
          }
    }

To copy to clipboard, switch view to plain text mode 

It uses the exact same algorithm your fast implementation uses. So the slowdown has to be either in QList itself or in std::iter_swap.

[wysota]

I made a test using a QVector based implementation of the oldReverseList function that preallocates all the needed memory in the constructor.

2000000 iterations of oldReverseList in 18 seconds
2000000 iterations of oldReverseList2 in 15 seconds

2000000 iterations of oldReverseList in 18 seconds
2000000 iterations of oldReverseList2 in 15 seconds

To copy to clipboard, switch view to plain text mode 

It's slightly faster, but I wouldn't call it a big difference.

The implementation:

static inline QVector<QString> oldReverseList2(const QStringList &xx)
{
    if (xx.size() == 0) {
        return QVector<QString>();
    }
    QVector<QString> newreversed(xx.size());
	int s = xx.size();
	int li = 0;
    for(int i=s-1; i>=0;i--) {
        newreversed[li++] =xx.at(i);
    }
    return newreversed;
}

static inline QVector<QString> oldReverseList2(const QStringList &xx)
{
    if (xx.size() == 0) {
        return QVector<QString>();
    }
    QVector<QString> newreversed(xx.size());
	int s = xx.size();
	int li = 0;
    for(int i=s-1; i>=0;i--) {
        newreversed[li++] =xx.at(i);
    }
    return newreversed;
}

To copy to clipboard, switch view to plain text mode 

[camel]

So the slowdown has to be either in QList itself or in std::iter_swap.

We have a winner ;-)

I added the (not very beautifull) reimplementation of std::reverse using qSwap:

static inline QStringList std2ReverseList(const QStringList &list)
{
    QStringList reversedList = list;
    QStringList::iterator __first = reversedList.begin();
    QStringList::iterator __last = reversedList.end();
    {
        while (true)
            if (__first == __last || __first == --__last)
                return reversedList;
            else
            {
                qSwap(*__first, *__last);
                ++__first;
            }
    }
}

static inline QStringList std2ReverseList(const QStringList &list)
{
    QStringList reversedList = list;
    QStringList::iterator __first = reversedList.begin();
    QStringList::iterator __last = reversedList.end();
    {
        while (true)
            if (__first == __last || __first == --__last)
                return reversedList;
            else
            {
                qSwap(*__first, *__last);
                ++__first;
            }
    }
}

To copy to clipboard, switch view to plain text mode 

The result:

2000000 iterations of oldReverseList in 14 seconds
2000000 iterations of newReverseList in 8 seconds
2000000 iterations of stdReverseList in 14 seconds
2000000 iterations of std2ReverseList in 6 seconds

This means this is the (in the moment) speediest implementation, and the problem is in std::iter_swap

;-)

[patrik08]

the fasted solution is to read list reverse .....

and QStringList::appends(QStringList other list) not exist.....

void Gui_Remove::WakeUpsFile()
{
      CodaonDelete.clear();   /* container file and dir */
      passaggiwake++;
      //////////qDebug() << "####LISTTOBE REMOVE ->" << passaggiwake << "-" << startpath;
 
      if ( passaggiwake >= 2) {
       return;   /* break if like read a 2° time and delete not exist file */
      }          
 
      QStringList RFile = ReverseList(Del_File);     /* reverse list from file  delete file on top */
 
       for (int i = 0; i < RFile.size(); ++i) {      /*  to save  time  only read  reverse the list */
           //////////qDebug() << "###file del   -> " << RFile.at(i);
           CodaonDelete.append(RFile.at(i));
       }
 
      QStringList RDir = ReverseList(Del_Dir);    /* reverse list from dir  delete dir on  last action */
 
       for (int i = 0; i < RDir.size(); ++i) {
           //////////qDebug() << "###dir del  -> " << RDir.at(i);
           CodaonDelete.append(RDir.at(i));
       }
 
        Del_File.clear();
        Del_Dir.clear();
        Del_Work_Grep.clear();
 
       if (CodaonDelete.size() > 0) {
         CodaRemove(0);    
       }
}
 
 
 void Gui_Remove::CodaRemove( int now   )    /*  loop all dir and file list  send to class delete */
{
 
     if (aborter) {       /* button abort delete */
        return;
    }
 
    int bigmap = CodaonDelete.size();
    if (bigmap == 0) {
    CodaonDelete.clear();   /* sure  */
    LastRemove();   /* remove the last on top path */
    return;
    }
 
    if (now >= bigmap) { 
    CodaonDelete.clear();
    LastRemove();   /* remove the last on top path */
    return;
    }
      for (int i = 0; i < CodaonDelete.size(); ++i)  {
                      if (now == i) {
                          QString anextpath =  RealRemotePath(CodaonDelete.at(i));
                          if (anextpath.size() > 0) {
 
                               label->setText(tr("Pending operation on: %1").arg(RealRemotePath(startpath)));
                               label_2->setText(tr("Remove wait: %1").arg(anextpath));
 
 
                           DavDelete *lismix = new DavDelete(dbdav,anextpath);    /* file or dir */
                                             lismix->SetPosition(now);
                                            connect(lismix, SIGNAL(WarningMsg(QString)), this, SLOT(ShowMessageWarning(QString)));    /* abort the loop */
                                            connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int)));    /* continue delete  from path down to up */
                          } else {
                            CodaRemove(now + 1); 
                          }
                      return;
                      }
     }
}

void Gui_Remove::WakeUpsFile()
{
      CodaonDelete.clear();   /* container file and dir */
      passaggiwake++;
      //////////qDebug() << "####LISTTOBE REMOVE ->" << passaggiwake << "-" << startpath;
    
      if ( passaggiwake >= 2) {
       return;   /* break if like read a 2° time and delete not exist file */
      }          
    
      QStringList RFile = ReverseList(Del_File);     /* reverse list from file  delete file on top */
    
       for (int i = 0; i < RFile.size(); ++i) {      /*  to save  time  only read  reverse the list */
           //////////qDebug() << "###file del   -> " << RFile.at(i);
           CodaonDelete.append(RFile.at(i));
       }
         
      QStringList RDir = ReverseList(Del_Dir);    /* reverse list from dir  delete dir on  last action */
    
       for (int i = 0; i < RDir.size(); ++i) {
           //////////qDebug() << "###dir del  -> " << RDir.at(i);
           CodaonDelete.append(RDir.at(i));
       }
       
        Del_File.clear();
        Del_Dir.clear();
        Del_Work_Grep.clear();
       
       if (CodaonDelete.size() > 0) {
         CodaRemove(0);    
       }
}


 void Gui_Remove::CodaRemove( int now   )    /*  loop all dir and file list  send to class delete */
{
    
     if (aborter) {       /* button abort delete */
        return;
    }
    
    int bigmap = CodaonDelete.size();
    if (bigmap == 0) {
    CodaonDelete.clear();   /* sure  */
    LastRemove();   /* remove the last on top path */
    return;
    }
    
    if (now >= bigmap) { 
    CodaonDelete.clear();
    LastRemove();   /* remove the last on top path */
    return;
    }
      for (int i = 0; i < CodaonDelete.size(); ++i)  {
                      if (now == i) {
                          QString anextpath =  RealRemotePath(CodaonDelete.at(i));
                          if (anextpath.size() > 0) {
                              
                               label->setText(tr("Pending operation on: %1").arg(RealRemotePath(startpath)));
                               label_2->setText(tr("Remove wait: %1").arg(anextpath));
                              
                              
                           DavDelete *lismix = new DavDelete(dbdav,anextpath);    /* file or dir */
                                             lismix->SetPosition(now);
                                            connect(lismix, SIGNAL(WarningMsg(QString)), this, SLOT(ShowMessageWarning(QString)));    /* abort the loop */
                                            connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int)));    /* continue delete  from path down to up */
                          } else {
                            CodaRemove(now + 1); 
                          }
                      return;
                      }
     }
}

To copy to clipboard, switch view to plain text mode 

[camel]

the fasted solution is to read list reverse .....

Well yeah...but it's not as much fun ;-)

and QStringList::appends(QStringList other list) not exist.....

Use operator+=

Looking at your code...have you thought about using a QStack?
you just QStack::push() whatever you find you need to delete onto it, and when you want to do it you simple QStack::pop() the contents of the stack until it is empty....

[camel]

Doing a delete with a stack (pseudo-code)

bool recursiveDeleteDir(const QString &path){
    QStack<QString> currentPathStack;
    QStack<QString> deletablePathStack;
    QStringList deletableFileList;
 
    currentPathStack.push(path);
    while (!currentPathStack.isEmpty()) {
        QString currentPath = currentPathStack.pop();
        if (!isDeletableDir(currentPath))
            return false;
 
        QStringList entries = children(currentPath);
        foreach(QString entry, entries){
            if(isFile(entry) && isDeletableFile(entry))  {
                deletableFileList << entry;
            } else if (isDir(entry)) {
                currentPathStack.push(entry);
            } else {
                return false;
            }
        }
 
        deletablePathStack.push(currentPath);
    }
    foreach(QString file, deletableFile) {
        if (!deleteFile(file)) {
            return false; //ERROR: if you get these, your isDeletableFile got a hickup :-/
        }
    }
    while (!deletablePathStack.isEmpty()) {
        if (!deleteDir(deletablePathStack.pop())) {
            return false; //ERROR: if you get these, your isDeletableDir got a hickup :-/
        }
    }
    return true;
}

bool recursiveDeleteDir(const QString &path){
    QStack<QString> currentPathStack;
    QStack<QString> deletablePathStack;
    QStringList deletableFileList;

    currentPathStack.push(path);
    while (!currentPathStack.isEmpty()) {
        QString currentPath = currentPathStack.pop();
        if (!isDeletableDir(currentPath))
            return false;

        QStringList entries = children(currentPath);
        foreach(QString entry, entries){
            if(isFile(entry) && isDeletableFile(entry))  {
                deletableFileList << entry;
            } else if (isDir(entry)) {
                currentPathStack.push(entry);
            } else {
                return false;
            }
        }
        
        deletablePathStack.push(currentPath);
    }
    foreach(QString file, deletableFile) {
        if (!deleteFile(file)) {
            return false; //ERROR: if you get these, your isDeletableFile got a hickup :-/
        }
    }
    while (!deletablePathStack.isEmpty()) {
        if (!deleteDir(deletablePathStack.pop())) {
            return false; //ERROR: if you get these, your isDeletableDir got a hickup :-/
        }
    }
    return true;
}

To copy to clipboard, switch view to plain text mode 

[patrik08]

Hmmm... to delete on a local pc a dir recursive .... i not write 200 feet code...

/* remove dir recursive */
 
void DownDir_RM(const QString d)
 
{
 
   QDir dir(d);
 
   if (dir.exists())
 
   {
 
      const QFileInfoList list = dir.entryInfoList();
 
      QFileInfo fi;
 
      for (int l = 0; l < list.size(); l++)
 
      {
 
         fi = list.at(l);
 
         if (fi.isDir() && fi.fileName() != "." && fi.fileName() != "..")
 
            DownDir_RM(fi.absoluteFilePath());
 
         else if (fi.isFile())
 
         {
 
            bool ret = qt_unlink(fi.absoluteFilePath());
 
                  if (!ret) {
 
                   //////Api_Log("Can't remove: " + fi.absoluteFilePath() + " (write-protect?)");
		  }
 
         } 
 
 
 
      }
 
      dir.rmdir(d);
 
 
 
   }
 
}

/* remove dir recursive */

void DownDir_RM(const QString d)

{

   QDir dir(d);

   if (dir.exists())

   {

      const QFileInfoList list = dir.entryInfoList();

      QFileInfo fi;

      for (int l = 0; l < list.size(); l++)

      {

         fi = list.at(l);

         if (fi.isDir() && fi.fileName() != "." && fi.fileName() != "..")

            DownDir_RM(fi.absoluteFilePath());

         else if (fi.isFile())

         {

            bool ret = qt_unlink(fi.absoluteFilePath());

                  if (!ret) {

                   //////Api_Log("Can't remove: " + fi.absoluteFilePath() + " (write-protect?)");
		  }

         } 

        

      }

      dir.rmdir(d);

      

   }

}

To copy to clipboard, switch view to plain text mode 

My problem is to delete on remote server file and path.....

to delete dir i and file i have only a class ....

new QHttp();
QHttpRequestHeader header("DELETE", pathorfile ,1,1); /* header */

http://www.webdav.org/specs/rfc2518....ection.8.6.2.1

DavDelete *lismix = new DavDelete(dbdav,anextpath);
 
                                     lismix->SetPosition(now);
 
                            connect(lismix, SIGNAL(WarningMsg(QString)), this, SLOT(ShowMessageWarning(QString)));
 
                            connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int)));

DavDelete *lismix = new DavDelete(dbdav,anextpath);

                                     lismix->SetPosition(now);

                            connect(lismix, SIGNAL(WarningMsg(QString)), this, SLOT(ShowMessageWarning(QString)));

                            connect(lismix, SIGNAL(ConChain(int)), this, SLOT(CodaRemove(int)));

To copy to clipboard, switch view to plain text mode 

and i have only QStringList from file and Dir or a domdocument like this...
http://ppk.ciz.ch/qt_c++/davinfo.xml

to display tree folder like mc gui....

[wysota]

I don't see a difference between local and remote delete. The mechanism is the same, you only call a different method to do the actual delete.

[camel]

new QHttp();
QHttpRequestHeader header("DELETE", pathorfile ,1,1); /* header */

http://www.webdav.org/specs/rfc2518....ection.8.6.2.1

DavDelete *lismix = new DavDelete(dbdav,anextpath);

DavDelete *lismix = new DavDelete(dbdav,anextpath);

To copy to clipboard, switch view to plain text mode 

If the first two lines are the contents of your DavDelete, may I propose to you to change the class to take a list of files to delete?

The problem with your approach is that for every delete a new connection to the webdav server is created, while if you would create multiple requests on a single QHttp the same connection might be used, which is generally faster (even more so if the server and QHttp can do pipelining..but I do not know that).


(Disregard if you are actually doing this ;-)

The recursiveDeleteDir approach I posted would work very well for that, since you have, at the end, a list of all paths and files to delete (even in the right order so that you can delete them in a row without error) which you would just have to send to the WebDav server.

[For this to work efficiently, you must have the isFile, isDir children etc. function only using a local cache of course ;-)]

[camel]

Just to post my latest findings (of how you can speed up standard algorithms when you work with Qt types)

I simply added the following code:

static inline void swap(QString& a, QString& b)
{
    qSwap(a,b);
}

static inline void swap(QString& a, QString& b)
{
    qSwap(a,b);
}

To copy to clipboard, switch view to plain text mode 

That changed the result to:

2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds
2000000 iterations of stdReverseList in 7 seconds
2000000 iterations of std2ReverseList in 6 seconds

That means you get very easily a great(*) speedup because the STL can now use the optimizations used in qSwap. (Still not as fast as the overall winner here, but the absolute winner in the work/result ratio category :-)

(*): "great" of course only if you do 2000000 million iterations of a reverse list algorithm...which you probably do not do ;-)
but its probably a thing to keep in mind if you find the std algorithms taking too long for your taste :-)

[camel]

I'm pretty certain std::reverse uses the same algorithm your newReverse does

Actually I just added a stdReverseList to the mix

static inline QStringList stdReverseList(const QStringList &list)
{
    QStringList reversedList = list;
    std::reverse(reversedList.begin(), reversedList.end());
    return reversedList;
}

static inline QStringList stdReverseList(const QStringList &list)
{
    QStringList reversedList = list;
    std::reverse(reversedList.begin(), reversedList.end());
    return reversedList;
}

To copy to clipboard, switch view to plain text mode 

Result:

2000000 iterations of oldReverseList in 13 seconds
2000000 iterations of newReverseList in 7 seconds
2000000 iterations of stdReverseList in 14 seconds

My totaly unscientific guess to explain the result, would be that access via the iterators (as needed by std::reverse) is slower than access via operator[]...