Sort filenames naturally with Qt

Question

I am reading a directories content using QDir::entryList(). The filenames within are structured like this:

index_randomNumber.png

I need them sorted by index, the way the Windows Explorer would sort the files so that I get

0_0815.png
1_4711.png
2_2063.png
...

instead of what the sorting by QDir::Name gives me:

0_0815.png
10000_6661.png
10001_7401.png
...

Is there a built-in way in Qt to achieve this and if not, what's the right place to implement it?

Answer 1

If you want to use QCollator to sort entries from the list of entries returned by QDir::entryList, you can sort the result with std::sort():

dir.setFilter(QDir::Files | QDir::NoSymLinks);
dir.setSorting(QDir::NoSort);  // will sort manually with std::sort

auto entryList = dir.entryList();

QCollator collator;
collator.setNumericMode(true);

std::sort(
    entryList.begin(),
    entryList.end(),
    [&collator](const QString &file1, const QString &file2)
    {
        return collator.compare(file1, file2) < 0;
    });

---

According to The Badger's comment, QCollator can also be used directly as an argument to std::sort, replacing the lambda, so the call to std::sort becomes:

std::sort(entryList.begin(), entryList.end(), collator);

Answer 2

Qt didn't have natural sort implementation until Qt 5.2, see this feature request.

Since Qt 5.2 there is QCollator which allows natural sort when numeric mode is enabled.

Answer 3

Yes it is possible.

In order to do that you need to specify the flag LocaleAware when constructing the QDir. object. The constructor is

 QDir(const QString & path, const QString & nameFilter, SortFlags sort = SortFlags( Name | IgnoreCase ), Filters filters = AllEntries)

You can also use

QDir dir;
dir.setSorting(QDir::LocaleAware);

Answer 4

This isn't an answer to the question as such, but some general information for the benefit of others that stumble across this trying to figure out how to "sort naturally".

First off: it's impossible. "Correct" natural sorting depends on context that — short of "true" artificial intelligence — is virtually impossible to have. For instance, if I have a bunch of file names with mixed numbers and letters, and some parts of those names happen to match [0-9a-f], is that a hexadecimal number? Is "1,500" the same as "1500", or are "1" and "500" individual numbers? Does "2019/06/07" come before or after "2019/07/06"? What about "1.21" vs. "1.5"? (Hint: the last depends on if those are decimal numbers or semantic version numbers.)

"Solving" this problem requires constraining it; deciding we're only going to handle specific cases, and anything outside of those bounds is just going to produce a "wrong" answer. (Fortunately, the OP's problem would appear to already satisfy the usual set of constraints.)

That said, I believe QCollator works generally well (again, in that it doesn't "really" work, but it succeeds within the constraints that are generally accepted). In the "own solutions" department, have a look also at qtNaturalSort, which I wrote as a Qt-API improvement over a different (not QCollator) algorithm. (Case insensitivity is not supported as of writing, but patches welcomed!) I put a whole bunch of effort into making it parse numbers "correctly", even handling numbers of arbitrary length and non-BMP digits.

Answer 5

inline int findNumberPart(const QString& sIn)
{
  QString s = "";
  int i = 0;
  bool isNum = false;
  while (i < sIn.length())
  {
    if (isNum)
    {
      if (!sIn[i].isNumber())
        break;
      s += sIn[i];
    }
    else
    {
      if (sIn[i].isNumber())
        s += sIn[i];
    }
    ++i;
  }
  if (s == "")
    return 0;
  return s.toInt();
}

bool naturalSortCallback(const QString& s1, const QString& s2)
{
  int idx1 = findNumberPart(s1);
  int idx2 = findNumberPart(s2);
  return (idx1 < idx2);
}

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

  QDir dir(MYPATH);
  QStringList list = dir.entryList(QDir::AllEntries | QDir::NoDotAndDotDot);
  qSort(list.begin(), list.end(), naturalSortCallback);
  foreach(QString s, list)
    qDebug() << s << endl;

  return a.exec();
}

Answer 6

Qt doesn't support natural sorting natively, but it can be quite easily implemented. For example, this can be used to sort a QStringList:

struct naturalSortCompare {

    inline bool isNumber(QChar c) {
        return c >= '0' && c <= '9';
    }

    inline bool operator() (const QString& s1, const QString& s2) {
        if (s1 == "" || s2 == "") return s1 < s2;

        // Move to the first difference between the strings
        int startIndex = -1;
        int length = s1.length() > s2.length() ? s2.length() : s1.length();
        for (int i = 0; i < length; i++) {
            QChar c1 = s1[i];
            QChar c2 = s2[i];
            if (c1 != c2) {
                startIndex = i;
                break;
            }
        }

        // If the strings are the same, exit now.
        if (startIndex < 0) return s1 < s2;

        // Now extract the numbers, if any, from the two strings.
        QString sn1;
        QString sn2;
        bool done1 = false;
        bool done2 = false;
        length = s1.length() < s2.length() ? s2.length() : s1.length();

        for (int i = startIndex; i < length; i++) {
            if (!done1 && i < s1.length()) {
                if (isNumber(s1[i])) {
                    sn1 += QString(s1[i]);
                } else {
                    done1 = true;
                }
            }

            if (!done2 && i < s2.length()) {
                if (isNumber(s2[i])) {
                    sn2 += QString(s2[i]);
                } else {
                    done2 = true;
                }
            }

            if (done1 && done2) break;
        }

        // If none of the strings contain a number, use a regular comparison.
        if (sn1 == "" && sn2 == "") return s1 < s2;

        // If one of the strings doesn't contain a number at that position,
        // we put the string without number first so that, for example,
        // "example.bin" is before "example1.bin"
        if (sn1 == "" && sn2 != "") return true;
        if (sn1 != "" && sn2 == "") return false;

        return sn1.toInt() < sn2.toInt();
    }

};

Then usage is simply:

std::sort(stringList.begin(), stringList.end(), naturalSortCompare());