CODEWITHSUNDEEP
c++sortingc++17dereferencestd-filesystem
Miami
Miami

Reputation: 69

'Attempt to dereference a past-the-end iterator' when sorting a vector of filesystem paths

I'm writing a simple file chooser using std::filesystem. The entries of the current directory are stored in a vector. When I try to sort the vector with std::sort the program crashes.

This happens with g++-9 on Ubuntu 19.04. The file is compiled with the -D_GLIBCXX_DEBUG and -D_GLIBCXX_DEBUG_PEDANTIC debug flags.

The relevant code looks like this:

#include <filesystem>
#include <vector>
#include <algorithm>

namespace fs = std::filesystem;

struct FileBrowser {
    std::vector<fs::path> files;

    FileBrowser() {
        UpdateFiles();
    }

    void UpdateFiles() {
        files.clear();
        for (const auto& entry : fs::directory_iterator(currentPath)) {
            files.push_back(entry.path());
        }


        std::sort(files.begin(), files.end(), [](const auto& lhs, const auto& rhs) {
            if (fs::is_directory(lhs) && !fs::is_directory(rhs)) {
                return 1;
            } else if (fs::is_directory(rhs) && !fs::is_directory(lhs)) {
                return 0;
            } else {
                return lhs.filename().string().compare(rhs.filename().string());
            }
        });
    }
};

The error message looks like this:

/usr/include/c++/9/debug/safe_iterator.h:294:
In function:
    __gnu_debug::_Safe_iterator<_Iterator, _Sequence, _Category>::reference 
    __gnu_debug::_Safe_iterator<_Iterator, _Sequence, 
    _Category>::operator*() const [with _Iterator = 
    __gnu_cxx::__normal_iterator<std::filesystem::__cxx11::path*, 
    std::__cxx1998::vector<std::filesystem::__cxx11::path, 
    std::allocator<std::filesystem::__cxx11::path> > >; _Sequence = 
    std::__debug::vector<std::filesystem::__cxx11::path>; _Category = 
    std::forward_iterator_tag; __gnu_debug::_Safe_iterator<_Iterator, 
    _Sequence, _Category>::reference = std::filesystem::__cxx11::path&]

Error: attempt to dereference a past-the-end iterator.

Objects involved in the operation:
    iterator "this" @ 0x0x7fff6c67d9d0 {
      type = __gnu_cxx::__normal_iterator<std::filesystem::__cxx11::path*, std::__cxx1998::vector<std::filesystem::__cxx11::path, std::allocator<std::filesystem::__cxx11::path> > > (mutable iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::vector<std::filesystem::__cxx11::path, std::allocator<std::filesystem::__cxx11::path> >' @ 0x0x55ca5b4536c0
    }

I saw plenty of examples online where std::sort is called with vector.end(). I tried it with files.end() - 1 and received the same error message.

Upvotes: 3

Views: 1055

Answers (1)

Piotr Skotnicki
Piotr Skotnicki

Reputation: 48487

std::sort requires a strict weak ordering comparator, as described in [alg.sorting]/p3:

[...] For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.

A strict weak ordering comparator should return true only if the left hand side operand precedes the right hand side operand, and false otherwise.

The std::basic_string::compare function encodes its result as <0, 0 and >0, if the string is lexicographically less, equal or greater than the argument expression, respectively. This allows to determine the mutual relation between its arguments in a single pass. However, both positive and negative values are implicitly convertible to the true boolean value, and so the result will be misinterpreted by any standard library algorithm, leading to undefined behavior. In order to avoid that, the std::sort function call could look as follows:

std::sort(files.begin(), files.end(), [](const auto& lhs, const auto& rhs) {
    if (fs::is_directory(lhs) && !fs::is_directory(rhs)) {
        return true;
    } else if (fs::is_directory(rhs) && !fs::is_directory(lhs)) {
        return false;
    } else {
        return lhs.filename().string() < rhs.filename().string();
        //                            ~^~
    }
});

Upvotes: 6

Related Questions