为什么我不能将这个转换后的 directory_iterator 插入到向量中？

Question

我正在尝试使用其 insert(const_iterator pos, InputIt first, InputIt last) 成员函数模板将转换后的目录条目范围插入向量中。不幸的是，我无法在 GCC 11.1.0 下编译以下代码，它应该根据 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
    );
}

报错信息主要是说：

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>&)'

再往下：

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> >’

我已尝试将上述特化添加到 std::iterator_traits 以用于相关的迭代器类型，但无济于事。我想了解为什么这不能编译，如果可能的话，如何修复它。我想避免创建临时向量。

如果需要更多 gcc 的错误消息，请告诉我。

Answer 1

fs::directory_iterator是一个输入范围。这意味着当你通过 transform 调整它时，你仍然会得到一个输入范围（自然）。此转换范围的迭代器有一个后缀 operator++，即 returns void.

这可以说是 C++98 迭代器模型中的一个缺陷，它仍然需要 甚至输入迭代器 有一个后缀 operator++ return编辑回原来的类型。即使这必然是悬空操作。在 C++20 迭代器模型中，后缀增量可以 return void 用于输入迭代器。

因此，您返回的转换范围（views::common 是空操作，它已经是 common）是一个 C++20输入范围（正如您正在验证的那样），但它不是任何类型的 C++98/C++17 范围，因为它的迭代器甚至不满足 Cpp17InputIterator 由于那个后缀递增规则——所以它的迭代器甚至懒得提供 iterator_category.

这使得：

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

失败，因为此函数需要满足 Cpp17InputIterator 的类型，而 b 和 e 不满足。

解决方法是：

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

或者甚至将这两个步骤结合起来：

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

在这里，我们只要求源代码范围是 C++20 input_range（它是）。

目的是您很快就能写：

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

但直到 C++23 才会出现。

Answer 2

只是想添加一个替代解决方法。问题的解释请参考。以下适配器可用于将迭代器适配到 vector::insert.

的接口

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

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

template <typename It>
struct insertable_iterator_adapter : It {
    using iterator_category = std::input_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = std::decay_t<decltype(*std::declval<It>())>;
    using pointer = value_type*;
    using reference = value_type&;
};

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(); });

    directory_tree.insert(
        directory_tree.begin(),
        insertable_iterator_adapter{ranges::begin(subdir_names)},
        insertable_iterator_adapter{ranges::end(subdir_names)}
    );
}

尽管我不确定此解决方案适用于多少其他算法。

编辑：我不认为像

那样使用 std::inserter

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

当 directory_tree 已经有值时，

是个好主意，因为复杂度为 O(n * k)，其中 n = previous directory_tree.size() 和 k = subdir_names.size()

根据 cppreference vector::insert(const_iterator pos, InputIt first, InputIt last) 是“在 std::distance(first, last) 中线性加上 pos 和 end 之间的距离线性容器”。 ranges::copy 是“完全（最后 - 第一个）赋值”，其中对 std::insert_iterator 的赋值调用 vector::insert(const_iterator pos, const T& value) 这是“在 pos 之间的距离中呈线性和容器的末端” 这是因为当一次插入一个元素时，vector 每次都需要将所有元素都移动一个。

另一方面 vector::insert(const_iterator pos, InputIt first, InputIt last) 是“在 std::distance(first, last) 中线性加上 pos 和容器的末端”或 O(k + n).

具有相同 O(k + n) 复杂度的另一种选择是

ranges::copy(subdir_names, std::back_inserter(directory_tree));
std::rotate(
  ranges::begin(directory_tree),
  ranges::begin(directory_tree) + previous_size,
  ranges::end(directory_tree)
);

如果您的向量之前是空的，那么这三个选项之间没有复杂性差异，但是也没有理由插入而不是 push_back。

Benchmark 突出了复杂性问题。

对我来说，带适配器的选项是最清晰的，也具有很好的复杂性。如果您知道如何为 Cpp17InputIterator 编写更通用（更好）的适配器，请告诉我。

为什么我不能将这个转换后的 directory_iterator 插入到向量中？

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

c++

stdvector

c++20

std-filesystem

std-ranges