Why can't I insert this transformed directory_iterator into a vector?

Question

I am trying to insert a transformed range of directory entries into a vector using its insert(const_iterator pos, InputIt first, InputIt last) member function template. Unfortunately I can't get the following code to compile under GCC 11.1.0, which should have ranges support according to https://en.cppreference.com/w/cpp/compiler_support.

#include <filesystem>
#include <vector>
#include <ranges>
#include <iterator>

namespace fs = std::filesystem;
namespace ranges = std::ranges;
namespace views = std::views;

// no solution
namespace std {
    template <typename F>
    struct iterator_traits<ranges::transform_view<ranges::ref_view<fs::directory_iterator>, F>> {
        using iterator_category = std::input_iterator_tag;
    };
}

int main() {
    std::vector<fs::path> directory_tree;

    auto subdir = fs::directory_iterator(".");
    ranges::input_range auto subdir_names = subdir
        | views::transform([](const auto& entry) { return entry.path(); /* can be more complex*/ })
        | views::common;
    
    // replacing subdir_names with subdir works
    std::input_iterator auto b = ranges::begin(subdir_names);
    std::input_iterator auto e = ranges::end(subdir_names);
    directory_tree.insert(
        directory_tree.begin(),
        b,
        e
    );
}

The error message mainly says:

error: no matching function for call to 'std::vector<std::filesystem::__cxx11::path>::insert(std::vector<std::filesystem::__cxx11::path>::iterator, std::ranges::transform_view<std::ranges::ref_view<std::filesystem::__cxx11::directory_iterator>, main()::<lambda(const auto:16&)> >::_Iterator<false>&, std::ranges::transform_view<std::ranges::ref_view<std::filesystem::__cxx11::directory_iterator>, main()::<lambda(const auto:16&)> >::_Iterator<false>&)'

and further down:

error: no type named ‘iterator_category’ in ‘struct std::iterator_traits<std::ranges::transform_view<std::ranges::ref_view<std::filesystem::__cxx11::directory_iterator>, main()::<lambda(const auto:15&)> >::_Iterator<false> >’

I have tried to add the above specialisation to std::iterator_traits for the concerning iterator type but to no avail. I want to understand why this does not compile and if possible, how it can be fixed. I want to avoid creating a temporary vector.

Let me know if more of gcc's error message is required.

Answer 1

fs::directory_iterator is an input range. Which means that when you adapt it via transform you still get an input range (naturally). This transformed range's iterators have a postfix operator++ that returns void.

This was arguably a defect in the C++98 iterator model, which still required even input iterators to have a postfix operator++ that returned the original type back. Even if this was necessarily a dangling operation. In the C++20 iterator model, postfix-increment can return void for input iterators.

As such, the transformed range you get back (the views::common is no-op, it's already common) is a C++20 input range (as you're verifying) but it's not any kind of C++98/C++17 range because its iterators do not even satisfy Cpp17InputIterator due to that postfix-increment rule - and so its iterators don't even bother providing iterator_category.

That makes:

directory_tree.insert(directory_tree.begin(), b, e);

fail, since this function expects types that satisfy Cpp17InputIterator, and b and e do not.

---

The workaround is to instead do:

ranges::copy(subdir_names, std::inserter(directory_tree, directory_tree.begin()));

Or even combine the two steps:

ranges::copy(subdir
        | views::transform([](const auto& entry) { return entry.path(); /* can be more complex*/ }),
        std::inserter(directory_tree, directory_tree.begin())
);

Here, we only require the source range to be a C++20 input_range (which it is).

The intent is that soon you will be able to write:

directory_tree.insert_range(
        directory_tree.begin(),
        subdir
        | views::transform([](const auto& entry) { return entry.path(); }));

but that won't be until C++23.