0
\$\begingroup\$

I'm trying to print out a list of files in a specific order, with files closer to the root directory sorted first. For example these files:

  • c:\users\steve\foo.txt
  • c:\users\bar.txt
  • c:\users\steve\desktop\file.txt
  • c:\users\john\bing.txt

Should be sorted as:

  • c:\users\bar.txt
  • c:\users\john\bing.txt
  • c:\users\steve\foo.txt
  • c:\users\steve\desktop\file.txt

Code:

namespace fs = std::experimental::filesystem;

std::vector<std::string> sortedRules;
std::sort(sortedRules.begin(), sortedRules.end(), 
    [&](const string &str1, const string &str2)
{
    fs::path path1(str1);
    fs::path path2(str2);

    //if parent directories are the same, compare filenames
    if (path1.parent_path() == path2.parent_path())
        return path1 < path2;

    std::vector<std::string> path1Expnded;
    std::vector<std::string> path2Expnded;

    for (const auto &part : path1)
        path1Expnded.emplace_back(part.string());

    for (const auto &part : path2)
        path2Expnded.emplace_back(part.string());

    //if paths have same amount of stems, compare full paths
    if (path1Expnded.size() == path2Expnded.size())
        return path1 < path2;

    int minSize;
    path1Expnded.size() <= path2Expnded.size()
        ? minSize = path1Expnded.size()
        : minSize = path2Expnded.size();

    //sort by first differing stem
    for (int i = 0; i < minSize - 1; i++)
        if (path1Expnded[i] != path2Expnded[i])
            return path1Expnded[i] < path2Expnded[i];

    //if sizes differ and no stems are the same, sort by number of stems
    return path1Expnded.size() < path2Expnded.size();
});

I created a custom comparison lambda that overrides how std::sort compares, and it works most of the time. Sometimes items cannot be found after being sorted using this comparison lambda, and after being searched for using this same comparison lambda. So I'm guessing my algorithm is somehow incorrect.

Also even when the algorithm does run, it does so very slowly. It took me awhile to get the files to sort just the way I wanted, and while I tried to allow the function to return as soon as possible its performance is pretty poor. How can I fix the algorithm to ensure its correctness, and also make it more efficient?

\$\endgroup\$
1
  • \$\begingroup\$ Here's one possible solution using std::multimap, have a look here. \$\endgroup\$
    – Juho
    Dec 21 '17 at 9:06
1
\$\begingroup\$

First, don't use the conditional operator as an if statement. Either encode the conditional as part of the initialization of minSize, or use an if statement instead of the conditional. In this case, though, a better solution is to make use of the standard min function:

int minSize = std::min(path1Expnded.size(), path2Expnded.size());

But we can redo your code to eliminate this part.

The sort you've coded and the one you describe (how I am interpreting your description, anyway) are different, as your code only looks at the number of subfolders if one path is in a subfolder of the folder that has the file in the other path.

Your problem description ("files closer to the root directory sorted first"), sounds like all the paths with fewer folders should be before longer ones, in which case the number of stems should be the first thing compared. Then a direct comparison on the full paths if they have the same folder count.

What you've coded up will put files in a folder before subfolders of that folder. Your current implementation does a lot of memory allocations and frees, mainly with strings and vector resizes. You can simplify this a lot by first comparing the two parent_paths. If they are different, return the result of this comparison (the path to a file will be shorter than the path for a subfolder in the folder with the file, so it'll be earlier). Otherwise the two paths are the same, and return the result of comparing the filenames.

\$\endgroup\$
1
  • \$\begingroup\$ Wow, the algorithm you described is so concise, and actually runs pretty fast! As usual I was grossly over complicating things haha. Thanks for your answer! \$\endgroup\$ Dec 22 '17 at 1:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.