5 ms·
Every directory has entries "." and "..", which we aren't interested in. We filter them out with a helper function Dots(). bool Dots(const char* s) { return
by rasz 8y ago
Every directory has entries "." and "..", which we aren't interested in. We filter them out with a helper function Dots().
bool Dots(const char* s) { return s[0] == '.' && (!s[1] || (s[1] == '.' && !s[2])); }
why would you iterate over every single file entry? both . .. entries will land at one end of sorted list anyway.
- romka2 8y ago"." and ".." are filtered out before sorting. Sorting is O(N^2) in the common case (when there are fewer than 65 files in a directory), so it pays off to reduce the number of entries by 2 before we get there.
- rasz 8y agon log n? and arent . .. entries always at the beginning of the list? could just skip first 2 elements (or stop comparing after filtering . ..). What about scandir?
- jwilk 8y ago> n log n? From the article: Digging into the source code of std::sort() we can see that it uses Insertion Sort for short collections. Our 32-element vector falls under the threshold. Insertion Sort makes O(N^2) comparisons > arent . .. entries always at the beginning of the list? No.
- O_H_E 8y agoYou forgot to quote/code block, and to add a second newline
- jplayer01 8y agoI hope nobody ever uses code blocks. They're unreadable on mobile.
- tedunangst 8y agoAssuming that, branch predictor should make that check close to free. But the code still works even when that assumption is violated.