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

Question

我试图使用其insert(const_iterator pos, InputIt first, InputIt last)成员函数模板将目录条目的转换范围插入到矢量中。不幸的是，我无法在GCC11.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++，返回void。

这可以说是c++ 98迭代器模型中的一个缺陷，它仍然要求甚至输入迭代器具有返回原始类型的后缀operator++。即使这是一个悬空操作。在c++ 20迭代器模型中，对于输入迭代器，后缀自增可以返回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++ 20input_range(它是)。

这样做的目的是让你很快就能写:

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

但是要到c++ 23才会有

Answer 2

只是想添加一个替代的解决方案。关于这个问题的解释请参考Barry的回答。下面的适配器可用于使迭代器适应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到容器末端的距离的线性"。范围::拷贝是"精确(最后一个-第一个)赋值";其中对std::insert_iterator赋值调用vector::insert(const_iterator pos, const T&值)，该值与容器的位置和末端之间的距离呈线性关系。这是因为当每次插入一个元素时，vector每次都需要将之后的所有元素移动1。

另一方面，vector::insert(const_iterator pos, InputIt first, InputIt last)在std::distance(first, last)上是线性的，在pos到容器末端的距离上是线性的;或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)
);

如果vector先前为空，则这三个选项之间没有复杂性差异，但也没有理由使用insert而不是push_back。

基准测试突出复杂性问题。

对我来说，带适配器的选项是最清晰的，也有很好的复杂性。如果你知道如何为Cpp17InputIterator写一个更通用(更好)的适配器，请告诉我。