QString::startWith() & QStringList::removeAll() not behaving as expected

Question

I have two lists. Both containing the same values:

 QStringList filePaths;
 filePaths.append("C:/backup");
 filePaths.append("C:/download/file1");
 filePaths.append("D:");
 filePaths.append("C:/program");
 filePaths.append("C:/download");

 QStringList refinedPaths;

 int size = filePaths.size();

 for(int i = 0; i < size; i++)
 {
   refinedPaths.append(filePaths.at(i));
 }

 for(int i = 0; i < size; i++)
 {
   QString str1 = filePaths.at(i);

   for(int j = 0; j < size; j++)
   {
     QString str2 = filePaths.at(j);

     if(str2 == str1)
     {
       continue;
     }

     if(str2.startsWith(str1))
     {
       refinedPaths.removeAll(str2);
     }
   }
 }

What I'm expecting to happen is: * Iterate through the strings in list, comparing every item in the list with each other. * If string1 starts with string2 (string2 is therefore the parent directory of string1) * remove that string from the 'refined' stringlist.

Howver, what is happening is that if(str2.startsWith(str1)) is returning true every time, and refinedPaths.removeAll(str2); doesn't remove any of the strings in the list.

Any ideas?

score 2 · Answer 1 · answered Sep 07 '11 at 14:04

Snippet below rationalises the list as required in place.

   foreach (const QString& path, filePaths)
   {
      foreach (const QString& other, filePaths)
      {
         if (other != path && other.startsWith(path))
            filePaths.removeOne (other);
      }
   }

score 1 · Accepted Answer · answered Sep 07 '11 at 15:13

1

Your code works fine, not sure what problem you are referring to. Using your code here's the output I got

C:/backup
D:
C:/program
C:/download

A few things to improve,

instead of copying QStringList element by element you can just use the copy constructor i.e copying from filePaths to refinedPaths QStringList refinedPaths(filePaths);

use iterators instead of iterating by size().

QStringList refinedPaths(filePaths);

for(QStringList::const_iterator itr1 = filePaths.begin(); filePaths.end() != itr1 ; ++itr1)
{

  for(QStringList::const_iterator itr2 = filePaths.begin(); filePaths.end() != itr2 ; ++itr2)
  {
    if(*itr1 == *itr2)
    {
      continue;
    }

    if(itr2->startsWith(*itr1))
    {
      refinedPaths.removeAll(*itr2);
    }
  }
}

answered Sep 07 '11 at 15:13

Chenna V

10,185
11
77
104

I can see the code working now - I think the variables in QtCreator's debugging mode do not update while inside a for loop, or something. Why do you suggest the use of iterators over what I have done? – nf313743 Sep 07 '11 at 16:42
For lists generally .size() operation is O(n) but QStringLists are implemented using arrayLists and the size() operation is O(1) I believe. Iterators minimize possibility of out-of-bounds errors, most existing algorithms use iterators as input. A more detailed answer is here : http://stackoverflow.com/questions/131241/why-use-iterators-instead-of-array-indices – Chenna V Sep 07 '11 at 17:04

score 0 · Answer 3 · answered Sep 07 '11 at 19:12

    filePaths.sort();
    for (int k = 0; k < filePaths.size(); )
    {
        const QString & path = filePaths[k];
        while(k+1 < filePaths.size() && filePaths.at(k+1).startsWith(path))
            filePaths.removeAt(k+1);
        k++;
    }

About 3 times faster on the given data

QString::startWith() & QStringList::removeAll() not behaving as expected

3 Answers3